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):
|
|
The Newton Divided Difference Interpolating Polynomial (NDDIP): Let Di,j, for i+j £ n, be defined as follows. Let Di,0 = fi, and let
|
|
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.