divided difference table

In numerical work involving divided differences, 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:

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:

For convenience, introduce the notation ${\mathrm{\Delta }}_{ij}$ to denote the entry of the difference table at location $(i,j)$. Then, because of the recursion

$${\mathrm{\Delta }}^{n+1}f[x_0,x_1,\mathrm{\dots },x_{n+1}]=\frac{{\mathrm{\Delta }}^{n}f[x_1,x_2,\mathrm{\dots },x_{n+1}]-{\mathrm{\Delta }}^{n}f[x_0,x_1,\mathrm{\dots },x_n]}{x_{n+1}-x_0},$$

we have

${\mathrm{\Delta }}_{jj}$ $=f(x_j)$

${\mathrm{\Delta }}_{ij}$ $={\displaystyle \frac{{\mathrm{\Delta }}_{i-1j}-{\mathrm{\Delta }}_{ij-1}}{x_j-x_i}}.$

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 $f$ and $x_1$:

$f(x)$ $=x^2-4x+1$

$x_0$ $=2$

$x_1$ $=3$

$x_2$ $=5$

We may write down our first two columns:

Now, we start filling in the next column, starting with ${\mathrm{\Delta }}_{\mathrm{0\hspace{0.17em}1}}$. We take the difference of $-2$ and $-3$ and divide it by $x_1-x_0$. Since

$$\frac{(-2)-(-3)}{3-2}=\frac{1}{1}=1,$$

we have

Next we fill in the entry ${\mathrm{\Delta }}_{\mathrm{1\hspace{0.17em}2}}$. We take the difference of $6$ and $-2$ and divide it by $x_2-x_1$. Since

$$\frac{6-(-2)}{5-3}=\frac{8}{2}=4,$$

we have

Finally, we fill in the entry ${\mathrm{\Delta }}_{\mathrm{0\hspace{0.17em}2}}$. We take the difference of $4$ and $1$ and divide it by $x_2-x_0$. Since

$$\frac{4-1}{5-2}=\frac{3}{3}=1,$$

we have

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+x^2.$

Since $f$ is a second order 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