divided difference table
The arrangement of this table makes it easy to compute the divided differences. Also, once such a table has been computed, one can read off the coefficients in the divided difference interpolation formula as the top entries in the various columns.
To explain the computation, as well as to program it on a computer, it is convenient to label the locations in our table with pairs of integers like so:
Using these formulae, we may systematically compute the divided difference table as follows: The first and second column are just the tabulation of our function, so we may write them down immediately. Then we fill out the table one column at a time by using the formula.
Let us illustrate with a simple example. Consider the following choices for and :
We may write down our first two columns:
Now, we start filling in the next column, starting with . We take the difference of and and divide it by . Since
Next we fill in the entry . We take the difference of and and divide it by . Since
Finally, we fill in the entry . We take the difference of and and divide it by . Since
Thus, we have constructed our difference table. The top entries in the columns are so, as per our earlier remark, the divided difference interpolation formula reads