Postać Newtona wielomianu

Szablon:Dopracować Postać Newtona – jedna z metod przedstawiania wielomianu. Dla wielomianu stopnia $n$ wybiera się $n+1$ punktów $x_0,x_1,\dots ,x_n$ i buduje wielomian postaci:

$w(x)=a_0+\sum _{i=1}^n{a}_i\prod _{j=0}^{i-1}(x-x_j)$ $=a_0+a_1(x-x_0)+a_2(x-x_1)(x-x_0)+\dots +a_n(x-x_{n-1})\cdots (x-x_1)(x-x_0)$

Wielomiany Newtona mogą być używane do interpolowania dowolnych funkcji.

Procedura interpolacji jest następująca:

$x_i$	$f(x_i)$
$x_0$	$f(x_0)$
$x_1$	$f(x_1)$
$x_2$	$f(x_2)$
$⋮$	$⋮$
$x_n$	$f(x_n)$

Uzupełniamy tabelkę dopisując kolejne kolumny różnicami dzielonymi:

$x_i$	$f(x_i)$	$f[x_{i-1},x_i]$
$x_0$	$f(x_0)$
$x_1$	$f(x_1)$	$f[x_0,x_1]$
$x_2$	$f(x_2)$	$f[x_1,x_2]$
$⋮$	$⋮$	$⋮$
$x_n$	$f(x_n)$	$f[x_{n-1},x_n]$

Aż skończy się możliwość dalszego dopisywania:

$x_i$	$f(x_i)$	$f[x_{i-1},x_i]$	$f[x_{i-2},x_{i-1},x_i]$	$\dots$	$f[x_0,\dots ,x_i]$
$x_0$	$f(x_0)$
$x_1$	$f(x_1)$	$f[x_0,x_1]$
$x_2$	$f(x_2)$	$f[x_1,x_2]$	$f[x_0,x_1,x_2]$
$⋮$	$⋮$	$⋮$	$⋮$	$\ddots$
$x_n$	$f(x_n)$	$f[x_{n-1},x_n]$	$f[x_{n-2},x_{n-1},x_n]$	$\dots$	$f[x_0,\dots ,x_n]$

I używamy kolejnych liczb po przekątnej jako współczynników $a_i.$

Warto zauważyć, że przy implementacji znajdowania kolejnych wyrazów różnicowych nie musimy korzystać z macierzy (tablicy wielowymiarowej) – wystarczy nam jedynie zwykła tablica, pod warunkiem, że wyrazy będziemy obliczać „od dołu”.