Д.П. Костомаров, А.П. Фаворский - Вводные лекции по численным методам (pdf) (1113729), страница 10
Текст из файла (страница 10)
Уравнение этойпрямой, наряду с (9) и (10), можно переписать в виде:f ( x1 ) − f ( x0 )y = P1 ( x ) = f ( x0 ) +(11)( x − x0 ) .x1 − x0- 45 Из данного примера видно, что всегда существуют различные эквивалентные междусобой формы записи интерполяционного полинома, удобные в различных ситуациях.1.3. Построение интерполяционного полинома в форме Лагранжа.Интерполяционный полином первой степени (9) мы построили, решая напрямуюсистему двух уравнений с двумя неизвестными - коэффициентами c0 и c1 . Однакорешить таким же образом систему (8) при произвольном n технически очень сложно.Проще сделать это с помощью специальных методов, учитывающих особенностирассматриваемой задачи.
Один из таких методов, принадлежащих Лагранжу, мы ирассмотрим в этом разделе.Представим искомый полином Pn ( x ) в виде:nPn ( x ) = ∑ f ( xi )Qn ,i ( x ) ,(12)i =0где Qn ,i ( x ) полиномы степени n , «ориентированные» на точки xi в том смысле, что⎧0, x = x j ∀j ≠ i,Qn ,i ( x ) = ⎨⎩1, x = xi .Такие полиномы легко построить:j =n(x − xj )Qn ,i ( x ) = ∏j =0 ( xi − x j )(13)(14)j ≠iили в развернутом виде:Qn ,0 ( x ) =( x − x1 )( x − x2 )K ( x − xn ),( x0 − x1 )( x0 − x2 )K ( x0 − xn )Qn ,i ( x ) =( x − x0 )K ( x − xi −1 )( x − xi +1 )K ( x − xn ),( xi − x0 )K ( xi − xi −1 )( xi − xi +1 )K ( xi − xn )( x − x0 )( x − x1 )K ( x − xn −1 ).( xn − x0 )( xn − x1 )K ( xn − xn −1 )Иногда нам будет удобно записывать Qn ,i ( x ) в виде:(15)Qn ,n ( x ) =( x − x0 )K[i ]K ( x − xn ).( xi − x0 )K[i ]K ( xi − xn )Из выражения (12) и формул (13) очевидно, что построенный полином Pn ( x )действительно является интерполяционным полиномом для функции y = f ( x ) насетке с узлами x0 , x1 ,..., xn .
Его принято называть интерполяционным полиномом вформе Лагранжа. Этим подчеркивается, что возможны и другие эквивалентныепредставления интерполяционного полинома Pn ( x ) . С одним из них мы познакомимсяв следующем разделе.В заключение отметим, что из трех различных представлений интерполяционногополинома первой степени (9)- (11) формула (10) дает его запись в форме Лагранжа.Qn ,i ( x ) =Задача 2.- 46 Написать интерполяционный полином второй степени для функции y = sin x по еезначениям в трех точках: x0 = 0 , x1 = π / 6 , x2 = π / 2 . Вычислить с помощью этогополинома приближенное значение синуса в точке x = π / 4 , сравнить полученный⎛π ⎞результат с точным значением синуса и подсчитать погрешность R2 ⎜ ⎟ .⎝4⎠Воспользуемся для записи полинома формулой Лагранжа (12).
Врассматриваемом случае y0 = sin x0 = 0 , так что в формуле останется только дваслагаемых соответствующих точкам x1 и x2 . В результате получим:π⎞π⎞⎛⎛x⎜ x − ⎟ x⎜ x − ⎟1 ⎝2⎠6 ⎠ x ⎛ 7π⎞(16)+ ⎝= 2⎜− 3x ⎟P2 ( x ) =π ⎛π ⎞π ⎝ 22 π⎛ π⎞⎠⎜− ⎟⎜ ⎟6⎝ 3⎠2⎝ 3⎠Перейдем к выполнению второй части задания. Вычислим с помощьюинтерполяционного полинома (16) приближенное значения синуса в точке x = π / 4 иподсчитаем погрешность:⎛ π ⎞ 11⎛ π ⎞ 1 11P2 ⎜ ⎟ = , R2 ⎜ ⎟ =− = 0.0197 < 0.02 .(17)4164162⎝ ⎠⎝ ⎠На рис. 1 приведены для сравнения графики функций sin x (сплошная линия) и P2 ( x )(пунктир).1.4.
Интерполяционный полином в форме Ньютона.Интерполяционный полином в форме Лагранжа, несмотря на своё изящество,неудобен для вычислений тем, что при увеличении числа узлов интерполяцииприходится перестраивать весь полином заново.Перепишем интерполяционный полином Лагранжа в иной, эквивалентной формеnPn ( x ) = P0 ( x ) + ∑ ( Pi ( x ) − Pi −1 ( x )) ,i =1(18)где Pi ( x ) - полиномы Лагранжа степени i ≤ n , соответствующие узламинтерполирования x0 , x1 ,K xi . В частности, P0 ( x ) = f ( x0 ) - полином нулевой степени.Полином(19)Qi ( x ) = Pi ( x ) − Pi −1 ( x )имеет степень i и по построению обращается в ноль при x = x0 , x = x1 ,K x = xi −1 ,поэтому его можно представить в виде(20)Qi ( x ) = Ai ( x − x0 )( x − x1 )K ( x − xi −1 ) ,где Ai - числовой коэффициент при x i .
Поскольку Pi −1 ( x ) не содержит степени i , тоAi просто совпадает с коэффициентом при x i в полиноме Pi ( x ) . Согласно (12) и (15)его можно записать в видеif ( xk )Ai = ∑,(21)k =0ω k ,i- 47 гдеω k ,i = ( xk − x0 )K ( xk − xk −1 )( xk − xk +1 )K ( xk − xi ) .(22)При этом(23)A0 = f ( x0 ) .Формулы (19) и (21) позволяют написать рекуррентное соотношение для полиномаPn ( x ) :(24)Pn ( x ) = Pn −1 ( x ) + An ( x − x0 )K ( x − xn −1 ) .Выражая аналогичным образом по индукции Pn −1 ( x ) через Pn −2 ( x ) , Pn −2 ( x ) черезPn −3 ( x ) и т. д., получим окончательную формулу для полинома Pn ( x ) :Pn ( x ) = A0 + A1 ( x − x0 ) + A2 ( x − x0 ) ( x − x1 ) + K(25)+ Ai ( x − x0 )K ( x − xi −1 ) + K + An ( x − x0 )K ( x − xn−1 ) .Представление (25) удобно для вычислителя, поскольку увеличение n на единицутребует только добавления к «старому» многочлену одного дополнительногослагаемого.
Такое представление интерполяционного полинома Pn ( x ) называютинтерполяционным полиномом в форме Ньютона.Из трех эквивалентных представлений интерполяционного полинома первойстепени (9) - (11) формула (11) дает его запись в форме Ньютона.Задача 3.Написать интерполяционный полином второй степени в форме Ньютона дляфункции y = sin x по ее значениям в трех точках: x0 = 0 , x1 = π / 6 , x2 = π / 2 (см.задачу 2).Согласно формуле (25)π⎞⎛P2 ( x ) = A0 + A1 x + A2 x ⎜ x − ⎟ .(26)6⎠⎝Коэффициенты в этом разложении вычисляются по формулам (21) и(23):18631⎛ 6⎞(27)A0 = 0 , A1 = ⎜ ⎟ , A2 = − 2 + 2 = − 2 .2πππ2 ⎝π ⎠Подставляя найденные значения коэффициентов в формулу (26), получим33x ⎛π ⎞ x ⎛ 7π⎞P2 ( x ) = x − 2 ⎜ x − ⎟ = 2 ⎜− 3x ⎟ .(28)ππ ⎝6⎠ π ⎝ 2⎠Первоначальные выражения для интерполяционного полинома в форме Лагранжа иНьютона различны, но окончательные ответы, естественно, совпадают.1.5. Погрешность интерполирования.Поставим вопрос о том, насколько хорошо интерполяционный полином Pn ( x )приближает функцию f ( x ) на отрезке [ a , b ] , то есть попытаемся оценить погрешность(остаточный член)(29)Rn ( x ) = f ( x ) − Pn ( x ) , x ∈ [ a , b ] .- 48 Сразу же отметим, что по определению интерполяционного полинома(30)Rn ( xi ) = 0 при i = 0,1,K , n ,поэтому речь идет об оценке Rn ( x ) при значениях x ≠ xi .Для того, чтобы это сделать, следует ввести дополнительно предположение огладкости функции f ( x ) .
Предположим, что f ( x ) имеет ( n + 1) непрерывнуюпроизводную на отрезке [ a , b ] .В силу (30) Rn ( x ) можно представить в виде:(31)Rn ( x ) = ω n +1 ( x ) rn ( x ) ,где ω n +1 ( x ) - полином степени ( n + 1) :(32)ω n +1 ( x ) = ( x − x0 )( x − x1 )K ( x − xn ) .Зафиксируем произвольное значение x ∈ [ a , b ] и рассмотрим вспомогательнуюфункцию от переменной t :g (t ) = f ( t ) − Pn ( t ) − ω n +1 (t ) rn ( x ) ,заданную на отрезке [ a , b ] и содержащую переменную x в качестве параметра. В силусвоего определения функция g (t ) обязана обращаться в нуль в узлахинтерполирования при t = xi и кроме того при t = x , т. е. как функция аргумента t онаимеет ( n + 2 ) нуля:(33)g ( xi ) = 0 , i = 0,1,K , n , g ( x ) = 0 .Если x ∈ [ x0 , xn ] , то все ее нули также лежат на отрезке [ x0 , xn ] .
Если x < x0 , то этинули, вообще говоря, принадлежат отрезку [ x , xn ] , а если x > xn , то они находятся наотрезке [ x0 , x ] . Объединяя эти три случая, скажем, что указанные нули функции g (t )принадлежат отрезку [α , β ] , где α = min( x0 , x ) ≥ a , β = max( xn , x ) ≤ b .Согласно известной теореме Ролля можно утверждать, что производная g ′(t ) имеетпо крайней мере ( n + 1) нуль на отрезке [α , β ] (эти нули перемежаются с нулямисамой функции g (t ) ).
Повторяя это рассуждение, заключаем, что g ′′(t ) имеет покрайней мере n нулей на отрезке [α , β ] , g ′′′(t ) - ( n − 1) нуль и, наконец, g ( n +1) (t )обращается хотя бы один раз в нуль в некоторой точке t = ξ ∈ [α , β ] , то естьg ( n +1) (ξ ) = f ( n +1) (ξ ) − Pn( n +1) (ξ ) − ( n + 1)! rn ( x ) = 0 .Учитывая, что ( n + 1) производная полинома степени n тождественно равна нулю,получаем, чтоf ( n +1) (ξ )rn ( x ) =; ξ ∈ [α , β ](34)( n + 1)!и соответственноf ( n+1) (ξ )ω n+1 ( x ) .Rn ( x ) =(35)( n + 1)!Формула (35) не позволяет вычислить погрешность, поскольку точное значениеаргумента ξ нам неизвестно.
Однако с ее помощью погрешность можно оценить:- 49 -Rn ( x ) ≤M n +1ω n+1 ( x ) ,(n + 1)!(36)гдеM n +1 = max f ( n +1) ( x ) ≤ max f ( n+1) ( x ) .x∈[α , β ]x∈[ a ,b](37)Обсудим роль полинома ω n +1 ( x ) (32) в оценке (36). На отрезке [ x0 , xn ] он имеет( n + 1) нуль, а его значения между этими нулями сравнительно невелики, но, когдаточка x выходит за пределы отрезка [ x0 , xn ] и удаляется от точки x0 влево или отточки xn вправо, оценка (36) ухудшается из-за быстрого роста функции ω n +1 ( x ) .
Этохорошо видно на рис. 2, где в качестве примера приведен график функции ω 4 ( x ) скорнями x0 = −3/ 2 , x1 = −1/ 2 , x2 = 1/ 2 , x3 = 3 / 2 :9 ⎞⎛1⎞⎛ω4 ( x ) = ⎜ x 2 − ⎟ ⎜ x 2 − ⎟ .4 ⎠⎝4⎠⎝⎡ 3 3⎤Ее наибольшее по модулю значение на отрезке ⎢ − , ⎥ равно единице. Однако уже в⎣ 2 2⎦точках x = ±2 за пределами отрезка полином ω 4 ( x ) принимает значение105ω4 ( ±2) == 6.5625 .16Из сказанного можно сделать следующий вывод. Если x ∈ [ x0 , xn ] , то множительω n +1 ( x ) не обесценивает оценку (36). Такой случай называют собственноинтерполяцией f ( x ) . Противоположный случай, когда точка x лежит вне отрезканазывают экстраполяцией функции f ( x ) . Отмеченная выше особенность поведенияполинома ω n +1 ( x ) резко ухудшает оценку (36) при экстраполяции. Поэтому на практикеэкстраполяции избегают или ограничиваются многочленами невысокой степени( n = 1, 2 ) , когда рост функции ω n+1 ( x ) не настолько критичен.Задача 4.Написать мажорантную оценку для погрешности (36) при вычисленииприближенного значения sin x в точке x = π / 4 с помощью интерполяционногополинома второй степени P2 ( x ) (16).