Next: Multivariate Lagrange interpolation. Up: Multivariate Lagrange Interpolation Previous: Introduction   Contents

Subsections

# A small reminder about univariate interpolation.

We want to interpolate a simple curve in the plane (in ). We have a set of interpolation points on the curve. We can choose N as we want. We must have if .

## Lagrange interpolation

We define a Lagrange polynomial as

 (3.2)

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 solution to these problems : The Newton interpolation.

## Newton interpolation

The Newton algorithm is iterative. We use the polynomial of degree which already interpolates points and transform it into a polynomial of degree which interpolates points of the function . We have:

 (3.5)

The term assures that the second term of will vanish at all the points .
Definition: is called a ''divided difference''. It's the unique leading coefficient (that is the coefficient of ) of the polynomial of degree that agree with at the sequence .
The final Newton interpolating polynomial is thus:

 (3.6)

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:

 (3.7)

 (3.8)

## The divided difference for the Newton form.

Lemma 1

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

 (3.9)

Using Equation 3.8 inside 3.10, we obtain:

 (3.10)

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 as a function of x. (In other word, we will interpolate the function at the point using 3.10.) We obtain:

 (3.11)

Let us rewrite Equation 3.9 with .

 (3.12)

Using Equation 3.12 inside Equation 3.13:

 (3.13)

Let us rewrite Equation 3.5 changing index to .

 (3.14)

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):

 (3.15)

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.
Lemma 2

This is clear from the definition of .
Lemma 3

Combining Equation 3.16 and Equation 3.8, we obtain:

 (3.17)

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 can generate the entries of the divided difference table column by column from the given dataset using Equation 3.18. The top diagonal then contains the desired coefficients , of the final Newton form of Equation 3.6.

## The Horner scheme

Suppose we want to evaluate the following polynomial:

 (3.18)

We will certainly NOT use the following algorithm:
1. Initialisation
2. For
1. Set
3. Return
This algorithm is slow (lots of multiplications in ) and leads to poor precision in the result (due to rounding errors).
The Horner scheme uses the following representation of the polynomial 3.20: , to construct a very efficient evaluation algorithm:
1. Initialisation
2. For
1. Set
3. Return
There is only multiplication in this algorithm. It's thus very fast and accurate.

Next: Multivariate Lagrange interpolation. Up: Multivariate Lagrange Interpolation Previous: Introduction   Contents
Frank Vanden Berghen 2004-04-19