Calcolo delle differenze divise

Il calcolo delle differenze divise segue un algoritmo fondato su due loro proprietà:

1. $f[x_i]=f_i$
2. $f [ x_0,x_1, \ldots,x_{k+1} ] =\frac{f [ x_1,\ldots,x_{k+1} ] - f [ x_0,\ldots,x_k ] }{x_{k+1}-x_0}$

La procedura per calcolare le differenze divise lavora su un vettore inzializzato a $(f_0,\ldots,f_n)$ e applica ripetutamente questa proprietà. Al primo passo si calcola $f[x_{n-1},x_n]$ e lo si riscrive nel vettore in posizione $n$, e così via fino a $f[x_0,x_1]$ che viene salvato in posizione 2.

Alla fine del ciclo esterno il vettore conttiene $f[x_0], \ldots f[x_0,\ldots,x_k]$ che sono i coefficienti del polinomio interpolante.