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):


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


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.