Postać Newtona wielomianu

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})+\ldots +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 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}]$	$\ldots$	$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}]$
$\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}]$	$\ldots$	$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”.