Многочлен Ньютона

Маючи множину з k + 1 точок

${\displaystyle (x_{0},y_{0}),\ldots ,(x_{j},y_{j}),\ldots ,(x_{k},y_{k})}$

де немає двох однакових x_j, інтерполяційний многочлен у формі Ньютона — це лінійна комбінація базових многочленів Ньютона

${\displaystyle N(x):=\sum _{j=0}^{k}a_{j}n_{j}(x)}$

де базовий многочлен Ньютона задається так

${\displaystyle n_{j}(x):=\prod _{i=0}^{j-1}(x-x_{i})}$

для j > 0 і ${\displaystyle n_{0}(x)\equiv 1}$.

Коефіцієнти задаються як

${\displaystyle a_{j}:=[y_{0},\ldots ,y_{j}]}$

де

${\displaystyle [y_{0},\ldots ,y_{j}]}$

це позначення розділеної різниці.

Отже інтерполяційний многочлен Ньютона можна записати як

${\displaystyle N(x)=[y_{0}]+[y_{0},y_{1}](x-x_{0})+\cdots +[y_{0},\ldots ,y_{k}](x-x_{0})(x-x_{1})\cdots (x-x_{k-1}).}$

Інтерполяційний многочлен Ньютона можна представити у спрощеній формі якщо ${\displaystyle x_{0},x_{1},\dots ,x_{k}}$ впорядковані послідовно і з рівними проміжками. Позначаючи ${\displaystyle h=x_{i+1}-x_{i}}$ для кожного ${\displaystyle i=0,1,\dots ,k-1}$ і ${\displaystyle x=x_{0}+sh}$, різницю ${\displaystyle x-x_{i}}$ можна записати як ${\displaystyle (s-i)h}$. Так інтерполяційний многочлен Ньютона набуває форми:

${\displaystyle {\begin{aligned}N(x)&=[y_{0}]+[y_{0},y_{1}]sh+\cdots +[y_{0},\ldots ,y_{k}]s(s-1)\cdots (s-k+1){h}^{k}\\&=\sum _{i=0}^{k}s(s-1)\cdots (s-i+1){h}^{i}[y_{0},\ldots ,y_{i}]\\&=\sum _{i=0}^{k}{s \choose i}i!{h}^{i}[y_{0},\ldots ,y_{i}]\end{aligned}}}$

така форма називається прямий інтерполяційний многочлен Ньютона.

Якщо вузли пересортувати в зворотньому порядку: ${\displaystyle {x}_{k},{x}_{k-1},\dots ,{x}_{0}}$, інтерполяційний многочлен Ньютона стає:

${\displaystyle N(x)=[y_{k}]+[{y}_{k},{y}_{k-1}](x-{x}_{k})+\cdots +[{y}_{k},\ldots ,{y}_{0}](x-{x}_{k})(x-{x}_{k-1})\cdots (x-{x}_{1})}$

Якщо ${\displaystyle {x}_{k},\;{x}_{k-1},\;\dots ,\;{x}_{0}}$ на рівних відстанях з ${\displaystyle x={x}_{k}+sh}$, а ${\displaystyle {x}_{i}={x}_{k}-(k-i)h}$ для i = 0, 1, ..., k, тоді,

${\displaystyle {\begin{aligned}N(x)&=[{y}_{k}]+[{y}_{k},{y}_{k-1}]sh+\cdots +[{y}_{k},\ldots ,{y}_{0}]s(s+1)\cdots (s+k-1){h}^{k}\\&=\sum _{i=0}^{k}{(-1)}^{i}{-s \choose i}i!{h}^{i}[{y}_{k},\ldots ,{y}_{k-i}]\end{aligned}}}$

така форма називається зворотній інтерполяційний многочлен Ньютона.

Розв'язуючи задачу інтерполяції приводить нас до необхідності розв'язання системи лінійних рівнянь. Використовуючи стандартний базис одночленів, ${\displaystyle \{1,x^{1},x^{2},\dots ,x^{n}\},}$ для інтерполяційного многочлена ми отримуємо дуже складну матрицю Вандермонда. Обираючи інший базис, а саме базис Ньютона, ми отримуємо систему лінійних рівнянь з набагато простішою нижньотрикутною матрицею, яку можна розв'язати швидше.

Для k + 1 точок ми будуємо базис Ньютона так:

${\displaystyle n_{j}(x):=\prod _{i=0}^{j-1}(x-x_{i})\qquad j=0,\ldots ,k.}$

Використовуючи ці многочлени як базис для ${\displaystyle \Pi _{k}}$, щоб розв'язати задачу поліноміальної інтерполяції, нам треба розв'язати

${\displaystyle {\begin{bmatrix}1&&\ldots &&0\\1&x_{1}-x_{0}&&&\\1&x_{2}-x_{0}&(x_{2}-x_{0})(x_{2}-x_{1})&&\vdots \\\vdots &\vdots &&\ddots &\\1&x_{k}-x_{0}&\ldots &\ldots &\prod _{j=0}^{k-1}(x_{k}-x_{j})\end{bmatrix}}{\begin{bmatrix}a_{0}\\\\\vdots \\\\a_{k}\end{bmatrix}}={\begin{bmatrix}y_{0}\\\\\vdots \\\\y_{k}\end{bmatrix}}.}$

Цю систему можна розв'язати покроково, розв'язуючи

${\displaystyle \sum _{i=0}^{j}a_{i}n_{i}(x_{j})=y_{j}\qquad j=0,\dots ,k.}$

Як можна бачити з означення розділеної різниці, ми можемо додавати нові точки, що отримати новий інтерполяційний многочлен без переобчислення старих коефіцієнтів. І якщо точка змінилась, зазвичай, нам не потрібно переобчислювати усі коефіцієнти. Ба, більше — якщо x_i розташовані на рівних відстанях, обчислення стає набагато простішим. Тому, зазвичай, віддають перевагу формулі із розділеними різницями перед многочленом Лагранжа.

• Інтерполяційний многочлен
• Многочлен Лагранжа
• Інтерполяційна формула Брамагупти

1. https://web.archive.org/web/20100904060718/http://nptel.iitm.ac.in/courses/Webcourse-contents/IIT-KANPUR/Numerical%20Analysis/numerical-analysis/Rathish-kumar/rathish-oct31/fratnode5.html