Divided differences explained

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.^[1]

Divided differences is a recursive division process. Given a sequence of data points

(x_0,y_0),\ldots,(x_n,y_n)

, the method calculates the coefficients of the interpolation polynomial of these points in the Newton form.

Definition

Given n + 1 data points $(x_0, y_0),\ldots,(x_, y_)$ where the

x_k

are assumed to be pairwise distinct, the forward divided differences are defined as:

\begin\mathopen[y_k] &:= y_k, && k \in \ \\\mathopen[y_k,\ldots,y_{k+j}] &:= \frac, && k\in\,\ j\in\.\end

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: $\beginx_0 & y_0 = [y_0] & & & \\ & & [y_0,y_1] & & \\x_1 & y_1 = [y_1] & & [y_0,y_1,y_2] & \\ & & [y_1,y_2] & & [y_0,y_1,y_2,y_3]\\x_2 & y_2 = [y_2] & & [y_1,y_2,y_3] & \\ & & [y_2,y_3] & & \\x_3 & y_3 = [y_3] & & & \\\end$

Notation

Note that the divided difference

[y_k,\ldots,y_k+j]

depends on the values

x_k,\ldots,x_k+j

and

y_k,\ldots,y_k+j

, but the notation hides the dependency on the x-values. If the data points are given by a function f,

(x_0, y_0), \ldots, (x_, y_n)=(x_0, f(x_0)), \ldots, (x_n, f(x_n))

one sometimes writes the divided difference in the notation

f[x_k,\ldots,x_{k+j}]\ \stackrel= \ [f(x_k),\ldots,f(x_{k+j})] = [y_k,\ldots,y_{k+j}].

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

f[x_k,\ldots,x_{k+j}]=\mathopen[x_0,\ldots,x_n]f= \mathopen[x_0,\ldots,x_n;f]=D[x_0,\ldots,x_n]f.

Example

Divided differences for

k=0

and the first few values of

\begin \mathopen[y_0] &= y_0 \\ \mathopen[y_0,y_1] &= \frac \\ \mathopen[y_0,y_1,y_2]&= \frac = \frac = \frac-\frac\\ \mathopen[y_0,y_1,y_2,y_3] &= \frac\end

Thus, the table corresponding to these terms upto two columns has the following form: $\begin x_0 & y_ & & \\ & & & \\ x_1 & y_ & & \\ & & & \\ x_2 & y_ & & \vdots \\ & & \vdots & \\\vdots & & & \vdots \\ & & \vdots & \\ x_n & y_ & & \\\end$

Properties

Linearity $\begin$

(f+g)[x_0,\dots,x_n] &= f[x_0,\dots,x_n] + g[x_0,\dots,x_n] \\(\lambda\cdot f)[x_0,\dots,x_n] &= \lambda\cdot f[x_0,\dots,x_n]\end

Leibniz rule $(f\cdot g)[x_0,\dots,x_n] = f[x_0]\cdot g[x_0,\dots,x_n] + f[x_0,x_1]\cdot g[x_1,\dots,x_n] + \dots + f[x_0,\dots,x_n]\cdot g[x_n] = \sum_^n f[x_0,\ldots,x_r]\cdot g[x_r,\ldots,x_n]$
Divided differences are symmetric: If

\sigma:\{0,...,n\}\to\{0,...,n\}

is a permutation then

f[x_0, \dots, x_n] = f[x_{\sigma(0)}, \dots, x_{\sigma(n)}]

Polynomial interpolation in the Newton form: if

is a polynomial function of degree

\leqn

, and

p[x_0,...,x_n]

is the divided difference, then

P_(x) = p[x_0] + p[x_0,x_1](x-x_0) + p[x_0,x_1,x_2](x-x_0)(x-x_1) + \cdots + p[x_0,\ldots,x_n] (x-x_0)(x-x_1)\cdots(x-x_)

is a polynomial function of degree

, then

p[x_0, \dots, x_n] = 0.

Mean value theorem for divided differences

is n times differentiable, then

f[x_0,\dots,x_n] = \frac

for a number

\xi

in the open interval determined by the smallest and largest of the

x_k

's.

Matrix form

The divided difference scheme can be put into an upper triangular matrix: $T_f(x_0,\dots,x_n)=\beginf[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] \\0 & 0 & f[x_2] & \ldots & f[x_2,\dots,x_n] \\\vdots & \vdots & & \ddots & \vdots \\0 & 0 & 0 & \ldots & f[x_n]\end.$

Then it holds

T_f+g(x)=T_f(x)+T_g(x)

T_λ(x)=λT_f(x)

is a scalar

T_{f ⋅}(x)=T_f(x) ⋅ T_g(x)

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

T_f(x)

is a triangular matrix, its eigenvalues are obviously

f(x_0),...,f(x_n)

\delta_\xi

be a Kronecker delta-like function, that is

\delta_\xi(t) = \begin1 &: t=\xi, \\0 &: \mbox.\end

Obviously

f ⋅ \delta_\xi=f(\xi) ⋅ \delta_\xi

, thus

\delta_\xi

is an eigenfunction of the pointwise function multiplication. That is

\delta
	x_i

(x)

is somehow an "eigenmatrix" of

T_f(x)

T_f(x) ⋅

\delta
	x_i

(x)=f(x_i) ⋅

\delta
	x_i

(x)

. However, all columns of

\delta
	x_i

(x)

are multiples of each other, the matrix rank of

\delta
	x_i

(x)

is 1. So you can compose the matrix of all eigenvectors of

T_f(x)

from the

-th column of each

\delta
	x_i

(x)

. Denote the matrix of eigenvectors with

U(x)

. Example

U(x_0,x_1,x_2,x_3) = \begin1 & \frac & \frac & \frac \\0 & 1 & \frac & \frac \\0 & 0 & 1 & \frac \\0 & 0 & 0 & 1\end

The diagonalization of

T_f(x)

can be written as

U(x) \cdot \operatorname(f(x_0),\dots,f(x_n)) = T_f(x) \cdot U(x) .

Polynomials and power series

The matrix $J =\beginx_0 & 1 & 0 & 0 & \cdots & 0 \\0 & x_1 & 1 & 0 & \cdots & 0 \\0 & 0 & x_2 & 1 & & 0 \\\vdots & \vdots & & \ddots & \ddots & \\0 & 0 & 0 & 0 & \; \ddots & 1\\0 & 0 & 0 & 0 & & x_n\end$ contains the divided difference scheme for the identity function with respect to the nodes

x_0,...,x_n

, thus

J^m

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

p(\xi) = a_0 + a_1 \cdot \xi + \dots + a_m \cdot \xi^m

and

p(J) = a_0 + a_1\cdot J + \dots + a_m\cdot J^m

then

T_p(x) = p(J).

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

f(\xi) = \sum_^\infty a_k \xi^k

and

f(J)=\sum_^\infty a_k J^k

then

T_f(x)=f(J).

Alternative characterizations

Expanded form

$\beginf[x_0] &= f(x_0) \\f[x_0,x_1] &= \frac + \frac \\f[x_0,x_1,x_2] &= \frac + \frac + \frac \\f[x_0,x_1,x_2,x_3] &= \frac + \frac +\\&\quad\quad \frac + \frac \\f[x_0,\dots,x_n] &=\sum_^ \frac\end$

\omega(\xi)=(\xi-x₀₎ … (\xi-x_n)

this can be written as

f[x_0,\dots,x_n] = \sum_^ \frac.

Peano form

x_0<x_{1< … <x}_n

and

n\geq1

, the divided differences can be expressed as^[4]

f[x_0,\ldots,x_n] = \frac \int_^ f^(t)\;B_(t) \, dt

where

f⁽ⁿ⁾

is the

-th derivative of the function

and

B_n-1

is a certain B-spline of degree

n-1

for the data points

x_0,...,x_n

, given by the formula

B_(t) = \sum_^n \frac

This is a consequence of the Peano kernel theorem; it is called the Peano form of the divided differences and

B_n-1

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+1 data points $(x_0, y_0), \ldots, (x_n, y_n)$ with $x_ = x_0 + k h,\ \text \ k=0,\ldots,n \text h>0$ the forward differences are defined as $\begin\Delta^ y_k &:= y_k,\qquad k=0,\ldots,n \\\Delta^y_k &:= \Delta^y_ - \Delta^y_k,\qquad k=0,\ldots,n-j,\ j=1,\dots,n.\end$ whereas the backward differences are defined as: $\begin\nabla^ y_k &:= y_k,\qquad k=0,\ldots,n \\\nabla^y_k &:= \nabla^y_ - \nabla^y_,\qquad k=0,\ldots,n-j,\ j=1,\dots,n.\end$ Thus the forward difference table is written as: $\beginy_0 & & & \\ & \Delta y_0 & & \\y_1 & & \Delta^2 y_0 & \\ & \Delta y_1 & & \Delta^3 y_0\\y_2 & & \Delta^2 y_1 & \\ & \Delta y_2 & & \\y_3 & & & \\\end$ whereas the backwards difference table is written as: $\beginy_0 & & & \\ & \nabla y_1 & & \\y_1 & & \nabla^2 y_2 & \\ & \nabla y_2 & & \nabla^3 y_3\\y_2 & & \nabla^2 y_3 & \\ & \nabla y_3 & & \\y_3 & & & \\\end$

The relationship between divided differences and forward differences is^[5] $[y_j, y_{j+1}, \ldots, y_{j+k}] = \frac\Delta^y_j,$ whereas for backward differences: $[{y}_{j}, y_{j-1},\ldots,{y}_{j-k}] = \frac\nabla^y_j.$

References

Book: Louis Melville Milne-Thomson. L. M. Milne-Thomson. The Calculus of Finite Differences . 2000. 1933. American Mathematical Soc.. 978-0-8218-2107-7. Chapter 1: Divided Differences.
Book: Myron B. Allen. Eli L. Isaacson. Numerical Analysis for Applied Science . 1998. John Wiley & Sons. 978-1-118-03027-1. Appendix A.
Book: Ron Goldman. Pyramid Algorithms: A Dynamic Programming Approach to Curves and Surfaces for Geometric Modeling. 2002. Morgan Kaufmann. 978-0-08-051547-2. Chapter 4:Newton Interpolation and Difference Triangles.

External links

An implementation in Haskell.

Notes and References

Book: Isaacson . Walter . The Innovators . 2014 . Simon & Schuster . 978-1-4767-0869-0 . 20 .
[Carl de Boor|de Boor, Carl]
Opitz, G. Steigungsmatrizen, Z. Angew. Math. Mech. (1964), 44, T52–T54
Book: Skof, Fulvia . 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 . 2011-04-30 . Springer Science & Business Media . 978-88-470-1836-5 . 40 . en.
Book: Burden. Richard L.. Faires. J. Douglas . Numerical Analysis . limited . 2011. 129. Cengage Learning . 9780538733519. 9th.

Divided differences explained

Definition

Notation

Example

Properties

Matrix form

Polynomials and power series

Alternative characterizations

Expanded form

Peano form

Forward and backward differences

See also

References

External links

Notes and References