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

Означення

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

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

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

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

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

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

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

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

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

де

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

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

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

$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}).$

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

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

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

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

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

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

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

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

Головна ідея

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

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

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

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

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

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

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

Застосування

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

Приклад

Розділені різниці можна записати у вигляді таблиці. Наприклад, для функції f і точок $x_{0},\ldots ,x_{n}$. Записуємо

${\begin{matrix}x_{0}&f(x_{0})&&\\&&{f(x_{1})-f(x_{0}) \over x_{1}-x_{0}}&\\x_{1}&f(x_{1})&&{{f(x_{2})-f(x_{1}) \over x_{2}-x_{1}}-{f(x_{1})-f(x_{0}) \over x_{1}-x_{0}} \over x_{2}-x_{0}}\\&&{f(x_{2})-f(x_{1}) \over x_{2}-x_{1}}&\\x_{2}&f(x_{2})&&\vdots \\&&\vdots &\\\vdots &&&\vdots \\&&\vdots &\\x_{n}&f(x_{n})&&\\\end{matrix}}$

Тоді інтерполяційний многочлен формується використовуючи горішні елементи кожного стовпчика як коефіцієнти.

Див. також

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

Посилання

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