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. Given a sequence of data points , the method calculates the coefficients of the interpolation polynomial of these points in the Newton form.
It is sometimes denoted by a delta with a bar: or .
Definition Given n + 1 data points
where the are assumed to be pairwise distinct, the forward divided differences are defined as:
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:
Notation Note that the divided difference depends on the values and , but the notation hides the dependency on the x-values. If the data points are given by a function f,
one sometimes writes the divided difference in the notation Other notations for the divided difference of the function ƒ on the nodes x0, ..., xn are:
Example
Divided differences for and the first few values of :
Thus, the table corresponding to these terms up to two columns has the following form:
Properties Linearity Leibniz rule Divided differences are symmetric: If is a permutation then Polynomial interpolation in the Newton form: if is a polynomial function of degree , and is the divided difference, then If is a polynomial function of degree , then Mean value theorem for divided differences: if is n times differentiable, then for a number in the open interval determined by the smallest and largest of the 's.
Matrix form The divided difference scheme can be put into an upper triangular matrix:
Then it holds
if 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. Since is a triangular matrix, its eigenvalues are obviously . Let be a Kronecker delta-like function, that is Obviously , thus is an eigenfunction of the pointwise function multiplication. That is is somehow an "eigenmatrix" of : . However, all columns of are multiples of each other, the matrix rank of is 1. So you can compose the matrix of all eigenvectors of from the -th column of each . Denote the matrix of eigenvectors with . Example The diagonalization of can be written as
Polynomials and power series The matrix
contains the divided difference scheme for the identity function with respect to the nodes , thus contains the divided differences for the power function with exponent . Consequently, you can obtain the divided differences for a polynomial function by applying to the matrix : If
and
then
This is known as Opitz' formula.de Boor, Carl, Divided Differences, Surv. Approx. Theory 1 (2005), 46–69, Opitz, G. Steigungsmatrizen, Z. Angew. Math. Mech. (1964), 44, T52–T54
Now consider increasing the degree of to infinity, i.e. turn the Taylor polynomial into a Taylor series. Let be a function which corresponds to a power series. You can compute the divided difference scheme for by applying the corresponding matrix series to : If
and
then
Alternative characterizations
Expanded form
With the help of the polynomial function this can be written as
Peano form If and , the divided differences can be expressed as
where is the -th derivative of the function and is a certain B-spline of degree for the data points , given by the formula
This is a consequence of the Peano kernel theorem; it is called the Peano form of the divided differences and is the Peano kernel for the divided differences, all named after Giuseppe Peano.
Hermite–Genocchi formula When is times continuously differentiable on a convex domain containing the nodes , including the confluent case of repeated nodes in arbitrary order (see ), the divided difference can be expressed as an integral over a -simplex :
where
is the -simplex.
Cauchy's integral formula When is analytic on a simply connected domain containing the nodes , including the confluent case of repeated nodes in arbitrary order (see ), the divided difference admits a contour integral representation via Cauchy's integral formula:
where is a positively oriented, simple closed contour in enclosing all the nodes .
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+1 data points
with
the forward differences are defined as:
whereas the backward differences are defined as:
Thus the forward difference table is written as:
whereas the backwards difference table is written as:
The relationship between divided differences and forward differences is whereas for backward differences:
Explicit formula
When the data points are equispaced we can also derive an explicit formula for . For any fixed and such that ,
Proof. We prove this by induction on :
Base case: Let and . Then by definition , and
Induction step: Assume the above formula holds until and consider such that . 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
where when . We obtain our thesis for by substituting the identity
Generalization When some of the nodes coincide, the recursive definition of standard divided differences involves division by zero and can no longer be applied directly. In this confluent case, divided differences are extended by taking a limit, which incorporates higher-order derivatives of the function . The resulting values are known as confluent divided differences or generalized divided differences. Conceptually, node confluence bridges discrete divided differences and continuous calculus, replacing finite differences with exact higher-order derivatives as nodes coalesce.
Let (or ) consist of nodes with arbitrary repetitions and order. Suppose there are distinct values among the nodes, with corresponding multiplicities such that .
Assuming is times continuously differentiable on an open domain in (or ) containing the nodes, the confluent divided difference is defined as the limit:
where consists of pairwise distinct nodes converging to .
The computation of confluent divided differences in general can be simplified in two steps: first considering adjacent repeated nodes, and then extending to arbitrary permutations of repeated nodes.
Adjacent repeated nodes Consider the case where identical nodes in are grouped contiguously:
In this case, the divided difference table is constructed using the standard recursive formula whenever the outer nodes are distinct. When evaluating divided differences on identical nodes , applying the limit definition directly causes the limit to reduce to and coincide with a scaled higher-order derivative of :
All other entries in the divided difference table are then computed using the standard recursive rule.
Arbitrary permutations of repeated nodes For an arbitrary list of nodes where repeated nodes are not necessarily adjacent, let be a permutation that reorders such that identical nodes become contiguous. Denote the permuted vector of nodes as .
Let be a vector of pairwise distinct nodes, and let denote the corresponding permuted vector. Because divided differences for distinct nodes are invariant under node permutation:
and the times continuous differentiability of ensures that the standard divided difference as a mapping is continuous on the domain of distinct nodes, taking the limit as and yields two limits that agree:
This establishes that confluent divided differences inherit the node permutation invariance property of standard divided differences.
In practice, any confluent divided difference with arbitrarily ordered repeated nodes can be computed by first permuting the node sequence so that identical nodes are adjacent, and then constructing the divided difference table using the derivative substitution rule above.
Generalized case example To evaluate a confluent divided difference with non-adjacent repeated nodes, such as , the node sequence is first permuted to group identical nodes contiguously:
The evaluation then proceeds by constructing the divided difference table:
Extracting and simplifying the rightmost entry from the resulting divided difference table yields:
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