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

Означення

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

$(x_0,y_0),\dots ,(x_j,y_j),\dots ,(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,\dots ,y_j]$

де

$[y_0,\dots ,y_j]$

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

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

$N(x)=[y_0]+[y_0,y_1](x-x_0)+\cdots +[y_0,\dots ,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{array}{cc}N(x)& =[y_0]+[y_0,y_1]sh+\cdots +[y_0,\dots ,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,\dots ,y_i]\\ & =\sum _{i=0}^k(\genfrac{}{}{0ex}{}{s}{i})i!h^i[y_0,\dots ,y_i]\end{array}$

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

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

$N(x)=[y_k]+[y_k,y_{k-1}](x-x_k)+\cdots +[y_k,\dots ,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{array}{cc}N(x)& =[y_k]+[y_k,y_{k-1}]sh+\cdots +[y_k,\dots ,y_0]s(s+1)\cdots (s+k-1)h^k\\ & =\sum _{i=0}^k{(-1)}^i(\genfrac{}{}{0ex}{}{-s}{i})i!h^i[y_k,\dots ,y_{k-i}]\end{array}$

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

Головна ідея

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

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

$n_j(x):=\prod _{i=0}^{j-1}(x-x_i)j=0,\dots ,k.$

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

$\left[\begin{array}{ccccc}1& & \dots & & 0\\ 1& x_1-x_0& & & \\ 1& x_2-x_0& (x_2-x_0)(x_2-x_1)& & ⋮\\ ⋮& ⋮& & \ddots & \\ 1& x_k-x_0& \dots & \dots & \prod _{j=0}^{k-1}(x_k-x_j)\end{array}\right]\left[\begin{array}{c}{a}_0\\ \\ ⋮\\ \\ a_k\end{array}\right]=\left[\begin{array}{c}{y}_0\\ \\ ⋮\\ \\ y_k\end{array}\right].$

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

$\sum _{i=0}^j{a}_i{n}_i(x_j)=y_{j}j=0,\dots ,k.$

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

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

Приклад

Розділені різниці можна записати у вигляді таблиці. Наприклад, для функції f і точок $x_0,\dots ,x_n$. Записуємо

$\begin{array}{cccc}{x}_0& f(x_0)& & \\ & & \frac{f(x_1)-f(x_0)}{x_1-x_0}& \\ x_1& f(x_1)& & \frac{\frac{f(x_2)-f(x_1)}{x_2-x_1}-\frac{f(x_1)-f(x_0)}{x_1-x_0}}{x_2-x_0}\\ & & \frac{f(x_2)-f(x_1)}{x_2-x_1}& \\ x_2& f(x_2)& & ⋮\\ & & ⋮& \\ ⋮& & & ⋮\\ & & ⋮& \\ x_n& f(x_n)& & \end{array}$

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

Див. також

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

Посилання

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