The Interpolatory Polynomial

Given a set of n+1 points (x₀,f₀),...,(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₀+a₁x+a₂x²+...+a_nxⁿ, then substituting the points (x₀,f₀), (x₁,f₁), etc into p(x) gives a system of n+1 equations for the n+1 unknown coefficients a₀,a₁,...,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³. 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³), or örder n³".

The Lagrange Interpolating Polynomial (LIP): Given x₀,x₁,...,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) =

(x-x₀)(x-x₁)...(x-x_i-1)(x-x_i+1)...(x-x_n)

(x_i-x₀)(x_i-x₁)...(x_i-x_i-1)(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₀l₀(x) + f₁l₁(x) + ... +f_nl_n(x).

Notice that p(x_i) = f₀.0+f₁.0+... + f_i-1.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², 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,j-1-D_i,j-1

x_i+j-x_i

The half-matrix 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 + (x-x₀)[ D_0,1 + (x-x₁)[ D_0,2 + ...[ D_0,n-1 + (x-x_n-1)[ D_0,n ]]...]].

It may not be obvious, but this p(x) is a degree n polynomial passing through all the points (x₀,f₀), (x₁,f₁), ..., (x_n,f_n). 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 n² 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_EX by T_TH, version 2.25.