# Divided differences

In mathematics, divided differences is an algorithm, historically used for computing tables of logarithms and trigonometric functions.[citation needed] Charles Babbage's difference engine, an early mechanical calculator, was designed to use this algorithm in its operation.[1]

Divided differences is a recursive division process. Given a sequence of data points ${\displaystyle (x_{0},y_{0}),\ldots ,(x_{n},y_{n})}$, the method calculates the coefficients of the interpolation polynomial of these points in the Newton form.

## Definition

Given n + 1 data points

${\displaystyle (x_{0},y_{0}),\ldots ,(x_{n},y_{n})}$

where the ${\displaystyle x_{k}}$ are assumed to be pairwise distinct, the forward divided differences are defined as:

${\displaystyle [y_{k}]:=y_{k},\qquad k\in \{0,\ldots ,n\}}$
${\displaystyle [y_{k},\ldots ,y_{k+j}]:={\frac {[y_{k+1},\ldots ,y_{k+j}]-[y_{k},\ldots ,y_{k+j-1}]}{x_{k+j}-x_{k}}},\qquad k\in \{0,\ldots ,n-j\},\ j\in \{1,\ldots ,n\}.}$

To make the recursive process of computation clearer, the divided differences can be put in tabular form, where the columns correspond to the value of j above, and each entry in the table is computed from the difference of the entries to its immediate lower left and to its immediate upper left, divided by a difference of corresponding x-values:

${\displaystyle {\begin{matrix}x_{0}&y_{0}=[y_{0}]&&&\\&&[y_{0},y_{1}]&&\\x_{1}&y_{1}=[y_{1}]&&[y_{0},y_{1},y_{2}]&\\&&[y_{1},y_{2}]&&[y_{0},y_{1},y_{2},y_{3}]\\x_{2}&y_{2}=[y_{2}]&&[y_{1},y_{2},y_{3}]&\\&&[y_{2},y_{3}]&&\\x_{3}&y_{3}=[y_{3}]&&&\\\end{matrix}}}$

### Notation

Note that the divided difference ${\displaystyle [y_{k},\ldots ,y_{k+j}]}$ depends on the values ${\displaystyle x_{k},\ldots ,x_{k+j}}$ and ${\displaystyle y_{k},\ldots ,y_{k+j}}$, but the notation hides the dependency on the x-values. If the data points are given by a function ƒ,

${\displaystyle (x_{0},f(x_{0})),\ldots ,(x_{k},f(x_{n}))}$

one sometimes writes

${\displaystyle f[x_{k},\ldots ,x_{k+j}]}$

for the divided difference

${\displaystyle [f(x_{k}),\ldots ,f(x_{k+j})]}$

Several other notations for the divided difference of the function ƒ on the nodes x0, ..., xn are also used, for instance:

${\displaystyle [x_{0},\ldots ,x_{n}]f,}$
${\displaystyle [x_{0},\ldots ,x_{n};f],}$
${\displaystyle D[x_{0},\ldots ,x_{n}]f}$

## Example

Divided differences for ${\displaystyle k=0}$ and the first few values of ${\displaystyle j}$:

{\displaystyle {\begin{aligned}{\mathopen {[}}y_{0}]&=y_{0}\\{\mathopen {[}}y_{0},y_{1}]&={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}\\{\mathopen {[}}y_{0},y_{1},y_{2}]&={\frac {{\mathopen {[}}y_{1},y_{2}]-{\mathopen {[}}y_{0},y_{1}]}{x_{2}-x_{0}}}={\frac {{\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}-{\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}}{x_{2}-x_{0}}}={\frac {y_{2}-y_{1}}{(x_{2}-x_{1})(x_{2}-x_{0})}}-{\frac {y_{1}-y_{0}}{(x_{1}-x_{0})(x_{2}-x_{0})}}\\{\mathopen {[}}y_{0},y_{1},y_{2},y_{3}]&={\frac {{\mathopen {[}}y_{1},y_{2},y_{3}]-{\mathopen {[}}y_{0},y_{1},y_{2}]}{x_{3}-x_{0}}}\end{aligned}}}

## Properties

${\displaystyle (f+g)[x_{0},\dots ,x_{n}]=f[x_{0},\dots ,x_{n}]+g[x_{0},\dots ,x_{n}]}$
${\displaystyle (\lambda \cdot f)[x_{0},\dots ,x_{n}]=\lambda \cdot f[x_{0},\dots ,x_{n}]}$
${\displaystyle (f\cdot g)[x_{0},\dots ,x_{n}]=f[x_{0}]\cdot g[x_{0},\dots ,x_{n}]+f[x_{0},x_{1}]\cdot g[x_{1},\dots ,x_{n}]+\dots +f[x_{0},\dots ,x_{n}]\cdot g[x_{n}]=\sum _{r=0}^{n}f[x_{0},\ldots ,x_{r}]\cdot g[x_{r},\ldots ,x_{n}]}$
• Divided differences are symmetric: If ${\displaystyle \sigma :\{0,\dots ,n\}\to \{0,\dots ,n\}}$ is a permutation then
${\displaystyle f[x_{0},\dots ,x_{n}]=f[x_{\sigma (0)},\dots ,x_{\sigma (n)}]}$
• Polynomial interpolation in the Newton form: if ${\displaystyle p}$ is a polynomial function of degree ${\displaystyle \leq n}$, then
${\displaystyle p(x)=p[x_{0}]+p[x_{0},x_{1}](x-x_{0})+p[x_{0},x_{1},x_{2}](x-x_{0})(x-x_{1})+\cdots +p[x_{0},\ldots ,x_{n}](x-x_{0})(x-x_{1})\cdots (x-x_{n-1})}$
• If ${\displaystyle p}$ is a polynomial function of degree ${\displaystyle , then
${\displaystyle p[x_{0},\dots ,x_{n}]=0.}$
${\displaystyle f[x_{0},\dots ,x_{n}]={\frac {f^{(n)}(\xi )}{n!}}}$ for a number ${\displaystyle \xi }$ in the open interval determined by the smallest and largest of the ${\displaystyle x_{k}}$'s.

## Matrix form

The divided difference scheme can be put into an upper triangular matrix:

${\displaystyle T_{f}(x_{0},\dots ,x_{n})={\begin{pmatrix}f[x_{0}]&f[x_{0},x_{1}]&f[x_{0},x_{1},x_{2}]&\ldots &f[x_{0},\dots ,x_{n}]\\0&f[x_{1}]&f[x_{1},x_{2}]&\ldots &f[x_{1},\dots ,x_{n}]\\0&0&f[x_{2}]&\ldots &f[x_{2},\dots ,x_{n}]\\\vdots &\vdots &&\ddots &\vdots \\0&0&0&\ldots &f[x_{n}]\end{pmatrix}}}$.

Then it holds

• ${\displaystyle T_{f+g}(x)=T_{f}(x)+T_{g}(x)}$
• ${\displaystyle T_{\lambda f}(x)=\lambda T_{f}(x)}$ if ${\displaystyle \lambda }$ is a scalar
• ${\displaystyle T_{f\cdot g}(x)=T_{f}(x)\cdot T_{g}(x)}$
This follows from the Leibniz rule. It means that multiplication of such matrices is commutative. Summarised, the matrices of divided difference schemes with respect to the same set of nodes x form a commutative ring.
• Since ${\displaystyle T_{f}(x)}$ is a triangular matrix, its eigenvalues are obviously ${\displaystyle f(x_{0}),\dots ,f(x_{n})}$.
• Let ${\displaystyle \delta _{\xi }}$ be a Kronecker delta-like function, that is
${\displaystyle \delta _{\xi }(t)={\begin{cases}1&:t=\xi ,\\0&:{\mbox{else}}.\end{cases}}}$
Obviously ${\displaystyle f\cdot \delta _{\xi }=f(\xi )\cdot \delta _{\xi }}$, thus ${\displaystyle \delta _{\xi }}$ is an eigenfunction of the pointwise function multiplication. That is ${\displaystyle T_{\delta _{x_{i}}}(x)}$ is somehow an "eigenmatrix" of ${\displaystyle T_{f}(x)}$: ${\displaystyle T_{f}(x)\cdot T_{\delta _{x_{i}}}(x)=f(x_{i})\cdot T_{\delta _{x_{i}}}(x)}$. However, all columns of ${\displaystyle T_{\delta _{x_{i}}}(x)}$ are multiples of each other, the matrix rank of ${\displaystyle T_{\delta _{x_{i}}}(x)}$ is 1. So you can compose the matrix of all eigenvectors of ${\displaystyle T_{f}(x)}$ from the ${\displaystyle i}$-th column of each ${\displaystyle T_{\delta _{x_{i}}}(x)}$. Denote the matrix of eigenvectors with ${\displaystyle U(x)}$. Example
${\displaystyle U(x_{0},x_{1},x_{2},x_{3})={\begin{pmatrix}1&{\frac {1}{(x_{1}-x_{0})}}&{\frac {1}{(x_{2}-x_{0})\cdot (x_{2}-x_{1})}}&{\frac {1}{(x_{3}-x_{0})\cdot (x_{3}-x_{1})\cdot (x_{3}-x_{2})}}\\0&1&{\frac {1}{(x_{2}-x_{1})}}&{\frac {1}{(x_{3}-x_{1})\cdot (x_{3}-x_{2})}}\\0&0&1&{\frac {1}{(x_{3}-x_{2})}}\\0&0&0&1\end{pmatrix}}}$
The diagonalization of ${\displaystyle T_{f}(x)}$ can be written as
${\displaystyle U(x)\cdot \operatorname {diag} (f(x_{0}),\dots ,f(x_{n}))=T_{f}(x)\cdot U(x)}$.

### Polynomials and power series

The matrix

${\displaystyle J={\begin{pmatrix}x_{0}&1&0&0&\cdots &0\\0&x_{1}&1&0&\cdots &0\\0&0&x_{2}&1&&0\\\vdots &\vdots &&\ddots &\ddots &\\0&0&0&0&\;\ddots &1\\0&0&0&0&&x_{n}\end{pmatrix}}}$

contains the divided difference scheme for the identity function with respect to the nodes ${\displaystyle x_{0},\dots ,x_{n}}$, thus ${\displaystyle J^{m}}$ contains the divided differences for the power function with exponent ${\displaystyle m}$. Consequently, you can obtain the divided differences for a polynomial function ${\displaystyle p}$ by applying ${\displaystyle p}$ to the matrix ${\displaystyle J}$: If

${\displaystyle p(\xi )=a_{0}+a_{1}\cdot \xi +\dots +a_{m}\cdot \xi ^{m}}$

and

${\displaystyle p(J)=a_{0}+a_{1}\cdot J+\dots +a_{m}\cdot J^{m}}$

then

${\displaystyle T_{p}(x)=p(J).}$

This is known as Opitz' formula.[2][3]

Now consider increasing the degree of ${\displaystyle p}$ to infinity, i.e. turn the Taylor polynomial into a Taylor series. Let ${\displaystyle f}$ be a function which corresponds to a power series. You can compute the divided difference scheme for ${\displaystyle f}$ by applying the corresponding matrix series to ${\displaystyle J}$: If

${\displaystyle f(\xi )=\sum _{k=0}^{\infty }a_{k}\xi ^{k}}$

and

${\displaystyle f(J)=\sum _{k=0}^{\infty }a_{k}J^{k}}$

then

${\displaystyle T_{f}(x)=f(J).}$

## Alternative characterizations

### Expanded form

{\displaystyle {\begin{aligned}f[x_{0}]&=f(x_{0})\\f[x_{0},x_{1}]&={\frac {f(x_{0})}{(x_{0}-x_{1})}}+{\frac {f(x_{1})}{(x_{1}-x_{0})}}\\f[x_{0},x_{1},x_{2}]&={\frac {f(x_{0})}{(x_{0}-x_{1})\cdot (x_{0}-x_{2})}}+{\frac {f(x_{1})}{(x_{1}-x_{0})\cdot (x_{1}-x_{2})}}+{\frac {f(x_{2})}{(x_{2}-x_{0})\cdot (x_{2}-x_{1})}}\\f[x_{0},x_{1},x_{2},x_{3}]&={\frac {f(x_{0})}{(x_{0}-x_{1})\cdot (x_{0}-x_{2})\cdot (x_{0}-x_{3})}}+{\frac {f(x_{1})}{(x_{1}-x_{0})\cdot (x_{1}-x_{2})\cdot (x_{1}-x_{3})}}+{\frac {f(x_{2})}{(x_{2}-x_{0})\cdot (x_{2}-x_{1})\cdot (x_{2}-x_{3})}}+\\&\quad \quad {\frac {f(x_{3})}{(x_{3}-x_{0})\cdot (x_{3}-x_{1})\cdot (x_{3}-x_{2})}}\\f[x_{0},\dots ,x_{n}]&=\sum _{j=0}^{n}{\frac {f(x_{j})}{\prod _{k\in \{0,\dots ,n\}\setminus \{j\}}(x_{j}-x_{k})}}\end{aligned}}}

With the help of the polynomial function ${\displaystyle \omega (\xi )=(\xi -x_{0})\cdots (\xi -x_{n})}$ this can be written as

${\displaystyle f[x_{0},\dots ,x_{n}]=\sum _{j=0}^{n}{\frac {f(x_{j})}{\omega '(x_{j})}}.}$

### Peano form

If ${\displaystyle x_{0} and ${\displaystyle n\geq 1}$, the divided differences can be expressed as[4]

${\displaystyle f[x_{0},\ldots ,x_{n}]={\frac {1}{(n-1)!}}\int _{x_{0}}^{x_{n}}f^{(n)}(t)\;B_{n-1}(t)\,dt}$

where ${\displaystyle f^{(n)}}$ is the ${\displaystyle n}$-th derivative of the function ${\displaystyle f}$ and ${\displaystyle B_{n-1}}$ is a certain B-spline of degree ${\displaystyle n-1}$ for the data points ${\displaystyle x_{0},\dots ,x_{n}}$, given by the formula

${\displaystyle B_{n-1}(t)=\sum _{k=0}^{n}{\frac {(\max(0,x_{k}-t))^{n-1}}{\omega '(x_{k})}}}$

This is a consequence of the Peano kernel theorem; it is called the Peano form of the divided differences and ${\displaystyle B_{n-1}}$ is the Peano kernel for the divided differences, all named after Giuseppe Peano.

### Forward differences

When the data points are equidistantly distributed we get the special case called forward differences. They are easier to calculate than the more general divided differences.

Given n+1 data points

${\displaystyle (x_{0},y_{0}),\ldots ,(x_{n},y_{n})}$

with

${\displaystyle x_{k}=x_{0}+kh,\ {\text{ for }}\ k=0,\ldots ,n{\text{ and fixed }}h>0}$

the forward differences are defined as

${\displaystyle \Delta ^{(0)}y_{k}:=y_{k},\qquad k=0,\ldots ,n}$
${\displaystyle \Delta ^{(j)}y_{k}:=\Delta ^{(j-1)}y_{k+1}-\Delta ^{(j-1)}y_{k},\qquad k=0,\ldots ,n-j,\ j=1,\dots ,n.}$

${\displaystyle {\begin{matrix}y_{0}&&&\\&\Delta y_{0}&&\\y_{1}&&\Delta ^{2}y_{0}&\\&\Delta y_{1}&&\Delta ^{3}y_{0}\\y_{2}&&\Delta ^{2}y_{1}&\\&\Delta y_{2}&&\\y_{3}&&&\\\end{matrix}}}$

The relationship between divided differences and forward differences is[5]

${\displaystyle [y_{0},y_{1},\ldots ,y_{n}]={\frac {1}{n!h^{n}}}\Delta ^{(n)}y_{0}.}$