1611688890-f641c9ec8276824e4686da772eb56520 (826652), страница 11

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

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

. , xi+k+1 )=f ∠ (xi+1 , xi+2 , . . . , xi+k+1 ) − f ∠ (xi , xi+1 , . . . , xi+k )xi+k+1 − xiпо определению разделённой разности=1xi+k+1·− xi i+k+1Xj=i+1f (xj )i+k+1Ql=i+1l6=j(xj − xl )−i+kXj=if (xj )i+kQl=il6=j(xj − xl ) согласно индукционному предположению602. Численные методы анализа=(xi+k+1f (xi+k+1 )i+kQ(xi+k+1 − xl )− xi )l=i+1i+kXf (xj )−i+k+1+·Qxi+k+1 − xi  j=i+1(xj − xl )1−l=i+1l6=ji+kXf (xj )j=i+1i+kQl=il6=j(xj − xl ) f (xi )i+kQ(xi − xl )(xi+k+1 − xi )l=i+1после выведения из-под скобок последнего слагаемого первой суммыи первого слагаемого второй суммы.

В полученное выражение членыс f (xi+k+1 ) и f (xi ) — первый и последний — входят по одному разу,причём их коэффициенты уже имеют тот вид, который утверждаетсяв Предложении. Члены с остальными f (xj ) входят дважды (они стоятв больших круглых скобках), но после приведения подобных коэффициент при f (xj ) будет равен11 i+k+1− i+kYY·xi+k+1 − xi (xj − xl )(xj − xl )1l=i+1l6=j=l=il6=j(xj − xi ) − (xj − xi+k+1 )1,= i+k+1i+k+1YY(xj − xl )(xj − xl )(xi+k+1 − xi )l=il6=jчто и требовалось показать.l=il6=jСледствие. Разделённая разность как функция узлов x0 , x1 , . . .

, xk— симметричная функция своих аргументов. Иными словами, она неизменяется при любой их перестановке. Это непосредственно следуетиз симметричного вида выражения, стоящего в правой части (2.19).2.2. Интерполирование функций61Для фиксированного набора узлов численные значения разделённых разностей любой функции нетрудно вычислить согласно определениям (2.15)–(2.16) или по формуле (2.19). Но сложность выражений для разделённых разностей как функций узлов в общем случаебыстро возрастает с ростом порядка разделённой разности. Тем не менее, в случае алгебраических полиномов выражения для разделённыхразностей относительно просто получаются из выражений для исходной функции.

Вспомним известную формулу элементарной алгебрыxn − y n = (x − y)(xn−1 + xn−2 y + · · · + xy n−2 + y n−1 ), из которой следует,чтоxn − y n= xn−1 + xn−2 y + · · · + xy n−2 + y n−1 .(2.20)x−yЭтот результат позволяет явно выписать разделённую разность длялюбой целой степени переменной. Далее для произвольного полиномаможно воспользоваться свойством линейности разделённой разности(2.18).Пример 2.2.1 Вычислим разделённые разности от полинома g(x) =x3 − 4x + 1.Будем искать по отдельности разделённые разности от мономов,образующих g(x). В силу (2.20) имеемx32 − x31= x22 + x2 x1 + x21 .x2 − x1Для линейного монома (−4x) разделённая разность находится тривиально и равна (−4), а для константы 1 она равна нулю. Следовательно,в целомg ∠ (x1 , x2 ) = x22 + x2 x1 + x21 − 4.Вычислим вторую разделённую разность от g(x):g ∠ (x1 , x2 , x3 ) ===g ∠ (x2 , x3 ) − g ∠ (x1 , x2 )x3 − x1(x23 + x3 x2 + x22 − 4) − (x22 + x2 x1 + x21 − 4)x3 − x1x23 + (x3 − x1 )x2 − x21= x1 + x2 + x3 .x3 − x1622.

Численные методы анализаТретья разделённая разностьg ∠ (x1 , x2 , x3 , x4 ) =g ∠ (x2 , x3 , x4 ) − g ∠ (x1 , x2 , x3 )x4 − x1(x2 + x3 + x4 ) − (x1 + x2 + x3 )x4 − x1x4 − x1= 1,=x4 − x1=т. е. является постоянной. Четвёртая и последующие разделённые разности от g(x) будут, очевидно, тождественно нулевыми функциями. Как видим, взятие разделённой разности от полинома уменьшаетего степень на единицу, так что разделённые разности порядка более nот полинома степени n равны нулю. Это следует в общем случае из формулы (2.20) Сделанное наблюдение демонстрирует глубокую аналогиюмежду разделёнными разностями и производными: каждое применение дифференцирования к полиному также последовательно уменьшает его степень на единицу.

В действительности, эта связь видна дажеиз определения разделённой разности первого порядка, которую можно рассматривать как «неполную производную», поскольку у неё отсутствует предельный переход одного аргумента к другому.Предложение 2.2.2 (связь разделённых разностей с производными)Пусть f ∈ Cn [a, b], т. е. функция f непрерывно дифференцируема nраз на интервале [a, b], где расположены узлы x0 , x1 , . .

. , xn , и пустьx = min{x0 , x1 , . . . , xn }, x = max{x0 , x1 , . . . , xn }. Тогдаf ∠ (x0 , x1 , . . . , xn ) =1 (n)f (ξ)n!(2.21)для некоторой точки ξ ∈ ] x, x [.Для разделённых разностей первого порядка этот факт непосредственно следует из теоремы Лагранжа о среднем (формулы конечныхприращений), согласно которойf (xi+1 ) − f (xi ) = f ′ (ξ) · (xi+1 − xi )для некоторой точки ξ ∈ ] xi , xi+1 [ . Для общего случая доказательствоПредложения 2.2.2 будет приведено несколько позже, в §2.2д.632.2.

Интерполирование функцийСуществует более точное (хотя и более громоздкое) интегральноепредставление для разделённых разностей, о котором можно подробноузнать в [20, 56, 69].2.2гИнтерполяционный полином НьютонаВыведем теперь другую форму интерполяционного полинома с учётом требования иметь такое выражение, которое в минимальной степени перестраивалось бы при смене набора узлов интерполяции.Обозначим через Pk (x) интерполяционный полином степени k, построенный по узлам x0 , x1 , . . . , xk . В частности, P0 (x) = f (x0 ), имеянулевую степень и будучи построенным по одному узлу x0 .

Тогда очевидно следующее тождествоPn (x) = P0 (x) +nXk=1Pk (x) − Pk−1 (x) .(2.22)Замечательность этого представления состоит в том, что при добавлении или удалении последних по номеру узлов интерполяции перестройке должны подвергнуться лишь те последние слагаемые суммыиз правой части (2.22), которые вовлекает эти изменяемые узлы. Первые слагаемые в (2.22) зависят только от первых узлов интерполяциии останутся неизменными.

Таким образом, стоящая перед нами задачаокажется решённой, если будут найдены удобные и просто выписываемые выражения для разностей Pk (x) − Pk−1 (x).Заметим, что разность Pk (x) − Pk−1 (x) есть полином степени k,который обращается в нуль в узлах x0 , x1 , . . . , xk−1 , общих для Pk (x)и Pk−1 (x), где эти полиномы должны принимать одинаковые значенияf (x0 ), f (x1 ), . . . , f (xk−1 ).

Поэтому должно бытьPk (x) − Pk−1 (x) = Ak (x − x0 )(x − x1 ) · · · (x − xk−1 )с некоторой константой Ak . Для её определения вспомним, что по условию интерполяции Pk (xk ) = yk . Следовательно,Ak =yk − Pk−1 (xk ).(xk − x0 )(xk − x1 ) · · · (xk − xk−1 )Отсюда, подставляя вместо Pk−1 (x) выражение для интерполяционно-642. Численные методы анализаго полинома в форме Лагранжа, нетрудно вывести, чтоk−1Q(xk − xl ) k−1l=0X1l6=jAk = k−1yj k−1· yk −QQj=0(xj − xl ) (xk − xl )l=0l=0l6=jk−1Q(xk − xl ) l=01l6=j= k−1−yj k−1 k−1QQQj=0(xj − xl ) (xk − xl )(xk − xl )k−1Xykl=0=ykk−1Ql=0=ykkQl=0l6=k=(xk − xl )−+(xk − xl )kXj=0yjkQk−1Xj=0k−1Xj=0l=0l=0l6=j(xk − xj )yjk−1Q(xj − xk )yjk−1Ql=0l6=jl=0l6=j(xj − xl )после сокращенияпроизведений(xj − xl )= (y0 , y1 , .

. . , yk )∠(xj − xl )l=0l6=jв силу представления, доказанного в Предложении 2.2.1. ОкончательноPn (x) =y0 + (y0 , y1 )∠ (x − x0 ) + (y0 , y1 , y2 )∠ (x − x0 )(x − x1 ) +. . . + (y0 , y1 , y2 , . . . , yn )∠ (x − x0 )(x − x1 ) · · · (x − xn−1 ).Выражение в правой части этого равенства называется интерполя-652.2. Интерполирование функцийционным полиномом в форме Ньютона, или просто интерполяционным полиномом Ньютона.

Оно является равносильной формой записиинтерполяционного полинома, широко применяемой в ситуациях, гдеиспользование формы Лагранжа по тем или иным причинам оказывается неудобным. Полезно иметь в виду следующее представление5Pn (x) = Pk (x) + (y0 , y1 , . . . , yk+1 )∠ (x − x0 ) · · · (x − xk )(2.23)+ . . . + (y0 , y1 , . .

. , yn )∠ (x − x0 ) · · · (x − xn−1 ),справедливое для любого k, такого что 0 ≤ k ≤ n − 1.Пусть f — вещественная n-гладкая функция. С учётом результатаПредложения 2.2.2, т. е. равенстваf ∠ (x0 , x1 , . . . , xn ) =1 (n)f (ξ),n!хорошо видно, что интерполяционный полином Ньютона для гладкойфункции непрерывного аргумента является прямым аналогом полинома Тейлора (формулы Тейлора)f (x0 ) + f ′ (x0 )(x − x0 ) +f ′′ (x0 )f (n) (x0 )(x − x0 )2 + . . .

+(x − x0 )n .2!n!При этом аналогами степеней переменной (x − x0 )k являются произведения (x − x0 )(x − x1 ) · · · (x − xk ), которые в случае равномерно расположенных и упорядоченных по возрастанию узлов x0 , x1 , . . . , xk частоназывают обобщённой степенью [10].Практическое нахождение интерполяционного полинома Ньютонатребует знания всех разделённых разностей функции, и наиболее удобно вычислять их всё-таки по рекуррентным формулам (2.15)–(2.17).Важнейший частный случай интерполирования относится к равномерному расположению узлов, когда величина hi = xi − xi+1 постояннаи не зависит от i, т. е. hi = h = const. Тогда вычисление разделённыхразностей решительно упрощается, сводясь к оперированию с так называемыми конечными разностями. По определению конечной разностью (иногда добавляют — первого порядка) от функции f в точке xназывается величина∆y = ∆f (x) = f (x + h) − f (x).5 Образно выражаясь, оно показывает, как интерполяционные полиномы Ньютона разных степеней вложены друг в друга наподобие «матрёшек».662.

Численные методы анализаВ частности, можно считать, что ∆x = h. Конечные разности второгопорядка ∆2 f (x) — это конечные разности от конечных разностей, идалее рекуррентно.Таблица 2.1. Горизонтальная таблицаконечных разностей функцииxyx0y0x1y1x2y2x3y3x4...y4...∆y∆y0∆y1∆y2∆y3...∆2 y...∆n y∆2 y0∆2 y1∆2 y2∆2 y3...............∆n y0∆n y1∆n y2...Интерполяционный полином Ньютона для равномерно расположенных узлов принимает видPn (x) =f (x0 ) +∆2 f (x0 )∆f (x0 )(x − x0 )(x − x1 ) +(x − x0 ) +1! h2! h2∆n f (x0 )(x − x0 )(x − x1 ) · · · (x − xn−1 ),...

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

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