DIVIDED DIFFERENCES

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

Contents

Definition

Notation

Example

Properties

Matrix form

Alternative definitions

Expanded form

Partial fractions

Peano form

Taylor form

First order

Higher order

Polynomials and power series

Forward differences

Definition

Example

See also

Definition

Given ''n'' data points
:$(x\_0,\; y\_0),ldots,(x\_\{n-1\},\; y\_\{n-1\})$
the 'divided differences' are defined as
:$[y\_\{$
u}] := y_{
u} qquad mbox{ , }
u in { 0,ldots,n-1}
:$[y\_\{$
u},ldots,y_{
u+j}] := rac{[y_{
u+1},ldots y_{
u+j}] - [y_{
u},ldots y_{
u+j-1}]}{x_{
u+j}-x_{
u}} qquad mbox{ , }
uin{0,ldots,n-j}, jin{1,ldots,n-1}.

Notation

If the data points are given as a function $f$
:$(x\_0,\; f(x\_0)),ldots,(x\_\{n-1\},\; f(x\_\{n-1\}))$
we sometimes write
:$f[x\_\{$
u}] := f(x_{
u}) qquad mbox{ , }
u in { 0,ldots,n-1 }
:$f[x\_\{$
u},ldots,x_{
u+j}] := rac{f[x_{
u+1},ldots x_{
u+j}] - f[x_{
u},ldots x_{
u+j-1}]}{x_{
u+j}-x_{
u}} qquad mbox{ , }
uin{0,ldots,n-j}, jin{1,ldots,n-1}.
Several notations for the divided difference of the function $f$ on the knots $x\_0,ldots,x\_n$ are used:

★ $[x\_0,ldots,x\_n]f$,

★ $[x\_0,ldots,x\_n;f]$,

★ $D[x\_0,ldots,x\_n]f$ etc.

Example

For the first few $[y\_\{$
u}] this yields
:$$
egin{array}{lcl}
[y_0] &=& y_0 \
[y_0,y_1] &=& rac{y_1-y_0}{x_1-x_0} \
[y_0,y_1,y_2] &=& rac{rac{y_2-y_1}{x_2-x_1}-rac{y_1-y_0}{x_1-x_0}}{x_2-x_0} \
end{array}

To make the recursive process more clear the divided differences can be put in a tabular form
:$$
egin{matrix}
x_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{matrix}

Properties

★ Linearity
:: $(f+g)[x\_0,dots,x\_n]\; =\; f[x\_0,dots,x\_n]\; +\; g[x\_0,dots,x\_n]$
:: $(lambdacdot\; f)[x\_0,dots,x\_n]\; =\; lambdacdot\; f[x\_0,dots,x\_n]$

★ Leibniz rule
:: $(fcdot\; 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]$

★ From the mean value theorem for divided differences it follows that
::

Matrix form

The divided difference scheme can be put into an upper triangular matrix.
Let $T\_f(x\_0,dots,x\_n)=$
egin{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] \
dots & ddots & ddots & ddots & dots \
0 & ldots & 0 & 0 & f[x_n]
end{pmatrix}.
Then it holds

★ $T\_\{f+g\}\; x\; =\; T\_f\; x\; +\; T\_g\; x$

★ $T\_\{fcdot\; g\}\; x\; =\; T\_f\; x\; cdot\; 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 form a commutative ring.

★ Since $T\_f\; x$ is a triangular matrix, its eigenvalues are obviously $f(x\_0),\; dots,\; f(x\_n)$.

★ Let $delta\_xi$ be a Kronecker delta-like function, that is . Obviously $fcdot\; delta\_xi\; =\; f(xi)cdot\; delta\_xi$, thus $delta\_xi$ is an eigenfunction of the pointwise function multiplication. That is $T\_\{delta\_\{x\_i\}\}\; x$ is somehow an "eigenmatrix" of $T\_f\; x$: $T\_f\; x\; cdot\; T\_\{delta\_\{x\_i\}\}\; x\; =\; f(x\_i)\; cdot\; T\_\{delta\_\{x\_i\}\}\; x$. However, all columns of $T\_\{delta\_\{x\_i\}\}\; x$ are multiples of each other, the matrix rank of $T\_\{delta\_\{x\_i\}\}\; x$ is 1. So you can compose the matrix of all eigenvectors from the $i$-th column of each $T\_\{delta\_\{x\_i\}\}\; x$. Denote the matrix of eigenvectors with $U\; x$. Example
:
1 & rac{1}{(x1-x0)} & rac{1}{(x2-x0)cdot(x2-x1)} & rac{1}{(x3-x0)cdot(x3-x1)cdot(x3-x2)} \
0 & 1 & rac{1}{(x2-x1)} & rac{1}{(x3-x1)cdot(x3-x2)} \
0 & 0 & 1 & rac{1}{(x3-x2)} \
0 & 0 & 0 & 1
end{pmatrix}
:The diagonalization of $T\_f\; x$ can be written as
:$U\; x\; cdot\; operatorname\{diag\}(f(x\_0),dots,f(x\_n))\; =\; T\_f\; x\; cdot\; U\; x$.

Alternative definitions

Expanded form

$$
egin{array}{lcl}
f[x_0] &=& f(x_0) \
f[x_0,x_1] &=& rac{f(x_0)}{(x_0-x_1)} + rac{f(x_1)}{(x_1-x_0)} \
f[x_0,x_1,x_2] &=& rac{f(x_0)}{(x_0-x_1)cdot(x_0-x_2)} + rac{f(x_1)}{(x_1-x_0)cdot(x_1-x_2)} + rac{f(x_2)}{(x_2-x_0)cdot(x_2-x_1)} \
f[x_0,x_1,x_2,x_3] &=& rac{f(x_0)}{(x_0-x_1)cdot(x_0-x_2)cdot(x_0-x_3)} + rac{f(x_1)}{(x_1-x_0)cdot(x_1-x_2)cdot(x_1-x_3)} + rac{f(x_2)}{(x_2-x_0)cdot(x_2-x_1)cdot(x_2-x_3)} + rac{f(x_3)}{(x_3-x_0)cdot(x_3-x_1)cdot(x_3-x_2)} \
f[x_0,dots,x_n] &=&
sum_{j=0}^{n} rac{f(x_j)}{prod_{kin{0,dots,n}setminus{j}} (x_j-x_k)}
end{array}

With help of a polynomial function $q$ with $q(xi)\; =\; (xi-x\_1)cdot\; dots\; cdot(xi-x\_n)$
this can be written as
:$$
f[x_0,dots,x_n] = sum_{j=0}^{n} rac{f(x_j)}{q'(x_j)}
.

Partial fractions

You can represent partial fractions using the expanded form of divided differences.
(This does not simplify computation, but is interesting in itself.)
If $p$ and $q$ are polynomial functions,
where
and $q$ is given in terms of linear factors by $q(xi)\; =\; (xi-x\_1)cdot\; dots\; cdot(xi-x\_n)$,
then it follows from partial fraction decomposition that
:
ight)[x_1,dots,x_n]
If limits of the divided differences are accepted,
then this connection does also hold, if some of the $x\_j$ coincide.
If $f$ is a polynomial function with arbitrary degree
and it is decomposed by $f(x)\; =\; p(x)\; +\; q(x)cdot\; d(x)$ using polynomial division of $f$ by $q$,
then it holds
:
ight)[x_1,dots,x_n].

Peano form

The divided differences can be expressed as
:
where $B\_\{n-1\}$ is a B-spline of degree $n-1$ for the data points $x\_0,dots,x\_n$ and $f^\{(n)\}$ is the $n$-th derivative of the function $f$.
This is called the 'Peano form' of the divided differences and $B\_\{n-1\}$ is called the Peano kernel for the divided differences, both named after Giuseppe Peano.

Taylor form

First order

If nodes are cumulated, then the numerical computation of the divided differences is inaccurate, because you divide almost two zeros, each of which with a high relative error due to differences of similar values.
However we know, that difference quotients approximate the derivative and vice versa:
: for
This approximation can be turned into an identity whenever Taylor's theorem applies.
:
:
You can eliminate the odd powers of $y-x$ by expanding the Taylor series at the center between $x$ and $y$:
:$x\; =\; m-h,\; y=m+h$, that is
:
:
:
f'(m) + f'(m)cdotrac{h^2}{3!} + dots

Higher order

The Taylor series or any other representation with function series
can in principle be used to approximate divided differences.
Taylor series are infinite sums of power functions.
The mapping from a function $f$ to a divided difference $f[x\_0,dots,x\_n]$ is a linear functional.
We can as well apply this functional to the function summands.
Express power notation with an ordinary function: $p\_n(x)\; =\; x^n$
Regular Taylor series is a weighted sum of power functions:
Taylor series for divided differences:
We know that the first $n$ terms vanish,
because we have a higher difference order than polynomial order,
and in the following term the divided difference is one:
:$$
egin{array}{llcl}
orall j & p_n[x_0,dots,x_n] &=& 1 \
& p_{n+1}[x_0,dots,x_n] &=& x_0 + dots + x_n \
& p_{n+m}[x_0,dots,x_n] &=& sum_{ain{0,dots,n}^m ext{ with } a_1 le a_2 le dots le a_m} prod_{jin a} x_j \
end{array}

It follows that the Taylor series for the divided difference essentially starts with

which is also a simple approximation of the divided difference,
according to the mean value theorem for divided differences.
If we would have to compute the divided differences for the power functions
in the usual way, we would encounter the same numerical problems
that we had when computing the divided difference of $f$.
The nice thing is, that there is a simpler way.
It holds
:$$
t^n = (1 - x_0cdot t) dots cdot (1 - x_ncdot t) cdot
(p_0[x_0,dots,x_n] + p_1[x_0,dots,x_n]cdot t + p_2[x_0,dots,x_n]cdot t^2 + dots) .

Consequently we can compute the divided differences of $p\_n$
by a division of formal power series.
See how this reduces to the successive computation of powers
when we compute $p\_n[h]$ for several $n$.
Cf. an implementation in Haskell.
If you need to compute a whole divided difference scheme with respect to a Taylor series,
see the section about divided differences of power series.

Polynomials and power series

Divided differences of polynomials are particularly interesting, because they can benefit from the Leibniz rule.
The matrix $J$ with
:$$
J=
egin{pmatrix}
x_0 & 1 & 0 & 0 & cdots & 0 \
0 & x_1 & 1 & 0 & cdots & 0 \
0 & 0 & x_2 & 1 & & 0 \
dots & dots & & ddots & ddots & \
0 & 0 & 0 & 0 & & x_n
end{pmatrix}

contains the divided difference scheme for the identity function with respect to the nodes $x\_0,dots,x\_n$,
thus $J^n$ contains the divided differences for the power function with exponent $n$.
Consequently you can obtain the divided differences for a polynomial function
with respect to the polynomial $p$
by applying $p$ (more precisely: its corresponding matrix polynomial function ) to the matrix $J$.
:
:
::
arphi(p)[x_0] & arphi(p)[x_0,x_1] & arphi(p)[x_0,x_1,x_2] & ldots & arphi(p)[x_0,dots,x_n] \
0 & arphi(p)[x_1] & arphi(p)[x_1,x_2] & ldots & arphi(p)[x_1,dots,x_n] \
dots & ddots & ddots & ddots & dots \
0 & ldots & 0 & 0 & arphi(p)[x_n]
end{pmatrix}

Now consider increasing the degree of $p$ to infinity,
i.e. turn the Taylor polynomial to a Taylor series.
Let $f$ be a function which corresponds to a power series.
You can compute a divided difference scheme by computing the according matrix series applied to $J$.
If the nodes $x\_0,dots,x\_n$ are all equal,
then $J$ is a Jordan block and
computation boils down to generalizing a scalar function to a matrix function using Jordan decomposition.

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

Definition

Given ''n'' data points
:$(x\_0,\; y\_0),ldots,(x\_\{n-1\},\; y\_\{n-1\})$
with
:$x\_\{$
u} = x_0 +
u h mbox{ , } h > 0 mbox{ , }
u=0,ldots,n-1
the divided differences can be calculated via 'forward differences' defined as
:$riangle^\{(0)\}y\_\{i\}\; :=\; y\_\{i\}$
:$riangle^\{(k)\}y\_\{i\}\; :=\; riangle^\{(k-1)\}y\_\{i+1\}\; -\; riangle^\{(k-1)\}y\_\{i\}\; mbox\{\; ,\; \}\; k\; ge\; 1.$

Example

:$$
egin{matrix}
y_0 & & & \
& riangle y_0 & & \
y_1 & & riangle^{2} y_0 & \
& riangle y_1 & & riangle^{3} y_0\
y_2 & & riangle^{2} y_1 & \
& riangle y_2 & & \
y_3 & & & \
end{matrix}

See also

★ Polynomial interpolation

★ Mean value theorem for divided differences