- Lagrange interpolation
- Newton interpolation
- The divided difference for the Newton form.
- The Horner scheme

We will have the following property: where is the Kronecker delta:

(3.3) |

Then, the interpolating polynomial is:

(3.4) |

This way to construct an interpolating polynomial is not very effective because:

- The Lagrange polynomials are all of degree and thus require lots of computing time for creation, evaluation and addition (during the computation of )...
- We must know in advance all the points. An iterative procedure would be better.

The term assures that the second term of will vanish at all the points .

The final Newton interpolating polynomial is thus:

The final interpolation polynomial is the sum of polynomials of degree varying from 0 to (see Equation 3.5). The manipulation of the Newton polynomials (of Equation 3.5) is faster than the Lagrange polynomials (of Equation 3.2) and thus, is more efficient in term of computing time. Unfortunately, with Newton polynomials, we don't have the nice property that .

We can already write two basic properties of the divided difference:

We will proof this by induction. First, we rewrite Equation 3.9, for N=1, using 3.7:

Using Equation 3.8 inside 3.10, we obtain:

This equation is readily verified. The case for is solved. Suppose the Equation 3.9 verified for and proof that it will also be true for . First, let us rewrite equation 3.10, replacing by and replacing by

Let us rewrite Equation 3.9 with .

Using Equation 3.12 inside Equation 3.13:

Let us rewrite Equation 3.5 changing index to .

Recalling the definition of the divided difference: is the unique leading coefficient of the polynomial of degree that agree with at the sequence . Because of the uniqueness and comparing equation 3.14 and 3.15, we see that (replacing by in 3.14):

Using Equation 3.16 inside 3.14:

(3.16) |

Recalling the discussion of the paragraph after Equation 3.11, we can say then this last equation complete the proof for . The lemma 1 is now proved.

Using Equation 3.19 and lemma 2, we obtain directly 3.18. The lemma is proved.

Equation 3.18 has suggested the name ``divided difference''.

We will certainly NOT use the following algorithm:

**Initialisation****For**- Set

**Return**

The Horner scheme uses the following representation of the polynomial 3.20: , to construct a very efficient evaluation algorithm:

**Initialisation****For**- Set

**Return**