Divided difference

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

Divided differences is a recursive division process. The method can be used to calculate the coefficients in the interpolation polynomial in the Newton form.

Given k+1 data points

The forward divided differences are defined as:

The backward divided differences are defined as:

If the data points are given as a function ƒ,

one sometimes writes

Several notations for the divided difference of the function ƒ on the nodes x₀, ..., x_n are used:

etc.

For the first few values of ${\displaystyle \nu }$, this yields:

To make the recursive process more clear, the divided differences can be put in a tabular form:

The divided difference scheme can be put into an upper triangular matrix. Let ${\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}]\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\ldots &f[x_{n}]\end{pmatrix}}}$.

...
Wikipedia