Интерполяционный многочлен Ньютона

Лекция 2. Интерполяционный многочлен Ньютона. Пусть дана табличная функция: i 1 ... n xi x0 x1 . . . xn yi y0 y1 . . . yn или yi = f (xi ), i = 0, 1, . . . , n. (1) Требуется найти многочлен Pn (x) степени не выше n, удовлетворяющий условиям Pn (xi ) = yi , i = 0, 1, . . . , n. (2) Случай 1. Равноотстоящие узлы интерполяции. Пусть xi = x0 + ih, i = 0, 1, . . . , n, где h – шаг разбиения. Введем понятие конечных разностей. Конечные разности первого порядка функции y = f (x): ∆y0 = y1 − y0 , ∆y1 = y2 − y1 , ∆yn−1 = yn − yn−1 ... – приращения функции при переходе от одного узла к следующему; можно получить для первых n точек. Конечные разности второго порядка: ∆2 y0 = ∆y1 − ∆y0 , ∆2 y1 = ∆y2 − ∆y1 , ... ∆2 yn−2 = ∆yn−1 − ∆yn−2 – приращения разности первого порядка; можно получить для первых n − 1 точек. ... Конечная разность n-го порядка: ∆n y0 = ∆n−1 y1 − ∆n−1 y0 существует только в точке x0 . 1 Будем искать интерполяционный многочлен (степени не выше n) в виде: Pn (x) = a0 + a1 (x − x0 ) + a2 (x − x0 )(x − x1 ) + . . . + + an (x − x0 )(x − x1 ) . . . (x − xn−1 ). (3) Используем условия (2) для нахождения коэффициентов a0 , a1 , . . . , an этого многочлена: Pn (x0 ) = a0 = y0 , Pn (x1 ) = a0 + a1 (x1 − x0 ) = a0 + a1 h = y1 , Pn (x2 ) = a0 + a1 (x2 − x0 ) + a2 (x2 − x0 )(x2 − x1 ) = a0 + 2a1 h + 2a2 h2 = y2 , ... Отсюда находим: a0 = y 0 , y 1 − a0 y1 − y0 ∆y0 a1 = = = , h h h y2 − a0 − 2a1 h y2 − y0 − 2(y1 − y0 ) a2 = = = 2h2 2h2 (y2 − y1 ) − (y1 − y0 ) ∆y1 − ∆y0 ∆2 y0 = = = , 2h2 2h2 2h2 ... ∆n y0 an = . n! hn Подставляя эти выражения в формулу (3), получаем ∆2 y0 ∆y0 (x − x0 ) + (x − x0 )(x − x1 ) + . . . + Pn (x) = y0 + h 2! h2 ∆n y0 + (x − x0 )(x − x1 ) . . . (x − xn−1 ) (4) n! hn – первый интерполяционный многочлен Ньютона (для интерполирования вперед). Замечания. 1) Если x∗ ∈ [xi , xi+1 ], то в (4) следует заменить x0 на xi и y0 на yi . 2) Формулу (4) используют для вычисления значений функции в точках левой половины отрезка [x0 , xn ]. Для правой половины отрезка [x0 , xn ] 2 используют второй интерполяционный многочлен Ньютона (для интерполирования назад): ∆yn−1 ∆2 yn−2 Pn (x) = yn + (x − xn ) + (x − xn )(x − xn−1 ) + . . . + h 2! h2 ∆n y0 (x − xn )(x − xn−1 ) . . . (x − x1 ). (5) + n! hn Пример. Функция y(x) задана таблицей x 0 1 2 3 y 0 1 8 27 Приблизить функцию интерполяционным многочленом Ньютона. Найти приближенное значение функции y(x) в точках x∗1 = 0,5 и x∗2 = 1,5.  Составим таблицу конечных разностей i xi yi ∆yi ∆2 yi ∆3 yi 1 6 6 1 1 1 7 12 – 2 2 8 19 – – 3 3 27 – – – Построим интерполяционный многочлен Ньютона P3 (x) третьей степени. В этом случае n = 3, h = 1. По формуле (4) находим: ∆2 y0 ∆3 y0 ∆y0 (x−x0 )+ (x−x0 )(x−x1 )+ (x−x0 )(x−x1 )(x−x2 ) = P3 (x) = y0 + h 2! h2 3! h3 = x + 3x(x − 1) + x(x − 1)(x − 2) = x + 3x2 − 3x + x(x2 − 3x + 2) = x3 . Таким образом, P3 (x) = x3 , P3 (x∗1 ) = 0,53 = 0,125, P3 (x∗2 ) = 1,53 = 3,375.  Случай 2. Неравноотстоящие узлы интерполяции. Интерполяционный многочлен Ньютона: Pn (x) = f (x0 ) + f (x0 , x1 )(x − x0 ) + f (x0 , x1 , x2 )(x − x0 )(x − x1 ) + . . . + + f (x0 , x1 , . . . , xn )(x − x0 )(x − x1 ) . . . (x − xn−1 ), (6) 3 где f (xi+1 ) − f (xi ) , xi+1 − xi – разделенная разность первого порядка; f (xi , xi+1 ) = f (xi , xi+1 , xi+2 ) = i = 0, 1, . . . , n − 1, f (xi+1 , xi+2 ) − f (xi , xi+1 ) , xi+2 − xi i = 0, 1, . . . , n − 2, – разделенная разность второго порядка; ... f (xi , xi+1 , . . . , xi+k ) = f (xi+1 , xi+2 , . . . , xi+k ) − f (xi , xi+1 , . . . , xi+k−1 ) = , xi+k − xi i = 0, 1, . . . , n − k, – разделенная разность k-го порядка; ... f (x1 , x2 , . . . , xn ) − f (x0 , x1 , . . . , xn−1 ) xn − x0 – разделенная разность n-го порядка. f (x0 , x1 , . . . , xn ) = Решение следует начинать с составления таблицы разделенных разностей: i xi yi x0 y0 1 x1 y1 f (xi , xi+1 ) f (xi , xi+1 , xi+2 ) . . . f (xi , xi+1 , . . . , xi+n ) ... ... ... n xn yn Замечание. Решение задачи интерполяции по Ньютону имеет преимущества по сравнению с ее решением в явном виде (нахождение коэффициентов интерполяционного многочлена из системы уравнений (3) Лекции 1): при изменении количества узловых точек и степени многочлена эту систему требуется решать заново, в то время как в многочлене Ньютона требуется только добавить или отбросить соответствующее число слагаемых в формулах (4), (5) или (6). Это удобно на практике и ускоряет процесс вычислений. 4