Divided differences

From Wikipedia, the free encyclopedia

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

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.

Definition[edit]

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[edit]

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[edit]

Divided differences for and the first few values of :

Thus, the table corresponding to these terms upto two columns has the following form:

Properties[edit]

  • 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[edit]

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[edit]

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.[2][3]

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[edit]

Expanded form[edit]

With the help of the polynomial function this can be written as

Peano form[edit]

If and , the divided differences can be expressed as[4]

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.

Forward and backward differences[edit]

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[5]

whereas for backward differences:[citation needed]

See also[edit]

References[edit]

  1. ^ Isaacson, Walter (2014). The Innovators. Simon & Schuster. p. 20. ISBN 978-1-4767-0869-0.
  2. ^ de Boor, Carl, Divided Differences, Surv. Approx. Theory 1 (2005), 46–69, [1]
  3. ^ Opitz, G. Steigungsmatrizen, Z. Angew. Math. Mech. (1964), 44, T52–T54
  4. ^ Skof, Fulvia (2011-04-30). Giuseppe Peano between Mathematics and Logic: Proceeding of the International Conference in honour of Giuseppe Peano on the 150th anniversary of his birth and the centennial of the Formulario Mathematico Torino (Italy) October 2-3, 2008. Springer Science & Business Media. p. 40. ISBN 978-88-470-1836-5.
  5. ^ Burden, Richard L.; Faires, J. Douglas (2011). Numerical Analysis (9th ed.). Cengage Learning. p. 129. ISBN 9780538733519.
  • Louis Melville Milne-Thomson (2000) [1933]. The Calculus of Finite Differences. American Mathematical Soc. Chapter 1: Divided Differences. ISBN 978-0-8218-2107-7.
  • Myron B. Allen; Eli L. Isaacson (1998). Numerical Analysis for Applied Science. John Wiley & Sons. Appendix A. ISBN 978-1-118-03027-1.
  • Ron Goldman (2002). Pyramid Algorithms: A Dynamic Programming Approach to Curves and Surfaces for Geometric Modeling. Morgan Kaufmann. Chapter 4:Newton Interpolation and Difference Triangles. ISBN 978-0-08-051547-2.

External links[edit]