Postać Newtona wielomianu

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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) = \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 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”.