The Interpolatory Polynomial


Given a set of n+1 points (x0,f0),...,(xn,fn), it can be shown that there is exactly one polynomial of degree n or less passing through the points. This polynomial is called the interpolating or interpolatory polynomial for the points. There will be many other polynomials with degree greater than n which also pass through the points, but only one with degree n or less.

There are several ways to find the interpolatory polynomial. Three are presented here, the worst one first.

A direct method: If one writes the polynomial as p(x) = a0+a1x+a2x2+...+anxn, then substituting the points (x0,f0), (x1,f1), etc into p(x) gives a system of n+1 equations for the n+1 unknown coefficients a0,a1,...,an. This system can then be solved, for example using Gaussian Elimination. This method is not a very good one, since the number of operations required to solve the system of equations will be roughly proportional to n3. If one doubles the number of points, it will octuple (multiply by 8) the number of operations required. We say that this method is O(n3), or örder n3".

The Lagrange Interpolating Polynomial (LIP): Given x0,x1,...,xn, we can define special polynomials li(x) which satisfy li(xi) = 1, and li(xj) = 0 for j i. It is easy enough to write down the li(x):

li(x) = (x-x0)(x-x1)...(x-xi-1)(x-xi+1)...(x-xn)
(xi-x0)(xi-x1)...(xi-xi-1)(xi-xi+1)...(xi-xn)
.
Notice that each li(x) is a degree n polynomial. Then, we can find p(x) via:
p(x) = f0l0(x) + f1l1(x) + ... +fnln(x).
Notice that p(xi) = f0.0+f1.0+... + fi-1.0+fi.1+fi+1.0+...+fn.0, which is equal to fi. When written in this way as a linear combination of the li(x), p(x) is called the Lagrange Interpolating Polynomial. It should be stressed, however, that it is exactly the same polynomial that would be obtained using the direct method. The LIP method is only order n2, so that doubling the number of points would only quadruple the number of operations. Therefore, for large n, this method is much faster than direct evaluation.

The Newton Divided Difference Interpolating Polynomial (NDDIP): Let Di,j, for i+j n, be defined as follows. Let Di,0 = fi, and let

Di,j = Di+1,j-1-Di,j-1
xi+j-xi
.
The half-matrix containing all the Di,j is called the Divided Difference Table, since each column (after column 0) is made up of differences between entries of the previous column, divided by differences between the xk values. Then, let p(x) be the polynomial defined by
p(x) = D0,0 + (x-x0)[ D0,1 + (x-x1)[ D0,2 + ...[ D0,n-1 + (x-xn-1)[ D0,n ]]...]].
It may not be obvious, but this p(x) is a degree n polynomial passing through all the points (x0,f0), (x1,f1), ..., (xn,fn). Equally non-obvious is the fact that this polynomial is exactly the same as that obtained either directly or using the LIP. It is called the Newton Divided Difference Interpolating Polynomial, and takes order n2 calculations to find. Although it is the same order as the LIP, it is faster, but only by a constant factor.

The DotPlacer Applet (on this site) allows you to place a set of points on the screen, and have it draw the interpolating polynomial through the points. You can even move the points around, and watch the curve change. Try it!

The algorithm used in the applet is the NDDIP method. To see examples of the three methods, follow this link. I have provided links to Mathworld in case you want to read more about the Lagrange Interpolating Polynomial.

If the above information is not helpful, you may like to consider the book displayed on the left. It is a somewhat technical book, but devoted entirely to polynomial interpolation in its many shapes and forms. It would be good for a person seeking to seriously apply just the polynomial interpolation method to a problem at hand. The book on the right, with code samples and good explanations, is regarded by many as one of the best books around for applying java (and smalltalk) to numerical methods.


File translated from TEX by TTH, version 2.25.