- •Бояршинов, М.Г.
- •1. ЧИСЛЕННЫЕ МЕТОДЫ АЛГЕБРЫ
- •1.1. Системы линейных алгебраических уравнений
- •1.2. Нелинейные уравнения
- •1.3. Аппроксимация функций
- •1.4. Собственные значения и собственные векторы
- •2. ЧИСЛЕННЫЕ МЕТОДЫ АНАЛИЗА
- •2.1. Численное дифференцирование
- •2.2. Численное интегрирование
- •3.2. Граничные задачи
- •4. ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО ВЫПОЛНЕНИЯ
- •4.1. Системы линейных алгебраических уравнений
- •4.2. Нелинейные уравнения
- •4.3. Аппроксимация функции
- •4.4. Собственные значения и собственные векторы
- •4.7. Задачи Коши
- •4.8. Граничные задачи
- •БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1.3. Аппроксимация функций
Под аппроксимацией заданной функции /(х ) понимается нахождение функции ф(х) из некоторого определенного класса (например, среди алгебраи ческих многочленов заданной степени), в том или ином смысле близкой к /(х ) и дающей ее приближенное представление.
Для решения ряда прикладных задач возникает необходимость прибли женной замены функции f( x ) некоторым набором известных функций, вычис ление которых проще организовать. В частности, может рассматриваться зада ча о наилучшем приближении в нормированном пространстве Я, когда задан ную функцию / € Я требуется заменить линейной комбинацией известных
элементов ср* е Я , к = 0,л, так, чтобы отклонение 1/ - *=0 У было мини-
мальным.
Частный случай аппроксимации функции - задача интерполирования - со стоит в том, чтобы функцию /(х ), известную лишь в узлах некоторой сетки
заданного отрезка, то есть определенную в виде таблицы, /(х ,)= / ,,/ = 0,л,
приблизить непрерывной на этом отрезке функцией ср(х), которая в точках х, совпадает с заданными табличными значениями,
Ф(*/)=//> <= 0,л.
Функция ср(х) может определяться, например, следующим образом:
п
Ф ( * ) = 1 > л ( х)’
к=0
где ф*(х) - набор линейно независимых функций. Очевидно, что в приведен ных примерах задач о наилучшем приближении и интерполировании функция ф(х) определяется набором параметров ак, к = 0, п , от которых зависит линей но. В противном случае говорят о нелинейной аппроксимации.
1.3.1. Интерполяционный многочлен Ньютона
Задание. Аппроксимировать функцию /(x ) = |xj на отрезке [-1, 1] с ис
пользованием полинома Ньютона. Исследовать сходимость последовательно сти полиномов на равномерной и чебышёвской сетках.
Алгоритм решения
Для произвольной функции /(х ) определим разделенные разности: - первая разделенная разность
f{xh Xj)= [/(* ,)-/(ху)] Дх,- -Ху),
- вторая разделенная разность
f { xi’xj>xk)~ [/^*i’xj )~ f(,xj ’хк)] j{xi ~ xk)i - третья разделенная разность
f{xi>Xj<xk,x,)= |/(х,,х>)х * )-/(х у,х*,х/)] /{ х .- х ,)
и так далее. Пусть Рп(х) - искомый интерполяционный многочлен степени п. Запишем для него разделенные разности:
Л.(х.х0) = [/5л(х ) - />п(д:о)] /( х - х 0), / >я(х,х0,х1)= [Рл(х,х0) - Р л(х0>х,)] /(х - х ,),
Рл(х,х0,х,,х2) = [Рл(х,х0,х,)—Рл(х0,х,,х2)] /( х - х 2) , ...
Отсюда получаем выражение для полинома в виде pA x )= pA*o)+рАх-хо)(х ~ хо)=
=^n(*o)+ (* - * o )k (Jfo ^ i)+ (* -;lciK(*.Xo,x1)]=
=^(*о)+(*~*о) [pn(Jco.xI)+(x -x,X />„(x0,x1,x2)+ (x -x 2)/5„(x,x0,xl,x;,)}]=..
Иначе это выражение можно записать в такой форме:
^(* )= ^ (х о )+ (х - х 0)/,л(х0,х1)+
+(х- х0)(х- х,)Рп(хо,х,,х2)+(х- х0)(х- х,)(х- х2)/5„(х,х0.х|,х2)+...
Поскольку в точках xh / = 0, п значения полинома Р„(х,) должны совпадать со значениями заданной функции /(*, ), то должны совпадать и соответствую щие разделенные разности: / ’„(XQ^ /(*о)» Рп(хо>х\)= /(*o»xi) и так далее. По этому искомый полином записывается в форме
Рп = /(*0 )+ (Х - Х0)[/■(*0.■*1)+ (*~ *1 ){/(*0 •*1.■*2 )+ •'• ■•}]
или
Л(х) = /(х 0)+ (х - х0)/(х0,х,)+ (х - х0)(х - х, )/(х0,х, .х2)+ ...
Погрешность аппроксимации функции /(х ) полиномом Рп(х) на отрезке
[a, b] определяется выражением
где |
= n ja ^ |/(B+1)(x)|, o (x )= (x -x 0)(x - x ,) ...(x - x j. |
Погрешность аппроксимации можно уменьшить, если использовать в ка
честве узловых точек корни полинома Чебышева степени п,
Ь + а |
Ь - а |
2/ +1 |
— |
*/= — |
+ — |
С05^ к , |
1 = 0,«. |
В этом случае оценка погрешности полинома Ньютона имеет вид
Выполнение расчетов
Пусть на отрезке [-1, 1] построена равномерная сетка, содержащая 5 узлов. Воспользуемся аналитической зависимостью /(х ) = |х| для табличного задания функции. Узловые координаты х, и соответствующие им значения функции /(* ,) приведены в табл. 1.9. Здесь же представлены значения разделенных раз ностей, определенные с использованием приведенных выше соотношений.
|
|
|
Таблица 1.9 |
|
Табличное задание функции /(х ) = |х| и значения соответствующих |
||
|
разделенных разностей для равномерной сетки на отрезке [-1,1] |
||
X, |
/(*,) /(*Г*/+1) |
У^(х,,Х;+1,Х/+|) /(*/»*/+1»xi+2»xi+3) |
f ( xi,xi+1»xi+2»xi+3>xi+4 ) |
-1,0 |
1,0 |
|
|
|
-1,0 |
|
|
-0,5 |
0,5 |
0,0 |
|
|
“ 1,0 |
1,3333 |
-1,3333 |
0,0 |
0,0 |
2,0 |
|
|
1,0 |
-1,3333 |
|
0,5 |
0,5 |
0,0 |
|
1,0 |
1,0 |
|
|
1,0 |
|
|
Использование полученных разделенных разностей позволяет построить на отрезке [-1, 1] полином Ньютона, соответствующий функции /(х ) = |х|, за данной таблично с помощью равномерной сетки, содержащей 5 узлов:
P4(x)=l + fx + l) ( - I + (х + 0,5){0 + (х - 0)[1,3333 + (х - 0,5)(-1,3333)]}).
Аналогичным образом строятся аппроксимации на сетках, содержащих 3, 9,17,33 и 65 узлов1. Вид соответствующих функций приведен на рис. 1.10.
1Рекомендуется выполнять вычисления с использованием переменных вещественного типа «двойной точности».
38
На рис. 1.11 показана зависимость погрешности аппроксимации полино мами Рп(х) заданной функции /(х ) = | х | на равномерных сетках:
5» = II рп(*)- / МП = |
/ Ml • |
Рис. 1.10. Аппроксимация на отрезке [-1,1] функции /(х ) = |х| полино мами Ньютона Л»(х), построенными с использованием равномерных сеток
Рис. 1.11. Погрешность аппроксимации у функции /(х ) = |х|
полиномами Ньютона Рп(х) на отрезке [-1,1] в зависимости от номера п на равномерных сетках
Для повышения точности аппроксимации функции полиномом Ньютона воспользуемся чебышевской сеткой на отрезке [-1,1]:
х, = cos[(2/ + 1)л/2(п + 1)1 / = 07л.
Втабл. 1.10 представлены значения разделенных разностей, определенные
сиспользованием чебышёвской сетки.
Полученные разделенные разности позволяют построить на отрезке [-1, 1] полином Ньютона, соответствующий функции /(х ) = |х|, заданной таблично с
помощью чебышёвской сетки, содержащей 5 узлов:
Р<(х) =0,9511+ (х+0,951 lX-1+(х+ 0 ,5 8 7 # + ( х - 0)[l,l 056+ (х - 0 ,5 8 7 # 1,162#.
Таблица 1.10 Табличное задание функции /(х ) = |х| и значения соответствующих
разделенных разностей для чебышёвской сетки на отрезке [-1, 1]
*/ |
/(*.-) /(*/.*/+о |
/(*(,*/+l,*l+l) |
l,Xit2,XM ,Xi+4) |
-0,9511 |
0,9511 |
|
|
|
-1,0 |
0,0 |
|
-0,5878 |
0,5878 |
1,1056 |
|
|
-1,0 |
|
|
0,0 |
0,0 |
1,7013 |
-1,1625 |
|
1,0 |
0,0 |
-1,1056 |
0,5878 |
0,5878 |
|
|
|
1,0 |
|
|
0,9511 |
0,9511 |
|
|
Р * - |
|
|
|
1,2 ■ |
- |
|
|
Рис. 1.12. Аппроксимация на отрезке [-1,1] функции /(* ) = |х|
полиномами Ньютона (Лагранжа) Рп(х), построенными с использованием чебышёвских сеток
0,001 -I------------ |
1------------ |
1------------ |
1------------ |
1------------ |
1------------ |
1---------- |
|
0 |
10 |
20 |
30 |
40 |
50 |
60 |
n |
Рис. 1.13. Погрешность аппроксимации 6„ функции /(*)= |x|
полиномами Ньютона (Лагранжа) Рп(х) на отрезке [-1,1] в зависимости от номера п при использовании чебышёвских сеток
Аналогично строятся аппроксимации на сетках, содержащих 3, 9, 17, 33 и 65 узлов1. Вид соответствующих функций приведен на рис. 1.12.
На рис. 1.13 показана зависимость погрешности аппроксимации полино мами Рп(х) заданной функции /(х ) = |х| на последовательности чебышёвских
сеток.
Выводы
1.Разработана вычислительная программа для аппроксимации заданной функции полиномом Ньютона на указанном отрезке с использованием равно мерных сеток.
2.С помощью этой программы исследована сходимость последователь
ности полиномов Ньютона, аппроксимирующих заданную функцию на сетках с 3, 5, 9, 17, 33 и 65 узлами. Показано, что для заданной функции последователь ность полиномов Ньютона на равномерных сетках расходится.
3.Разработана вычислительная программа для аппроксимации заданной функции полиномом Ньютона на указанном отрезке с использованием чебы шёвских сеток.
4.С помощью этой программы исследована сходимость последователь
ности полиномов Ньютона, аппроксимирующих заданную функцию на сетках с 3, 5, 9, 17, 33 и 65 узлами. Показано, что для данной функции последователь ность полиномов Ньютона на чебышёвских сетках сходится.
1Рекомендуется выполнять вычисления с использованием «двойной точности».
Погрешность аппроксимации можно уменьшить, если использовать в ка честве узловых точек корни полинома Чебышева степени п:
b + а Ъ -а |
2/ +1 |
. — |
-cos |
7 Г , |
7= О,п. |
|
2(л + 1) |
|
Выполнение расчетов
Пусть на отрезке [-1,1] построена равномерная сетка, содержащая 5 узлов. Воспользуемся аналитической зависимостью /(* )= |х| для табличного задания
значений функции. Узловые координаты и соответствующие им значения при ведены в табл. 1.9. Полином Лагранжа, аппроксимирующий функцию /(х ) = |х|, заданную таблично на отрезке [-1, 1] с помощью равномерной сетки,
содержащей 5 узлов, имеет вид
Л (х) *(* + 0.5)(*-0,5)(х-1) х(х +l)(x - 0,5)(х - 1)
x(x + l)(x + 0,5)(x-l) |
|
х(х +l)(x + 0,5)(х - 0,5) |
0,75 |
+ |
1,5 |
Аналогичным образом строятся аппроксимации на сетках, содержащих 3, 9, 17, 33 и 65 узлов. Вид соответствующих функций приведен на рис. 1.10. На рис. 1.11 показана зависимость погрешности аппроксимации полиномами Рп(х) заданной функции /(* ) = \х\ на равномерных сетках,
б»= 1ИХ*)- /М П = n jax p .M - f{x )\.
Для повышения точности аппроксимации функции полиномом Ньютона воспользуемся чебышёвской сеткой на отрезке [-1,1]:
(2/' + 1)я . —
Полином Лагранжа, аппроксимирующий таблично заданную функцию на том же отрезке с помощью чебышёвской сетки, содержащей 5 узлов, имеет вид
р / ч х(х + 0,5878)(х-0,5878)(х-0,9511) х(х+0,951 l)(x- 0,5878)(х-0,9511)
1,0635 |
|
0,6573 |
х(х + 0,951 l)(x + 0,5878)(x-0,951l) |
|
х(х+0,951 l)(x + 0,5878)(х - 0,5878) |
0,6573 |
+ |
1,0635 |
Аналогично строятся полиномы Лагранжа на чебышёвских сетках, содер жащих 3, 9, 17, 33 и 65 узлов. Вид соответствующих полиномов приведен на рис. 1.12. На рис. 1.13 показана зависимость погрешности аппроксимации
Пусть отыскиваемое приближение Рт(х) зависит от известного числа т + 1 параметров а0,аи ...,ат. Отклонение функции / ( х) от ее приближения Р„(х)
определяется соотношением
\ \ f - p j 2 = ||/|Г - 2 (/,^ )+ « ^ 1 Г = 1 /* 2 - 2 Х / л |
( * > 2 ^ ) . |
|||||
|
|
|
*=0 |
А=0 |
|
*=о |
Для определения |
наименьшего |
отклонения |
| | / - / 5J | используются |
|||
необходимые условия минимума функции нескольких переменных: |
||||||
да0 |
м |
дао |
м |
|
|
аао |
^ u - pj |
2=-2i ^ |
^ ^ |
+2i |
p^ |
^ |
r ^ =0- |
да. |
|
|
|
|
|
|
j - V - P . t » - 2 Ё Л ^ * 2 2 Л ( х , ) ^ - 0 . |
||||||
дат |
ыо |
|
*=о |
|
|
|
|
п\ |
|
|
|
|
|
С учетом того, что |
7^(х)= ^ , архР > условие минимальности ||/~ -/>/п|| за- |
|||||
|
р=о |
|
|
|
|
|
писывается в виде системы линейных алгебраических уравнений относительно коэффициентов ар, р = 0, т :
fа 0 Т \ + а $ \ х к + < h ’E |
x l + - |
• + в - 2 * г = 2 л . |
|||
*=0 |
k=Q |
к=0 |
|
*=0 |
А=0 |
пП
< *о2**+ а| 2 |
дГ* + а2 2 х*+ •..+ *т2 > г ' = |
2 / л , |
|||
0 |
к=0 |
*=о |
*=0 |
|
*=0 |
п |
п |
п |
л |
|
п |
а о У л |
+ Д1 Л ;Г + « 22 < +2+- |
+ ^ 2 |
^ |
= 2 / * |
|
А«0 |
*=0 |
*=0 |
*=0 |
|
*=0 |
Выполнение расчетов
Воспользуемся аналитической зависимостью /(х ) = |х| для табличного за
дания функции, например, в 101 узле равномерной сетки на отрезке [-1,1].
|
|
|
|
|
|
Таблица 1.11 |
|
|
Коэффициенты матрицы by и правая частьf системы линейных |
||||||
|
алгебраических уравнений метода наименьших квадратов (т = 4) |
||||||
|
|
./= 1 |
2 |
3 |
4 |
5 |
/ |
/= |
1 |
101,0 |
0,0 |
34,34 |
0,0 |
21,01333 |
51,0 |
2 |
|
0,0 |
34,34 |
0,0 |
21,01333 |
0,0 |
0,0 |
3 |
|
34,34 |
0,0 |
21,01333 |
0,0 |
15,30571 |
26,01 |
4 |
|
0,0 |
21,01333 |
0,0 |
15,30571 |
0,0 |
0,0 |
5 |
|
21,01333 |
0,0 |
15,30571 |
0,0 |
12,13777 |
17,68333 |
Рассмотрим построение полинома ЛОО, то есть т = 4. В табл. 1.11 приве дена матрица коэффициентов и правая часть системы уравнений метода наи меньших квадратов.
Рис. 1.14. Аппроксимация на отрезке [-1, 1] функции /(* ) = \х\
полиномами Р„(х), построенными с использованием метода наименьших квадратов
Рис. 1.15. Погрешность аппроксимации 5„ функции /(х ) = |х|
полиномами Рп(х) на отрезке [-1,1] при использовании метода наименьших квадратов
Решение этой системы уравнений методом Гаусса позволило построить полином, аппроксимирующий на отрезке [-1, 1] функцию /(х)=|*|, заданную
таблично с помощью равномерной сетки, содержащей 101 узел:
Р4(х) = 0,1182 + 1,6257х2 - 0,7977х4
Аналогичным образом строятся полиномы Р2(х\ Pg(x), Р,6(х), Рп(х) и Ры(х). Вид этих функций приведен на рис. 1.14. На рис. 1.15 показана зависи мость погрешности аппроксимации полиномами Рп(х) функции f{ x )= |JC| :
= И .М - /М 1 = ^ а х ]|/}„(х )-/(х )|.
Выводы
1.Разработана программа для аппроксимации заданной функции поли номами на указанном отрезке с использованием метода наименьших квадратов.
2.С помощью этой программы исследована последовательность полино мов Р2(х), Р4(х), Р%{х\ Р\ь(х\ Ръг{х) и Р ьа(х ), аппроксимирующих заданную функцию. Для заданной функции последовательность полиномов сходится.
1.3.4, Наилучшее приближение в гильбертовом пространстве
Задание. Для функции /(х ) = |х| на отрезке [-1, 1] построить наилучшее
приближение в гшьбертовом пространстве с использованием полиномов. Ис следовать сходимость последовательности полиномов.
Алгоритм решения
Рассмотрим линейное нормированное пространство Я, в котором задана конечная система линейно-независимых элементов ср* е Я , к = 0,п. Требует ся заменить элемент / е Я линейной комбинацией
п |
|
Ф = а0ф0 + О1Ф1 + • • • + оиФя = |
|
*=0 |
|
Пусть в Я норма порождена скалярным произведением |
|
ь |
ь |
(j,g )n = J/M sM d * . II/IL = (/- /)« |
= j f 2(x)dx |
а |
а |
Рассмотрим отклонение приближения (р от элемента/ ,
- решение системы уравнений B a = f ;
п
- построение ср = ^ а к(рк .
к=о
Выполнение расчетов
Выполнение расчетов рассматривается на примере построения полинома Р4{х). В качестве системы линейно-независимых функций выбираются полино мы (р*(х) = х к, к = 0, п. В соответствии с приведенными соотношениями вычис ляются коэффициенты btj иf системы линейных алгебраических уравнений:
1
**=(ф*.ф,)я = Jx*x'dr = £ + р + 1
Л = (А Ф* )н = |
= - fx k"dx + Jr*+,dx = |
|
* + 2 |
Значения подсчитанных коэффициентов приведены в табл. 1.12.
Рис. 1.16. Полиномы наилучшего приближения функции /(х)=|х| полиномами Рп(х) на отрезке [-1, 1 ]
Решение этой системы уравнений методом Гаусса позволило построить полином Р4(х) (рис. 1.16), аппроксимирующий на отрезке [-1, 1] функцию
/ М = Н :
/>4 (ж) = 0,1172 + 1,6406.x2 - 0,8203х4
Таблица 1.12
Коэффициенты матрицы btj и правая частьf системы линейных алгебраи ческих уравнений Ва = /п ри построении наилучшего приближения
/ = 1 |
j - 1 |
2 |
3 |
4 |
5 |
f |
2,0 |
0,0 |
0,6667 |
0,0 |
0,4 |
1,0 |
|
2 |
0,0 |
0,6667 |
0,0 |
0,4 |
0,0 |
0,0 |
3 |
0,6667 |
0,0 |
0,4 |
0,0 |
0,2857 |
0,5 |
4 |
0,0 |
0,4 |
0,0 |
0,2857 |
0,0 |
0,0 |
5 |
0,4 |
0,0 |
0,2857 |
0,0 |
0,2222 |
0,3333 |
Рис. 1.17. Погрешность 5„ аппроксимации функции У*(х)= |х|
полиномами Р„(х) наилучшего приближения на отрезке [-1,1]
Аналогичным образом строятся полиномы Рг(*\ Ръ(*\ Р\ь(*) и так далееВид этих функций приведен на рис. 1.16. На рис. 1.17 показана зависимости погрешности аппроксимации функции /(* )= |х| полиномами Рп(х\
8. = ||^ (* )-/(* )|| = |
/(* )|- |
Выводы
1. Разработана программа для наилучшего приближения в гильбертовой пространстве заданной функции /(* )= |х| полиномами Рп(х) на отрезке [-1,1].
2. С помощью этой программы исследована последовательность полиномов Рг(х\ Ра(х), PS(X), Р^С*), Рп(х) и Рб4(*) наилучшего приближения заданно# функции. Показано, что для заданной функции последовательность построен ных полиномов сходится.