divided difference

Let $f$ be a real (or complex) function. Given distinct real (or complex) numbers $x_0,x_1,x_2,\mathrm{\dots }$, the divided differences of $f$ are defined recursively as follows:

${\mathrm{\Delta }}^{1}f[x_0,x_1]$$={\displaystyle \frac{f(x_1)-f(x_0)}{x_1-x_0}}$

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

It is also convenient to define the zeroth divided difference of$f$ to be $f$ itself:

$${\mathrm{\Delta }}^{0}f[x_0]=f[x_0]$$

Some important properties of divided differences are:

1. Divided differences are invariant under permutations of $x_0,x_1,x_2,\mathrm{\dots }$

2. If $f$ is a polynomial of order $m$ and , then the $n$-th divided differences of $f$ vanish identically

3. If $f$ is a polynomial of order $m+n$, then ${\mathrm{\Delta }}^n(x,x_1,\mathrm{\dots },x_n)$ is a polynomial in $x$ of order $m$.

Divided differences are useful for interpolating functions when the values are given for unequally spaced values of the argument.

Becuse of the first property listed above, it does not matter withrespect to which two arguments we compute the divided differencewhen we compute the $n+1$-st divided difference from the $n$-thdivided difference. For instance, when computing the divideddifference table for tabulated values of a function, a convenientchoice is the following:

$${\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}$$