divided differences

Given n + 1 data points

$$(x\_0,\; y\_0),\backslash ldots,(x\_\{n\},\; y\_\{n\})$$

where the $x\_k$ are assumed to be pairwise distinct, the forward divided differences are defined as:

$$\backslash begin\{align\}$$

\mathopen[y_k] &:= y_k, && k \in \{ 0,\ldots,n\} \\

\mathopen[y_k,\ldots,y_{k+j}] &:= \frac{[y_{k+1},\ldots , y_{k+j}] - [y_{k},\ldots , y_{k+j-1}]}{x_{k+j}-x_k}, && k\in\{0,\ldots,n-j\},\ j\in\{1,\ldots,n\}.

\end{align}

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:

\begin{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}

Note that the divided difference $[y\_k,\backslash ldots,y\_\{k+j\}]$ depends on the values $x\_k,\backslash ldots,x\_\{k+j\}$ and $y\_k,\backslash 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),\; \backslash ldots,\; (x\_\{k\},\; 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,\backslash ldots,x\_\{k+j\}]$$

\ \stackrel{\text{def}}= \ [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,\backslash ldots,x\_\{k+j\}]=\backslash mathopen[x\_0,\backslash ldots,x\_n]f=$$

\mathopen[x_0,\ldots,x_n;f]=

D[x_0,\ldots,x_n]f.

Divided differences for $k=0$ and the first few values of $j$:

\begin{align}

\mathopen[y_0] &= y_0 \\

\mathopen[y_0,y_1] &= \frac{y_1-y_0}{x_1-x_0} \\

\mathopen[y_0,y_1,y_2]

&= \frac{\mathopen[y_1,y_2]-\mathopen[y_0,y_1]}{x_2-x_0}

= \frac{\frac{y_2-y_1}{x_2-x_1}-\frac{y_1-y_0}{x_1-x_0}}{x_2-x_0}

= \frac{y_2-y_1}{(x_2-x_1)(x_2-x_0)}-\frac{y_1-y_0}{(x_1-x_0)(x_2-x_0)}

\\

\mathopen[y_0,y_1,y_2,y_3] &= \frac{\mathopen[y_1,y_2,y_3]-\mathopen[y_0,y_1,y_2]}{x_3-x_0}

\end{align}

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

$$\backslash begin\{matrix\}$$

x_0 & y_{0} & & \\

& & {y_{1}-y_{0}\over x_1 - x_0} & \\

x_1 & y_{1} & & {{y_{2}-y_{1}\over x_2 - x_1}-{y_{1}-y_{0}\over x_1 - x_0} \over x_2 - x_0} \\

& & {y_{2}-y_{1}\over x_2 - x_1} & \\

x_2 & y_{2} & & \vdots \\

& & \vdots & \\

\vdots & & & \vdots \\

& & \vdots & \\

x_n & y_{n} & & \\

\end{matrix}

• Linearity $$\backslash begin\{align\}$$

(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{align}

• Leibniz rule $$(f\backslash cdot\; g)[x\_0,\backslash dots,x\_n]\; =\; f[x\_0]\backslash cdot\; g[x\_0,\backslash dots,x\_n]\; +\; f[x\_0,x\_1]\backslash cdot\; g[x\_1,\backslash dots,x\_n]\; +\; \backslash dots\; +\; f[x\_0,\backslash dots,x\_n]\backslash cdot\; g[x\_n]\; =\; \backslash sum\_\{r=0\}^n\; f[x\_0,\backslash ldots,x\_r]\backslash cdot\; g[x\_r,\backslash ldots,x\_n]$$
• Divided differences are symmetric: If $\backslash sigma\; :\; \backslash \{0,\; \backslash dots,\; n\backslash \}\; \backslash to\; \backslash \{0,\; \backslash dots,\; n\backslash \}$ is a permutation then $$f[x\_0,\; \backslash dots,\; x\_n]\; =\; f[x\_\{\backslash sigma(0)\},\; \backslash dots,\; x\_\{\backslash sigma(n)\}]$$
• Polynomial interpolation in the Newton form: if $P$ is a polynomial function of degree $\backslash leq\; n$, and $p[x\_0,\; \backslash dots\; ,\; x\_n]$ is the divided difference, then $$P\_\{n-1\}(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)\; +\; \backslash cdots\; +\; p[x\_0,\backslash ldots,x\_n]\; (x-x\_0)(x-x\_1)\backslash cdots(x-x\_\{n-1\})$$
• If $p$ is a polynomial function of degree
• Mean value theorem for divided differences: if $f$ is n times differentiable, then $$f[x\_0,\backslash dots,x\_n]\; =\; \backslash frac\{f^\{(n)\}(\backslash xi)\}\{n!\}$$ for a number $\backslash xi$ in the open interval determined by the smallest and largest of the $x\_k$'s.

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

$$T\_f(x\_0,\backslash dots,x\_n)=$$

\begin{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] \\

0 & 0 & f[x_2] & \ldots & f[x_2,\dots,x_n] \\

\vdots & \vdots & & \ddots & \vdots \\

0 & 0 & 0 & \ldots & f[x_n]

\end{pmatrix}.

Then it holds

• $T\_\{f+g\}(x)\; =\; T\_f(x)\; +\; T\_g(x)$
• $T\_\{\backslash lambda\; f\}(x)\; =\; \backslash lambda\; T\_f(x)$ if $\backslash lambda$ is a scalar
• $T\_\{f\backslash cdot\; g\}(x)\; =\; T\_f(x)\; \backslash cdot\; T\_g(x)$ {{pb}} 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),\; \backslash dots,\; f(x\_n)$.
• Let $\backslash delta\_\backslash xi$ be a Kronecker delta-like function, that is $$\backslash delta\_\backslash xi(t)\; =\; \backslash begin\{cases\}$$

1 &: t=\xi , \\

0 &: \mbox{else}.

\end{cases} Obviously $f\backslash cdot\; \backslash delta\_\backslash xi\; =\; f(\backslash xi)\backslash cdot\; \backslash delta\_\backslash xi$, thus $\backslash delta\_\backslash xi$ is an eigenfunction of the pointwise function multiplication. That is $T\_\{\backslash delta\_\{x\_i\}\}(x)$ is somehow an "eigenmatrix" of $T\_f(x)$: $T\_f(x)\; \backslash cdot\; T\_\{\backslash delta\_\{x\_i\}\}\; (x)\; =\; f(x\_i)\; \backslash cdot\; T\_\{\backslash delta\_\{x\_i\}\}(x)$. However, all columns of $T\_\{\backslash delta\_\{x\_i\}\}(x)$ are multiples of each other, the matrix rank of $T\_\{\backslash delta\_\{x\_i\}\}(x)$ is 1. So you can compose the matrix of all eigenvectors of $T\_f(x)$ from the $i$-th column of each $T\_\{\backslash delta\_\{x\_i\}\}(x)$. Denote the matrix of eigenvectors with $U(x)$. Example $$U(x\_0,x\_1,x\_2,x\_3)\; =\; \backslash begin\{pmatrix\}$$

1 & \frac{1}{(x_1-x_0)} & \frac{1}{(x_2-x_0) (x_2-x_1)} & \frac{1}{(x_3-x_0) (x_3-x_1) (x_3-x_2)} \\

0 & 1 & \frac{1}{(x_2-x_1)} & \frac{1}{(x_3-x_1) (x_3-x_2)} \\

0 & 0 & 1 & \frac{1}{(x_3-x_2)} \\

0 & 0 & 0 & 1

\end{pmatrix} The diagonalization of $T\_f(x)$ can be written as $$U(x)\; \backslash cdot\; \backslash operatorname\{diag\}(f(x\_0),\backslash dots,f(x\_n))\; =\; T\_f(x)\; \backslash cdot\; U(x)\; .$$

The matrix

J =

\begin{pmatrix}

x_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{pmatrix}

contains the divided difference scheme for the identity function with respect to the nodes $x\_0,\backslash dots,x\_n$, thus $J^m$ contains the divided differences for the power function with exponent $m$.

Consequently, you can obtain the divided differences for a polynomial function $p$ by applying $p$ to the matrix $J$: If

$$p(\backslash xi)\; =\; a\_0\; +\; a\_1\; \backslash cdot\; \backslash xi\; +\; \backslash dots\; +\; a\_m\; \backslash cdot\; \backslash xi^m$$

and

$$p(J)\; =\; a\_0\; +\; a\_1\backslash cdot\; J\; +\; \backslash dots\; +\; a\_m\backslash cdot\; J^m$$

then

$$T\_p(x)\; =\; p(J).$$

This is known as Opitz' formula.de Boor, Carl, Divided Differences, Surv. Approx. Theory 1 (2005), 46–69, [http://www.emis.de/journals/SAT/papers/2/]Opitz, G. Steigungsmatrizen, Z. Angew. Math. Mech. (1964), 44, T52–T54

Now consider increasing the degree of $p$ to infinity, i.e. turn the Taylor polynomial into a Taylor series.

Let $f$ be a function which corresponds to a power series.

You can compute the divided difference scheme for $f$ by applying the corresponding matrix series to $J$:

If

$$f(\backslash xi)\; =\; \backslash sum\_\{k=0\}^\backslash infty\; a\_k\; \backslash xi^k$$

and

$$f(J)=\backslash sum\_\{k=0\}^\backslash infty\; a\_k\; J^k$$

then

$$T\_f(x)=f(J).$$

\begin{align}

f[x_0] &= f(x_0) \\

f[x_0,x_1] &= \frac{f(x_0)}{(x_0-x_1)} + \frac{f(x_1)}{(x_1-x_0)} \\

f[x_0,x_1,x_2] &= \frac{f(x_0)}{(x_0-x_1)\cdot(x_0-x_2)} + \frac{f(x_1)}{(x_1-x_0)\cdot(x_1-x_2)} + \frac{f(x_2)}{(x_2-x_0)\cdot(x_2-x_1)} \\

f[x_0,x_1,x_2,x_3] &= \frac{f(x_0)}{(x_0-x_1)\cdot(x_0-x_2)\cdot(x_0-x_3)} + \frac{f(x_1)}{(x_1-x_0)\cdot(x_1-x_2)\cdot(x_1-x_3)} +\\

&\quad\quad \frac{f(x_2)}{(x_2-x_0)\cdot(x_2-x_1)\cdot(x_2-x_3)} + \frac{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} \frac{f(x_j)}{\prod_{k\in\{0,\dots,n\}\setminus\{j\}} (x_j-x_k)}

\end{align}

With the help of the polynomial function $\backslash omega(\backslash xi)\; =\; (\backslash xi-x\_0)\; \backslash cdots\; (\backslash xi-x\_n)$ this can be written as

f[x_0,\dots,x_n] = \sum_{j=0}^{n} \frac{f(x_j)}{\omega'(x_j)}.

If

$$f[x\_0,\backslash ldots,x\_n]\; =\; \backslash frac\{1\}\{(n-1)!\}\; \backslash int\_\{x\_0\}^\{x\_n\}\; f^\{(n)\}(t)\backslash ;B\_\{n-1\}(t)\; \backslash ,\; dt$$

where $f^\{(n)\}$ is the $n$-th derivative of the function $f$ and $B\_\{n-1\}$ is a certain B-spline of degree $n-1$ for the data points $x\_0,\backslash dots,x\_n$, given by the formula

$$B\_\{n-1\}(t)\; =\; \backslash sum\_\{k=0\}^n\; \backslash frac\{(\backslash max(0,x\_k-t))^\{n-1\}\}\{\backslash omega\text{'}(x\_k)\}$$

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.

{{details|Finite difference}}

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),\; \backslash ldots,\; (x\_n,\; y\_n)$$

with

$$x\_\{k\}\; =\; x\_0\; +\; k\; h,\backslash \; \backslash text\{\; for\; \}\; \backslash \; k=0,\backslash ldots,n\; \backslash text\{\; and\; fixed\; \}\; h>0$$

the forward differences are defined as

$$\backslash begin\{align\}$$

\Delta^{(0)} y_k &:= y_k,\qquad k=0,\ldots,n \\

\Delta^{(j)}y_k &:= \Delta^{(j-1)}y_{k+1} - \Delta^{(j-1)}y_k,\qquad k=0,\ldots,n-j,\ j=1,\dots,n.

\end{align}whereas the backward differences are defined as:

$$\backslash begin\{align\}$$

\nabla^{(0)} y_k &:= y_k,\qquad k=0,\ldots,n \\

\nabla^{(j)}y_k &:= \nabla^{(j-1)}y_{k} - \nabla^{(j-1)}y_{k-1},\qquad k=0,\ldots,n-j,\ j=1,\dots,n.

\end{align}

Thus the forward difference table is written as:$$$$

\begin{matrix}

y_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{matrix}

whereas the backwards difference table is written as:$$$$

\begin{matrix}

y_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{matrix}

The relationship between divided differences and forward differences is{{cite book|last1=Burden|first1=Richard L.| last2=Faires|first2=J. Douglas | title=Numerical Analysis |url=https://archive.org/details/numericalanalysi00rlbu |url-access=limited | date=2011|page=[https://archive.org/details/numericalanalysi00rlbu/page/n146 129]|publisher=Cengage Learning | isbn=9780538733519| edition=9th}}

$$[y\_j,\; y\_\{j+1\},\; \backslash ldots\; ,\; y\_\{j+k\}]\; =\; \backslash frac\{1\}\{k!h^k\}\backslash Delta^\{(k)\}y\_j,$$whereas for backward differences:{{Citation needed|date=December 2023}}$$[\{y\}\_\{j\},\; y\_\{j-1\},\backslash ldots,\{y\}\_\{j-k\}]\; =\; \backslash frac\{1\}\{k!h^k\}\backslash nabla^\{(k)\}y\_j.$$

• Difference quotient
• Neville's algorithm
• Polynomial interpolation
• Mean value theorem for divided differences
• Nörlund–Rice integral
• Pascal's triangle

{{Reflist|1}}

• {{cite book|author=Louis Melville Milne-Thomson|author-link=L. M. Milne-Thomson| title=The Calculus of Finite Differences | year=2000|orig-year=1933| publisher=American Mathematical Soc.| isbn=978-0-8218-2107-7|at=Chapter 1: Divided Differences}}
• {{cite book|author1=Myron B. Allen|author2=Eli L. Isaacson| title=Numerical Analysis for Applied Science | year=1998|publisher=John Wiley & Sons|isbn=978-1-118-03027-1| at=Appendix A}}
• {{cite book|author=Ron Goldman|title=Pyramid Algorithms: A Dynamic Programming Approach to Curves and Surfaces for Geometric Modeling|year=2002| publisher=Morgan Kaufmann| isbn=978-0-08-051547-2| at=Chapter 4:Newton Interpolation and Difference Triangles}}

• An [http://code.henning-thielemann.de/htam/src/Numerics/Interpolation/DividedDifference.hs implementation] in Haskell.

Category:Finite differences

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