А.А. Самарский, П.Н. Вабищевич, Е.А. Самарская - Задачи и упражнения по численным методам (2000) (1160081), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Более перспективнымиявляются подходы с использованием кусочно-гладких полиномов.Отдельно выделены задачи приближения функций в нормирован­ных пространствах.1.1. Задачи интерполяции и приближения функцийЗадача интерполяции ставится следующим образом. Пусть на отрезке[а,Ь] в узлах интерполирования х0 < х\ < ... < х„ известны значенияфункции у, = /(х,), г = 0 , 1 , . . . , п. Необходимо найти значения функцииf(x) в точках х ф х,, г = О, I,. . , п.Пусть на отрезке [о,Ь] задана система функций {^i(a;)}"=o и опреде­лимп<P(x) = '^2ctf,(x)(1.1).=0с действительными коэффициентами с,,г = 0 , 1 , .

. . , га. При интерполи­ровании функции /(х) для нахождения коэффициентов используютсяусловия¥>(*,) = / ( * i ) ,г = 0,1, . . , п .(1.2)xВ частном случае алгебраической интерполяции <pt( ) = x',i =Q,l,...,n.1.1. Задачи интерполяции и приближения функций9Основные обозначения/(х) — интерполируемая функциях0 < Х\ < ... <х„ — узлы интерполирования{y>,(i)}"=0 — система Чебышеваtp(x) — обобщенныйинтерполяционный многочленL„(x) — интерполяционныймногочлен п-го порядкаf(x„xt+l) — разделенная разность первогопорядка/(ж,-,х, + 1,... ,х, + *) — разделенная разность fc-roпорядкаSm(x) — интерполяционный сплайн т - г опорядкаПри интерполяции сплайнами функция f(x) приближается мно­гочленами невысокой степени на частичных отрезках [х,,ж 1+] ], гдеt = 0 , 1 , .

. . , п — 1.Рассматривается также задача построения обобщенного многочле­на <р(х), приближающего заданную функцию f(x). В линейном норми­рованном пространстве коэффициенты обобщенного многочлена tp(x)определяются из условия минимальности нормы пофешности интерпо­лирования:п/ (х) -]Гс<Мх) •(1-3):=0Аналогично ставятся задачи интерполяции и приближения много­мерных функций.Глава 1. Интерполирование и приближение функций101.2. Алгоритмы интерполяциии приближения функцийДля одномерных функций задачи интерполяции решаются с использова­нием алгебраических многочленов Лагранжа и Ньютона, параболическихи кубических сплайнов, рассмотрена задача наилучшего приближенияв гильбертовом пространстве.1.2.1. Полиномиальная интерполяцияПри аппроксимации полиномами используются функции<Pi(x)=x', i = 0,l,...,nи интерполяционный многочлен (см.

(1.1)) имеет видip(x) = Ln(x) = y^Cix'.i=0Интерполяционный многочлен Лагранжа записывается в виде^(х) —= ]J{X- Xi), степени п + 1:где ш(х)многочленi=0ш (х) = — (х).ахМожно использовать другую запись интерполяционного многочленав виде интерполяционного многочлена Ньютона, которая строится с по­мощью разделенных разностей. Разделенной разностью первого порядканазывается отношение1.2. Алгоритмы интерполяции и приближения функцийf{xx.11v _ /(».-+•) - /(»<)Разделенная разность «-го порядка определяется по рекуррентной фор­муле.,v _ f(Xi+\,Xi+2,...,Xi+k)Д Х , ' , Х 1 + | , . . .

,X{+k) —Xj+Jfc — xif(Xj,Xi+U...,Xi+k-l).С использованием таких обозначений получим[Ln(x)] = / (х0) + (х - х0) / (х 0) х,) ++ (x-xo)(x-xi)/(xo,Xi,x 2 ) + -.- ++ (х - х0) (х - х,) • • • (х - хп_,) f (х0, х ь . . . , х „ ) .(1.5)1.2.2. Интерполяционные сплайныПусть функция f(x) задана в узлах а = х0 < Х\ < ... < хп = 6.Интерполяционный сплайн Sm(x) порядкатоопределяется из условий:1. на каждом отрезке [x;,xj+1],i = 0,1,...

,п - 1 Sm(x) является поли­номом степени то;2. на всем отрезке [a, b] Sm(x) имеет непрерывные производные до по­рядкато— 1;3. в узлах интерполяции5 т (х.) =/(х,),г = 0,1,..., п.Прито> 2 единственность 5 т (х) обеспечиваетсято- 1 дополнитель­ными условиями. Обычно эти условия формулируются на концах отрезкаинтерполяции [о, Ь].Интерполяционный кубический сплайн 5з(х) на отрезке [х,,х,+|]задается полиномом третьей степени:Sf = а, + Ь,(х - х.) + у(х - х,)2 + j(x - Xi)\х{^х^х{+1,г = 0, l,...,n - 1,(1.6)Глава 1.

Интерполирование и приближение функций12причем(ОdSЪ, =-^(х,),а, = S**^,),d2S«С ='^-d3S<'>(Х,)'d ='4x^(x^По определению для Бз(х) выполнены условия:S(it)(xt) = f(xt),i = 0,l,...,n-l,,)Si (x,+ 1) =/(х, + 1 ),dS?,dxi = 0,l,...,n-l,. dS{,+l)(x,+\) = —-j— (x.+i),i = 0,l,...,n-2,Два дополнительных условия можно взять в виде (естественные кубиче­ские сплайны)d2s^d2stl)-£-(*>) = о, -±г-Ы = о.1.2.3. Приближение функций в нормированном пространствеПусть Н — вещественное гильбертово пространство со скалярным про­изведением (f,g) и нормой ||/|| = л / ( / , / ) .

В случае Н = Li(a,b) имеемьъ(/,«?) = J f(x)g(x)dx,(J\f(x)\2dx?/2.ll/ll =ааВ задаче о наилучшем приближении по системе функций<Р,(Х)ЕН,i = o,i,...,nстроится обобщенный многочлен (1.1) (элемент наилучшего приближе­ния), который для заданной приближаемой функции f(x) G Я миними­зирует норму отклонения (1.3).1.3.

Упражнения13Коэффициенты элемента наилучшего приближения находятся из ре­шения следующей системы линейных уравнений:^2CJ(VUVJ)= (/>¥>.),» = 0,1,...,п.(1.7);=01.3. УпражненияРассмотрены примеры решения некоторых проблем теории интерполяциии приближения функций.Упражнение 1.1. Покажите однозначную разрешимость задачи интерполя­ции алгебраическими многочленами.Решение. Для определения коэффициентов с,,г = 0 , 1 , . .

. , п получимсистему линейных алгебраических уравненийJ^Cjxf = / ( * , ) ,(1.8)» = 0 , 1 , . . . , п.Определитель этой системы есть определитель Вандермонда:W(xQ,xu...,x„)=1Ж0•••XQ1хх...х11Хп...ХпОн отличен от нуля в рассматриваемом случае несовпадающих узловинтерполяции (яо < х\ < ... < х„) и тем самым система уравнений (1.8)имеет единственное решение.Упражнение 1.2. Рассмотрите различные способы вычисления значений ин­терполяционного многочлена L„(x).Решение Для вычисления значения полиномаL„(x) = со + с}х + • • • + с„хпв одной точке требуется п(п + 1)/2 умножений и п сложений.Глава 1. Интерполирование и приближение функций14При использовании схемы Горнера полином переписывается в видеL„(x) - со + х[с{ +a;(c 2 + a;(---(cn_i+c„x)•••)))•В этом случае требуется только п умножений и п сложений.Упражнение 1.3. Получите расчетные формулы для коэффициентов есте­ственного кубического сплайна.Решение Введем обозначенияh, =xt - х,-\,t = l,2,...,n.Для кубического сплайна S3(x) с учетом представления (1.6) получимследующую систему уравнений:at = f(x,),a,+btht+]» = 0,1,...,п-1,с,d.+ -h2,+i + -hit+i1оb, + c,ft,+, + уЛ,2+| =6,+i,c, + d,ft,+1 = с , + ь0 = 0,= f(x,+i),(1.9)i = 0 , 1 , .

. . ,n - 1,i = 0,l,...,n-2,i = 0,l,...,n-2,(1.10)(1.11)(1.12)c„_ 1 +d„_ 1 ft n =0.(1.13)Формально доопределим с„ = 0, тогда из (1.12) и второго условия(1.13) получимd' = 4Z^ >« = 0,1,...,п-1,(1.14)а вместо (1.13) будем иметьсо = 0,с„ = 0.(1.15)Подстановка (1.9), (1.14) в (1.10) дает следующее представление длякоэффициентов Ь,:&i=/(*,+ , ) - / ( ^ _ W | + [ + 2 c < ) ;i = 1)2)...)n_,.(L16)1.3.

Упражнения15С учетом (1.14), (1.16) соотношения (1.11) приводят к уравнениюc,_ift, + 2с, (Л, + ftt+1) + c, + ih t+ i ==6//(«.+!)-/(».)/(*.)-/(*,-i)\(117)i = 1,2,... ,n — 1.Тем самым приходим к линейной системе уравнений (1.15), (1.17) с трехдиагональной матрицей с диагональным преобладанием. Решение этойсистемы всегда существует и единственно.Другие коэффициенты сплайна определяются в соответствии с (1.9),(1.14), (1.16).Упражнение 1.4.

Рассмотрим на отрезке [а,Ь] класс функций, имеющихсуммируемые с квадратом вторые производные, W2[a, b]. Построим интер­полирующую функциюu(x)ewl[a,b\,«(*,) = / ( * . ) ,i = 0,l,...,n,(1.18)которая минимизирует функционалJW =/(I?)*S-(1Л9)аПокажите, что такой функцией является естественный кубический сплайнS}(x) (экстремальное свойство кубического интерполирующего сплайна).Решение. Для доказательства рассмотрим величинут/«v)(&ud2s 2A.аИмеет место тождествоJ (u - S3) = J (и) - J (53) - 27,где[(d2%t - J Wd2S3\ d%_ ^ У/d2« _d2S3\ d2S322dx ) dx ** ~ % J \dx2dxi)dx2<lX-(1.20)Глава 1.

Интерполирование и приближение функций16d3S3,Принимая во внимание постоянство ——г-(ж)при х € [x,,z, + i], интегриdx1рованием по частям получимdx2 " dx2 ) dx2_ (du\dxXdSi\ d2S2dx J dx2~*•+!±?L(Xi+0)(u(x)-S3(x))Так как u(xi) = S3(xi),i = 0 , 1 , . . . ,n, тоdSj\d2S)dx J dx2_ (du\dxd2S,d2S3iДля естественного кубического сплайна -^-у(а)=-j-j-(b)= 0 и поэтомуdx2dx2/ = 0 в представлении (1.20), т.е.J(u) = J(S)) + J{u - S3).Очевидно, что J(u - Sj) ^ 0 и поэтому J(S3) < J(u), т.е. естественныйкубический сплайн Sy(x) доставляет минимум функционалу J(u).Упражнение 1.5. Установите свойство ортогональности погрешности f — <pэлементу наилучшего приближения(/-^)¥>) = 0(1.21)и получите оценку погрешности.Решение. Элемент наилучшего приближения определяется выражением¥>(x) =^2ciipi{x),i=0где коэффициенты удовлетворяют условиям (см.

(1.7))5Zc>^'Vi) = (f,<Pi)j=0171.3. Упражненияпри г — О,1,..., п. Домножим уравнение на с* и сложим по всемi = 0 , 1 , . . . , п, что даетIHI 2 = (/.*»)•о-22)Отсюда непосредственно вытекает доказываемое свойство (1.21).Из тождества11/-И12 = 11/И2-2(/,*») + 1И12с учетом (1.22) следует оценка11/-И12 = 1И12-1М12о-23)для погрешности наилучшего приближения.Упражнение 1.6. Для ортонормированной системы функций {<Pi(x)}i=Q, т. е.для функцийto" ^ - 1 1 ,<=,-,рассмотрите задачу среднеквадратичной аппроксимации.Решение. В этом случае система уравнений (1.7) упрощается и для коэф­фициентов наилучшего приближения получим<* = (Ш,i = 0 , 1 , . .

Характеристики

Список файлов книги