Интерполяционные формулы Ньютона
Интерполяционные формулы Ньютона — формулы вычислительной математики, применяющиеся для полиномиального интерполирования.
Формулы
Пусть заданы некоторые попарно различные точки [math]\displaystyle{ x_0, \, x_1, \, \ldots, \, x_n }[/math], называемые также узлами интерполяции, и известны значения [math]\displaystyle{ f(x_0), \, f(x_1), \, \ldots, \, f(x_n) }[/math] некоторой функции [math]\displaystyle{ f }[/math] в этих точках.
Случай неравноотстоящих узлов
Если все расстояния между соседними узлами различны, то многочлен Ньютона строится по формуле[1]
- [math]\displaystyle{ P_n(x) = f(x_0) + (x-x_0) f(x_0;x_1) + (x-x_0)(x-x_1) f(x_0;x_1;x_2) + \ldots + (x-x_0)\ldots(x-x_{n-1}) f(x_0;\ldots;x_n), }[/math]
где [math]\displaystyle{ f(x_0;\ldots;x_n) }[/math] — разделённая разность порядка [math]\displaystyle{ n }[/math].
Пользуясь свойствами разделённой разности можно показать, что приведённый выше многочлен действительно решает задачу интерполяции:[2]
Пусть [math]\displaystyle{ L_k(x) }[/math] - интерполяционный многочлен Лагранжа для точек [math]\displaystyle{ x_0, \, x_1, \, \ldots, \, x_k }[/math]. Тогда [math]\displaystyle{ L_n(x)=L_0(x)+(L_1(x)-L_0(x))+ \ldots + (L_n(x)-L_{n-1}(x)) }[/math].
Рассмотрим [math]\displaystyle{ L_k(x)-L_{k-1}(x) }[/math]:
[math]\displaystyle{ L_k(x) - L_{k-1}(x) = \sum_{i=0}^k f(x_i) * \prod_{j=0,j \neq i}^k \frac{(x-x_j)}{(x_i-x_j)} - \sum_{i=0}^{k-1} f(x_i) * \prod_{j=0,j \neq i}^{k-1} \frac{(x-x_j)}{(x_i-x_j)}= }[/math]
[math]\displaystyle{ = \sum_{i=0}^{k-1} f(x_i) * \frac{(x-x_0)* \ldots (x-x_{i-1})*(x-x_{i+1}) \ldots *(x-x_{k-1})}{(x_i-x_0)* \ldots *(x_i-x_{i-1})*(x_i-x_{i+1})* \ldots *(x_i-x_{k-1})} * (\frac{x-x_k}{x_i-x_k}-1) + }[/math]
[math]\displaystyle{ + f(x_k)* \frac{(x-x_0)* \ldots *(x-x_{k-1})}{(x_k-x_0)* \ldots *(x_k-x_{k-1})} }[/math].
С другой стороны разность двух интерполяционных многочленов Лагранжа есть многочлен степени [math]\displaystyle{ k-1 }[/math] , причём известны его корни - [math]\displaystyle{ x_0, x_1, x_2, ... , x_{k-1} }[/math].
По теореме Безу получаем: [math]\displaystyle{ L_k(x)-L_{k-1}(x)=a*(x-x_0)*...*(x-x_{k-1}) }[/math].
Находим [math]\displaystyle{ a }[/math]: пусть [math]\displaystyle{ x=x_{k} }[/math],
[math]\displaystyle{ a=\sum_{i=0}^k \frac{f(x_i)}{(x_i-x_0)*...*(x_i-x_{i-1})*(x_i-x_{i+1})*...*(x_i-x_k)}=f(x_0;x_1;...;x_k) }[/math]
После подстановки результата в [math]\displaystyle{ L_n(x) }[/math] получаем [math]\displaystyle{ P_n(x) }[/math].
Таким образом, показано, что многочлен Ньютона в случае неравноотстоящих узлов совпадает с интерполяционным многочленом Лагранжа, и следовательно решает задачу интерполяции.
Случай равноотстоящих узлов
Если соседние узлы находятся друг от друга на некотором фиксированном расстоянии [math]\displaystyle{ h }[/math], то есть [math]\displaystyle{ x_i = x_0 + ih }[/math], [math]\displaystyle{ i = 0,\ldots,n }[/math], то многочлен Ньютона можно строить либо начиная с [math]\displaystyle{ x_0 }[/math] (в таком случае говорят об «интерполировании вперёд»), либо с [math]\displaystyle{ x_n }[/math] («интерполирование назад»).
В первом случае формула для многочлена Ньютона принимает вид[3]
- [math]\displaystyle{ P_n(x) = y_0 + q \Delta y_0 + \frac{q(q-1)}{2!} \Delta^2 y_0 + \ldots + \frac{q(q-1)\ldots(q-n+1)}{n!} \Delta^n y_0, }[/math]
где [math]\displaystyle{ q=(x-x_0)/h, \; y_i=f(x_i) }[/math], а выражения вида [math]\displaystyle{ \Delta^ky_0 }[/math] — конечные разности.
Во втором случае формула принимает вид[4]
- [math]\displaystyle{ P_n(x) = y_n + q \Delta y_{n-1} + \frac{q(q+1)}{2!} \Delta^2 y_{n-2} + \ldots + \frac{q(q+1)\ldots(q+n-1)}{n!} \Delta^n y_0, }[/math]
где [math]\displaystyle{ q=(x-x_n)/h }[/math].
При [math]\displaystyle{ h=1 }[/math] справедлива формула
- [math]\displaystyle{ P_n(x)=\sum_{m=0}^{n} C_x^m \sum_{k=0}^m(-1)^{m-k}\,C_m^k\,f(k) }[/math]
где [math]\displaystyle{ C_x^m }[/math] — обобщённые на область действительных чисел биномиальные коэффициенты.
Остаточный член
Многочлен Ньютона представляет собой одну из форм записи многочлена Лагранжа, поэтому остаточные члены этих формул совпадают[5]. Однако остаточный член [math]\displaystyle{ R_n(x) = f(x) - P_n(x) }[/math] формулы Ньютона можно записать в другой форме:
- для случая неравноотстоящих узлов[5]:
- [math]\displaystyle{ R_n(x) = (x-x_0)(x-x_1) \ldots (x-x_n) f(x_0;\ldots;x_n). }[/math]
- Если функция [math]\displaystyle{ f }[/math] имеет производную порядка [math]\displaystyle{ n+1 }[/math], то [math]\displaystyle{ f(x_0;\ldots;x_n) = \frac{f^{(n+1)}(\xi)}{(n+1)!}, }[/math] где [math]\displaystyle{ \xi }[/math] — некоторая точка, принадлежащая наименьшему промежутку, содержащему все узлы интерполяции.
- для случая равноотстоящих узлов:
- для интерполирования вперёд[6]:
- [math]\displaystyle{ R_n = \frac{h^{n+1} f^{(n+1)}(\xi)}{(n+1)!} q(q-1)(q-2)\ldots(q-n). }[/math]
- для интерполирования назад[7]:
- [math]\displaystyle{ R_n = \frac{h^{n+1} f^{(n+1)}(\xi)}{(n+1)!} q(q+1)(q+2)\ldots(q+n). }[/math]
См. также
Примечания
- ↑ Березин, Жидков, 1962, с. 107.
- ↑ Berezin, I. S. (Ivan Semenovich). Методы вычислений.. — Nauka, Glav. red. fiziko-matematicheskoĭ lit-ry, 1966-.
- ↑ Березин, Жидков, 1962, с. 119.
- ↑ Березин, Жидков, 1962, с. 121.
- ↑ 5,0 5,1 Березин, Жидков, 1962, с. 109.
- ↑ Березин, Жидков, 1962, с. 122.
- ↑ Березин, Жидков, 1962, с. 123.
Литература
- Березин, И. С., Жидков Н. П. Методы вычислений. — 2-е изд. — М.: Физматлит, 1962. — Т. I.
 | Для улучшения этой статьи желательно: |