Polynomial interpolation

The unique solution to interpolation of at points is given by:

where are Lagrange Cardinal Polynomials.

Divided difference

is the coefficient next to
in the polynomial which interpolates at points .

Suppose interpolates at , while interpolates at . Then

interpolates at .
Hence the recurrence formula holds:

The Newton formula

interpolates at .

Proof

By induction:

Suppose interpolates at .
Then has degree (at most)
and roots at for (by induction hypothesis).
So it has to be .

Errors

Define the error functions .
It has roots in , hence has at least one root .
Then or for some in the interval.
Furthermore,
where interpolates at .
So certainly:

On interval , is minimized for (scaled) Chebyshev polynomials
(proof by contradiction, using that roots alternate in sign), so

and we have