
The Interpolatory Polynomial
Given a set of n+1 points (x_{0},f_{0}),...,(x_{n},f_{n}), 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) = a_{0}+a_{1}x+a_{2}x^{2}+...+a_{n}x^{n}, then substituting the points
(x_{0},f_{0}), (x_{1},f_{1}), etc into p(x) gives a system of n+1 equations
for the n+1 unknown coefficients a_{0},a_{1},...,a_{n}. 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 n^{3}. 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(n^{3}), or örder n^{3}".
The Lagrange Interpolating Polynomial (LIP): Given x_{0},x_{1},...,x_{n},
we can define special polynomials l_{i}(x) which satisfy l_{i}(x_{i}) = 1, and
l_{i}(x_{j}) = 0 for j � i. It is easy enough to write down the l_{i}(x):
l_{i}(x) = 
(xx_{0})(xx_{1})...(xx_{i1})(xx_{i+1})...(xx_{n}) (x_{i}x_{0})(x_{i}x_{1})...(x_{i}x_{i1})(x_{i}x_{i+1})...(x_{i}x_{n})

. 

Notice that each l_{i}(x) is a degree n polynomial. Then, we can find
p(x) via:
p(x) = f_{0}l_{0}(x) + f_{1}l_{1}(x) + ... +f_{n}l_{n}(x). 

Notice that p(x_{i}) = f_{0}.0+f_{1}.0+... + f_{i1}.0+f_{i}.1+f_{i+1}.0+...+f_{n}.0, which is
equal to f_{i}. When written in this way as a linear combination of the
l_{i}(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 n^{2}, 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 D_{i,j}, for i+j � n, be defined as follows. Let D_{i,0} = f_{i},
and let
D_{i,j} = 
D_{i+1,j1}D_{i,j1} x_{i+j}x_{i}

. 

The halfmatrix containing all the D_{i,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 x_{k} values.
Then, let p(x) be the polynomial defined by
p(x) = D_{0,0} + (xx_{0})[ D_{0,1} + (xx_{1})[ D_{0,2} + ...[ D_{0,n1} + (xx_{n1})[ D_{0,n} ]]...]]. 

It may not be obvious, but this p(x) is a degree n polynomial passing
through all the points (x_{0},f_{0}), (x_{1},f_{1}), ..., (x_{n},f_{n}). Equally
nonobvious 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
n^{2} 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 T_{E}X by T_{T}H, version 2.25.
