divided difference

A running average-of-slopes built recursively from data points, written f[x0,...,xk] -- the building block of Newton's interpolating-polynomial form.

The divided differences of $f$ at nodes $x_0,\ldots,x_n$ are defined recursively: the zeroth divided difference is $f[x_i]=f(x_i)$ , and each higher one is $f[x_i,\ldots,x_{i+k}]=\frac{f[x_{i+1},\ldots,x_{i+k}]-f[x_i,\ldots,x_{i+k-1}]}{x_{i+k}-x_i}.$ These are exactly the coefficients of Newton's divided-difference form of the interpolating polynomial, and they are built once, in a triangular table, regardless of which form the polynomial is eventually written in.

Examples

For $(0,1),(1,3),(2,7)$ : $f[x_0]=1$ , $f[x_0,x_1]=\dfrac{3-1}{1-0}=2$ , $f[x_0,x_1,x_2]=\dfrac{4-2}{2-0}=1$ (using $f[x_1,x_2]=\dfrac{7-3}{2-1}=4$ ).