divided difference table


In numerical work involving divided differencesMathworldPlanetmath, when computing the divided differences of a tabulated function, it is convenient to arrange the divided differences of a function f in a table like so:

x0f(x0)Δ1f[x0,x1]x1f(x1)Δ2f[x0,x1,x2]Δ1f[x1,x2]Δ3[x0,x1,x2.x3]x2f(x2)Δ2f[x1,x2,x3]Δ1f[x2,x3]x3f(x3)

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:

*(0,0)*(0,1)*(1,1)(0,2)*(1,2)(0,3)*(2,2)(1,3)*(2,3)*(3,3)

For convenience, introduce the notation Δij to denote the entry of the difference table at location (i,j). Then, because of the recursion

Δn+1f[x0,x1,,xn+1]=Δnf[x1,x2,,xn+1]-Δnf[x0,x1,,xn]xn+1-x0,

we have

Δjj =f(xj)
Δij =Δi-1j-Δij-1xj-xi.

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 formulaMathworldPlanetmathPlanetmath.

Let us illustrate with a simple example. Consider the following choices for f and x1:

f(x) =x2-4x+1
x0 =2
x1 =3
x2 =5

We may write down our first two columns:

2-33-256

Now, we start filling in the next column, starting with Δ0 1. We take the differencePlanetmathPlanetmath of -2 and -3 and divide it by x1-x0. Since

(-2)-(-3)3-2=11=1,

we have

2-313-256  .

Next we fill in the entry Δ1 2. We take the difference of 6 and -2 and divide it by x2-x1. Since

6-(-2)5-3=82=4,

we have

2-313-2456  .

Finally, we fill in the entry Δ0 2. We take the difference of 4 and 1 and divide it by x2-x0. Since

4-15-2=33=1,

we have

2-313-21456  .

Thus, we have constructed our difference table. The top entries in the columns are -3,1,1 so, as per our earlier remark, the divided difference interpolation formula reads

f(x) =-3+(x-2)+(x-2)(x-3)
=1-4x+x2.

Since f is a second orderPlanetmathPlanetmath polynomial, this interpolation to second order is exact. There is no remainder and, upon simplifying the expression, we recover our original polynomial.

Title divided difference table
Canonical name DividedDifferenceTable
Date of creation 2013-03-22 16:48:33
Last modified on 2013-03-22 16:48:33
Owner rspuzio (6075)
Last modified by rspuzio (6075)
Numerical id 15
Author rspuzio (6075)
Entry type Definition
Classification msc 39A70