divided difference table

In numerical work involving divided differences, whencomputing the divided differences of a tabulatedfunction, it is convenient to arrange the divideddifferences of a function $f$ in a table like so:

The arrangement of this table makes it easy to computethe divided differences. Also, once such a table hasbeen computed, one can read off the coefficients in thedivided difference interpolation formula as the topentries in the various columns.

To explain the computation, as well as to program it on acomputer, it is convenient to label the locations in ourtable with pairs of integers like so:

For convenience, introduce the notation ${\mathrm{\Delta }}_{ij}$ todenote 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 divideddifference table as follows: The first and second column arejust the tabulation of our function, so we may write themdown immediately. Then we fill out the table one column at atime by using the formula.

Let us illustrate with a simple example. Consider the followingchoices 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 differenceinterpolation formula reads

$f(x)$$=-3+(x-2)+(x-2)(x-3)$

$=1-4x+x^2.$

Since $f$ is a second order polynomial, this interpolationto second order is exact. There is no remainder and, uponsimplifying the expression, we recover our original polynomial.