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, the method calculates the coefficients of the interpolation polynomial of these points in the Newton form.

.

Definition

Given n+ are assumed to be pairwise distinct, the forward divided differences

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-

Notation

, but the notation hides the dependency on the x-values. If the data points are given by a function fOther notations for the divided difference of the function on the nodes x0,...,xn

Example

Properties

• Linearity

• Leibniz rule

• Polynomial interpolation in the Newton form

• Mean value theorem for divided differences is n's.

Matrix form

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

Then it holds

• is a scalar

• 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.

• is a triangular matrix, its eigenvalues.

• be a Kronecker delta is an eigenfunction is somehow an "eigenmatrix are multiples of each other, the matrix rank The diagonalization

Polynomials and power series

contains the divided difference scheme for the identity function contains the divided differences for the power function with exponent. Consequently, you can obtain the divided differences for a polynomial function This is known as Opitz' formula.

to infinity, i.e. turn the Taylor polynomial into a Taylor series be a function which corresponds to a power series

Alternative characterizations

Expanded form

With the help of the polynomial function

Peano form

, the divided differences can be expressed as-th derivative is a certain B-spline

This is a consequence of the Peano kernel theorem; it is called the Peano form is the Peano kernel for the divided differences, all named after Giuseppe Peano.

Forward and backward 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 Thus the forward difference

The relationship between divided differences and forward differences iswhereas for backward differences:

Explicit formula

Proof.:

Base case:

Induction step:. By the recursive definition we have

We can use our inductive hypothesis on both members of the left side, and obtain

This can be rearranged as

See also

• Difference quotient

• Neville's algorithm

• Polynomial interpolation

• Mean value theorem for divided differences

• Nörlund–Rice integral

• Pascal's triangle

• Lagrange polynomial

References

External links

• An implementation in Haskell.

de:Polynominterpolation#Bestimmung der Koeffizienten: Schema der dividierten Differenzen