Interpolazione polinomiale nella base di Newton

Per ottenere un algoritmo efficiente per il calcolo del polinomio interpolante è necessario abbandonare la rappresentazione del polinomio interpolate nella base canonica ed adottare una base diversa per lo spazio $\prod _n$. Una possibile base è la base di Newton, così definita ricorsivamente:

$$\left\{\begin{array}{ccl} \omega_0(x) & = & 1 \\ \omega_k(x) & = & (x-x_{k-1})\; \omega_{k-1}(x) \end{array}\right.$$

In pratica si ha $\omega_k(x)=(x-x_0)(x-x_1)\ldots(x-x_{k-1})$ da cui segue che $\omega_k(x_j)=0$ per $j<k$.

Si dimostra che $\{\omega_i(x)\}_{i=0\ldots n}$ è una base per $\prod _n$. Il polinomio interpolante di grado $n$ interpolante una funzione può essere quindi espresso come

$$\sum_{i=0}^{n}{c_i\omega_i(x)}$$

I coefficienti sono dati dalle differenze divise così definite:

$$c_k =f[x_0,\ldots,x_k] =\sum_{i=0}^{k}{\frac{f_i}{\prod_{j=0,j \neq i}^{k}{(x_i-x_j)}}} \quad k=0 \ldots n$$