Global Polynomial Interpolation

This section defines a polynomial that goes through a set number (m+1) of points. A global polynomial is defined over the entire region of space

This polynomial is of degree m (highest power is xm) and order m+1 (m+1 parameters {cj}). If we are given a set of m+1 points

then Lagrange's formula gives a polynomial of degree m that goes through the m+1 points:

Note that each coefficient of yj is a polynomial of degree m that vanishes at the points {xj} (except for one value of j) and takes the value of 1.0 at that point, i.e.

If the function f(x) is known, the error in the approximation is [Abramowitz and Stegun, 1964]

The error is of course zero at the points used in the interpolation, but it is non-zero in between those points. The evaluation of Pm(x) at a point other than at the defining points can be made with Neville's algorithm [Presset al. 1986]. Let P1 be the value at x of the unique function passing through the point (x1,y1); i.e. P1=y1. Let P12 be the value at x of the unique polynomial passing through the points x1 and x2. Likewise, Pijk...r is the unique polynomial passing through the points xi, xj, xk, ...xr. Then use the table

These entries are defined using

For example, consider P1234. The terms on the right-hand side involve P123 and P234. The "parents," P123 and P234, already agree at points 2 and 3. Here i=1, m=3; thus, the parents agree at xi+1, ..., xi+m-1 already. The formula makes Pi(i+1)...(i+m) agree with the function at the additional points xi+m and xi. Thus, Pi(i+1)...(i+m) agrees with the function at all the points {xi, xi+1, ...xi+m}.

In Matlab, the function y = polyval(p,x) evaluates the polynomial p at the x points (x can be a vector). The polynomial is in the form

Other interpolation schemes are: orthogonal polynomials of x that give a best fit; rational polynomials that are ratios of polynomials; piecewise polynomials derived with forward differences (points to the right) and backward differences (points to the left); splines; and finite elements.

Take Home Message: Lagrange's Formula is useful for defining and evaluating polynomial functions which go through a set number of points.