The main problem using Lagrange's method mètode Lagrange is that if after calculating the interpolating polynomial we want to add new data, we have to start the method from the beginning, use none of any previous calculation. The method that we present here, the Newton's Method or method of divided differences, takes advantadge of previous calculations.
We begin with $$n +1$$ points $$(x_k,f_k)$$ and looking for a polynomial of degree $$n$$ of the type:
$$$P_n(x)=c_0+c_1\cdot(x-x_0)+c_2\cdot(x-x_0)\cdot (x-x_1)+ \dots +$$$ $$$+ c_n\cdot(x-x_0) \cdots (x-x_{n-1})$$$
Defining:
$$f[x_i]=f_i$$
$$f[x_i,x_{i+1},\dots,x_{i+j},x_{i+j+1}]= \dfrac{f[x_{i+1},\dots,x_{i+j+1}]-f[x_i,\dots,x_{i+j}]}{x_{j+i+1}-x_i}$$
We see that the coefficients are:
$$c_0=f_0$$
$$c_1=\dfrac{f_1-f_0}{x_1-x_0}=f[x_0,x_1]$$
$$\vdots$$
$$c_k=f[x_0,x_1,\dots,x_k]=\dfrac{f[x_1,\dots,x_k]-f[x_0,x_1,\dots,x_{k-1}]}{x_k-x_0}$$
We obtain the polynomial. We will use the following scheme to make it easier. We will use an example at every step.
- We write the $$x_k$$ in a column and next to that we write $$f_k$$:
| $$x_0$$ | $$f_0$$ |
| $$x_1$$ | $$f_1$$ |
| $$x_2$$ | $$f_2$$ |
| $$x_3$$ | $$f_3$$ |
For example, we take the information in the table:
| $$0$$ | $$1$$ |
| $$0.5$$ | $$1.28$$ |
| $$1$$ | $$2.72$$ |
- In a new column we calculate the so-called first order divided differences, $$$ f[x_i,x_j]=\dfrac{f_j-f_i}{x_j-x_i}$$$
| $$x_0$$ | $$f_0$$ | |
| $$ f[x_0,x_1]$$ | ||
| $$x_1$$ | $$f_1$$ | |
| $$ f[x_1,x_2]$$ | ||
| $$x_2$$ | $$f_2$$ | |
| $$f[x_2,x_3]$$ | ||
| $$x_3$$ | $$f_3$$ |
In our example:
| $$0$$ | $$1$$ | |
| $$ f[0,0.05]=\dfrac{f_1-f_0}{x_1-x_0}= \dfrac{1.28-1}{0.5-0}=0.568$$ | ||
| $$0.5$$ | $$1.28$$ | |
| $$ f[0.5,1]=\dfrac{f_2-f_1}{x_2-x_1}= \dfrac{2.72-1.28}{1-0.5}=2.867$$ | ||
| $$1$$ | $$2.72$$ |
- In a new column we calculate the second order divided difference, $$$ f[x_i,x_j,x_k]=\dfrac{f[x_j,x_k]-f[x_i,x_j]}{x_k-x_i}$$$
| $$x_0$$ | $$f_0$$ | ||
| $$ f[x_0,x_1]$$ | |||
| $$x_1$$ | $$f_1$$ | $$ f[x_0,x_1,x_2]$$ | |
| $$ f[x_1,x_2]$$ | |||
| $$x_2$$ | $$f_2$$ | $$ f[x_1,x_2,x_3]$$ | |
| $$ f[x_2,x_3]$$ | |||
| $$x_3$$ | $$f_3$$ |
In our example:
| $$0$$ | $$1$$ | ||
| $$0.568$$ | |||
| $$0.5$$ | $$1.28$$ | $$f[x_0,x_1,x_2]=\dfrac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0} =\dfrac{2.867-0.568}{1-0}=2.3$$ | |
| $$2.867$$ | |||
| $$1$$ | $$2.72$$ |
And we keep on iterating until coming to a unique value, which will be $$f[x_0,\dots, x_k]$$.
Then, the coefficients of the polynomial are the first elements of each column (except the first one, of course).
In our example the polynomial will be: $$$P_2(x)=1+0.568(x-0)+2.3\cdot(x-0)(x-0.5)=1+0.568x+2.3x(x-0.5)$$$
If we are given a new point when the polynomial is already computed, we only have to add a line in the low part of the table and start computing the successive divided differences up to obtain the unique term in the last column, as before. With this method we will use all the calculations, since the resultant polynomial will be the previous one plus a term of larger degree.