6.3 Divided Differences We can use the notation f [ x i , x j ] to represent the first divided difference:
For the second divided difference:
In general, we can define the n th divided difference recursively:
although they can be computed more efficiently by starting with the first divided differences, then computing the second, then the third, and so on. Now, here's our payoff. For a polynomial interpolation functions in Newton form, we have
Thus, an interpolating line is
and an interpolating parabola is
Adding another data point means we simply compute and add another term to the interpolation function. The data points do not have to be in any particular order, nor do they need to be spaced evenly along the x axis. We can visualize the computation of divided differences using a divided difference table, as shown in Table 6-1. Table 6-1. A divided difference table showing the first through the fourth divided differences for a function f ( x ) and five data points x , x 1 , x 2 , x 3 , and x 4 . The gray shading shows an example of how to "fan back" diagonally from a divided difference to see how it is recursively defined and to determine its denominator:
|
Top |