# 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:

 $\begin{matrix}x_{0}&f(x_{0})&&&\\ &&\Delta^{1}f[x_{0},x_{1}]&&\\ x_{1}&f(x_{1})&&\Delta^{2}f[x_{0},x_{1},x_{2}]&\\ &&\Delta^{1}f[x_{1},x_{2}]&&\Delta^{3}[x_{0},x_{1},x_{2}.x_{3}]\\ x_{2}&f(x_{2})&&\Delta^{2}f[x_{1},x_{2},x_{3}]&\vdots&\ddots\\ &&\Delta^{1}f[x_{2},x_{3}]&\vdots&\\ x_{3}&f(x_{3})&\vdots&&\\ \vdots&\vdots&&&\end{matrix}$

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:

 $\begin{matrix}*&(0,0)&&&&\\ *&&(0,1)&&&\\ *&(1,1)&&(0,2)&&\\ *&&(1,2)&&(0,3)&\\ *&(2,2)&&(1,3)&\vdots&\ddots\\ *&&(2,3)&\vdots&&\\ *&(3,3)&\vdots&&&\\ \vdots&\vdots&&&&\end{matrix}$

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

 $\Delta^{n+1}f[x_{0},x_{1},\ldots,x_{n+1}]={\Delta^{n}f[x_{1},x_{2},\ldots,x_{n% +1}]-\Delta^{n}f[x_{0},x_{1},\ldots,x_{n}]\over x_{n+1}-x_{0}},$

we have

 $\displaystyle\Delta_{jj}$ $\displaystyle=f(x_{j})$ $\displaystyle\Delta_{ij}$ $\displaystyle={\Delta_{i-1\,j}-\Delta_{i\,j-1}\over 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}$:

 $\displaystyle f(x)$ $\displaystyle=x^{2}-4x+1$ $\displaystyle x_{0}$ $\displaystyle=2$ $\displaystyle x_{1}$ $\displaystyle=3$ $\displaystyle x_{2}$ $\displaystyle=5$

We may write down our first two columns:

 $\begin{matrix}2&-3\\ \\ 3&-2\\ \\ 5&6\end{matrix}$

Now, we start filling in the next column, starting with $\Delta_{0\,1}$. We take the difference of $-2$ and $-3$ and divide it by $x_{1}-x_{0}$. Since

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

we have

 $\begin{matrix}2&-3&\\ &&1\\ 3&-2&\\ &&\\ 5&6&\end{matrix}\qquad.$

Next we fill in the entry $\Delta_{1\,2}$. We take the difference of $6$ and $-2$ and divide it by $x_{2}-x_{1}$. Since

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

we have

 $\begin{matrix}2&-3&\\ &&1\\ 3&-2&\\ &&4\\ 5&6&\end{matrix}\qquad.$

Finally, we fill in the entry $\Delta_{0\,2}$. We take the difference of $4$ and $1$ and divide it by $x_{2}-x_{0}$. Since

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

we have

 $\begin{matrix}2&-3&&\\ &&1&\\ 3&-2&&1\\ &&4&\\ 5&6&&\end{matrix}\qquad.$

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

 $\displaystyle f(x)$ $\displaystyle=-3+(x-2)+(x-2)(x-3)$ $\displaystyle=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 DividedDifferenceTable 2013-03-22 16:48:33 2013-03-22 16:48:33 rspuzio (6075) rspuzio (6075) 15 rspuzio (6075) Definition msc 39A70