Интерполяционные формулы Ньютона

Пусть заданы некоторые попарно различные точки ${\displaystyle x_{0},\,x_{1},\,\ldots ,\,x_{n}}$, называемые также узлами интерполяции, и известны значения ${\displaystyle f(x_{0}),\,f(x_{1}),\,\ldots ,\,f(x_{n})}$ некоторой функции ${\displaystyle f}$ в этих точках.

Если все расстояния между соседними узлами различны, то многочлен Ньютона строится по формуле^[1]

${\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}),}$

где ${\displaystyle f(x_{0};\ldots ;x_{n})}$ — разделённая разность порядка ${\displaystyle n}$.

Пользуясь свойствами разделённой разности можно показать, что приведённый выше многочлен действительно решает задачу интерполяции:^[2]

Пусть ${\displaystyle L_{k}(x)}$ - интерполяционный многочлен Лагранжа для точек ${\displaystyle x_{0},\,x_{1},\,\ldots ,\,x_{k}}$. Тогда ${\displaystyle L_{n}(x)=L_{0}(x)+(L_{1}(x)-L_{0}(x))+\ldots +(L_{n}(x)-L_{n-1}(x))}$.

Рассмотрим ${\displaystyle L_{k}(x)-L_{k-1}(x)}$:

${\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})}}=}$

${\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)+}$

${\displaystyle +f(x_{k})*{\frac {(x-x_{0})*\ldots *(x-x_{k-1})}{(x_{k}-x_{0})*\ldots *(x_{k}-x_{k-1})}}}$.

С другой стороны разность двух интерполяционных многочленов Лагранжа есть многочлен степени ${\displaystyle k-1}$ , причём известны его корни - ${\displaystyle x_{0},x_{1},x_{2},...,x_{k-1}}$.

По теореме Безу получаем: ${\displaystyle L_{k}(x)-L_{k-1}(x)=a*(x-x_{0})*...*(x-x_{k-1})}$.

Находим ${\displaystyle a}$: пусть ${\displaystyle x=x_{k}}$,

${\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})}$

После подстановки результата в ${\displaystyle L_{n}(x)}$ получаем ${\displaystyle P_{n}(x)}$.

Таким образом, показано, что многочлен Ньютона в случае неравноотстоящих узлов совпадает с интерполяционным многочленом Лагранжа, и следовательно решает задачу интерполяции.

Если соседние узлы находятся друг от друга на некотором фиксированном расстоянии ${\displaystyle h}$, то есть ${\displaystyle x_{i}=x_{0}+ih}$, ${\displaystyle i=0,\ldots ,n}$, то многочлен Ньютона можно строить либо начиная с ${\displaystyle x_{0}}$ (в таком случае говорят об «интерполировании вперёд»), либо с ${\displaystyle x_{n}}$ («интерполирование назад»).

В первом случае формула для многочлена Ньютона принимает вид^[3]

${\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},}$

где ${\displaystyle q=(x-x_{0})/h,\;y_{i}=f(x_{i})}$, а выражения вида ${\displaystyle \Delta ^{k}y_{0}}$ — конечные разности.

Во втором случае формула принимает вид^[4]

${\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},}$

где ${\displaystyle q=(x-x_{n})/h}$.

При ${\displaystyle h=1}$ справедлива формула

${\displaystyle P_{n}(x)=\sum _{m=0}^{x}C_{x}^{m}\sum _{k=0}^{m}(-1)^{m-k}\,C_{m}^{k}\,f(k)}$

где ${\displaystyle C_{x}^{m}}$ — обобщённые на область действительных чисел биномиальные коэффициенты.

Многочлен Ньютона представляет собой одну из форм записи многочлена Лагранжа, поэтому остаточные члены этих формул совпадают^[5]. Однако остаточный член ${\displaystyle R_{n}(x)=f(x)-P_{n}(x)}$ формулы Ньютона можно записать в другой форме:

• для случая неравноотстоящих узлов^[5]:

${\displaystyle R_{n}(x)=(x-x_{0})(x-x_{1})\ldots (x-x_{n})f(x_{0};\ldots ;x_{n}).}$

Если функция ${\displaystyle f}$ имеет производную порядка ${\displaystyle n+1}$, то ${\displaystyle f(x_{0};\ldots ;x_{n})={\frac {f^{(n+1)}(\xi )}{(n+1)!}},}$ где ${\displaystyle \xi }$ — некоторая точка, принадлежащая наименьшему промежутку, содержащему все узлы интерполяции.

• для случая равноотстоящих узлов:

для интерполирования вперёд^[6]:

${\displaystyle R_{n}={\frac {h^{n+1}f^{(n+1)}(\xi )}{(n+1)!}}q(q-1)(q-2)\ldots (q-n).}$

для интерполирования назад^[7]:

${\displaystyle R_{n}={\frac {h^{n+1}f^{(n+1)}(\xi )}{(n+1)!}}q(q+1)(q+2)\ldots (q+n).}$