Mètode Newton

El principal problema del mètode Lagrange és que, si després de calcular el polinomi interpolador volem afegir una nova dada, hem de començar amb el mètode des del principi, sense poder aprofitar cap càlcul. El mètode que presentem a continuació, el mètode de Newton o de diferències dividides, aprofitarà els càlculs anteriors.

Partinm de $n+1$ punts $(x_k,f_k)$ i busquem un polinomi de grau $n$ del tipus:

$$P_n(x)=c_0+c_1\cdot (x-x_0)+c_2\cdot (x-x_0)\cdot (x-x_1)+\cdots +$$ $$+c_n\cdot (x-x_0)\cdots (x-x_{n-1})$$

Definint:

$f[x_i]=f_i$

$f[x_i,x_{i+1},\dots ,x_{i+j},x_{i+j+1}]={\displaystyle \frac{f[x_{i+1},\dots ,x_{i+j+1}]-f[x_i,\dots ,x_{i+j}]}{x_{j+i+1}-x_i}}$

Tenim que els coeficients són:

$c_0=f_0$

$c_1={\displaystyle \frac{f_1-f_0}{x_1-x_0}}=f[x_0,x_1]$

$⋮$

$c_k=f[x_0,x_1,\dots ,x_k]={\displaystyle \frac{f[x_1,\dots ,x_k]-f[x_0,x_1,\dots ,x_{k-1}]}{x_k-x_0}}$

Obtenim el polinomi. Farem servir el següent esquema per fer-lo més fàcil ajudant-nos, a cada pas, amb un exemple.

• Escrivim en una columna les $x_k$ i en la del costat les $f_k$:

• En una nova columna calculem l'anomenada diferència dividida de primer ordre, $$f[x_i,x_j]={\displaystyle \frac{f_j-f_i}{x_j-x_i}}$$

• En una nova columna calculem la diferència dividida de segon ordre, $$f[x_i,x_j,x_k]={\displaystyle \frac{f[x_j,x_k]-f[x_i,x_j]}{x_k-x_i}}$$

I seguim iterant fins arribar a un únic valor, que serà $f[x_0,\dots ,x_k]$.

Llavors, el polinomi té per coeficients el primer element de cada columna (excepte el primer, és clar).

Si un cop calculat el polinomi, ens donen una altra dada, només hem d'afegir una fila a la part inferior de la taula i anar calculant les diferències dividides successives fins a aconseguir, com abans, un sol terme en l'última columna. Amb aquest mètode aprofitarem tots els càlculs, ja que el polinomi resultant serà l'anterior afegint-hi un terme de grau més gran.