Postać Newtona wielomianu

Postać Newtona to 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 w postaci:

$w(x) = \sum_{i=0}^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) + \cdots + 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)$
$\vdots$	$\vdots$
$x_n$	$f(x_n)$

Uzupełniamy tę 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]$
$\vdots$	$\vdots$	$\vdots$
$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]$	$\cdots$	$f[x_{i-n},\ldots,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]$
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\ddots$
$x_n$	$f(x_n)$	$f[x_{n-1},x_n]$	$f[x_{n-2},x_{n-1},x_n]$	$\cdots$	$f[x_0,\ldots,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".