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):
Notice that each li(x) is a degree n polynomial. Then, we can find
li(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.
p(x) = f0l0(x) + f1l1(x) + ... +fnln(x).|
The Newton Divided Difference Interpolating Polynomial (NDDIP):
Let Di,j, for i+j � n, be defined as follows. Let Di,0 = fi,
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
Di,j = ||
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.
p(x) = D0,0 + (x-x0)[ D0,1 + (x-x1)[ D0,2 + ...[ D0,n-1 + (x-xn-1)[ D0,n ]]...]].|
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
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.