Java Number Cruncher: The Java Programmers Guide to Numerical Computing

If we are given two data points in the xy plane, there is one, and only one, polynomial interpolation function f ₁ ( x ) of degree 1 that will pass through both points a line function.

As shown in Figure 6-2, let the two points be ( x , f ₁ ( x )) and ( x ₁ , f ₁ ( x ₁ )). Then, using similar triangles , we have

and so

Notice that we have derived the Newton form of the polynomial

where the coefficients b = f ₁ ( x ) and b ₁ = the quantity in the square brackets. The quantity in the square brackets is called a divided difference, and it happens to be the slope of the line. As we'll soon see, divided differences play a major computational role in determining polynomial interpolation functions.

If there are three points in the xy plane, then there is a polynomial interpolation function f ₂ ( x ) of degree 2 that will pass through all three points. This is a quadratic function, which describes a parabola. Although we won't prove it here, this parabola is unique for any three given points.

The Newton form of the parabola is

where the centers x and x ₁ are the x coordinates of two of our three given points. The coefficients b _i are constant their values are the same for any value of x. So to compute b , first set x to the value x to get rid of the terms containing b ₁ and b ₂ , and we see that

Now set x to the value x ₁ to get rid of the term containing b ₂ and substitute in the value we just computed for b :

and so

Finally, set x to the center value x ₂ (the x coordinate of the third point) and substitute in the values for b and b ₁ :

Subtract f ₂ ( x ₁ ) from both sides:

But since

we have

Divide both sides by ( x ₂ - x ₁ ), and we get

and finally

Notice that the values of b and b ₁ are similar to the corresponding values we had computed for the first degree polynomial. The definition of b ₂ is recursive it's a divided difference that is composed of two divided differences.

In general, if we are given n +1 points, then there exists a unique polynomial function f _n ( x ) of degree n that passes through all the points.