Divided differences

From Wikipedia, the free encyclopedia

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.

1 Definition
2 Notes
3 Example
4 Peano form
5 Forward differences
- 5.1 Definition
- 5.2 Example
6 See also

[edit] Definition

Given n data points

$(x_0, y_0),\ldots,(x_{n-1}, y_{n-1})$

the divided differences are defined as

$[y_{\nu}] := y_{\nu} \qquad \mbox{ , } \nu = 0,\ldots,n-1$

$[y_{\nu},\ldots,y_{\nu+j}] := \frac{[y_{\nu+1},\ldots y_{\nu+j}] - [y_{\nu},\ldots y_{\nu+j-1}]}{x_{\nu+j}-x_{\nu}} \qquad \mbox{ , } \nu = 0,\ldots,n-j,j=1,\ldots,n-1.$

[edit] Notes

If the data points are given as a function f(x)

$(x_0, f(x_0)),\ldots,(x_{n-1}, f(x_{n-1}))$

we sometimes write

$f[x_{\nu}] := f(x_{\nu}) \qquad \mbox{ , } \nu = 0,\ldots,n-1$

$f[x_{\nu},\ldots,x_{\nu+j}] := \frac{f[x_{\nu+1},\ldots x_{\nu+j}] - f[x_{\nu},\ldots x_{\nu+j-1}]}{x_{\nu+j}-x_{\nu}} \qquad \mbox{ , } \nu = 0,\ldots,n-j,j=1,\ldots,n-1.$

[edit] Example

For the first few [y_ν] this yields

[y 0] = y 0

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

$[y_0,y_1,y_2] = \frac{\frac{y_2-y_1}{x_2-x_1}-\frac{y_1-y_0}{x_1-x_0}}{x_2-x_0}.$

To make the recursive process more clear the divided differences can be put in a tabular form

$\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}$

[edit] Peano form

The divided differences can be expressed as

$f[x_0,\ldots,x_n] = \frac{1}{n!} \int_{x_0}^{x_n} f^{(n)}(t)B_{n-1}(t) \, dt$

where B_n-1 is a B-spline of degree n-1 for the data points x₀,...,x_n and f⁽ⁿ⁾(x) is the n derivative of the function f(x).

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.

[edit] Forward differences

For more details on this topic, see 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.

[edit] Definition

Given n data points

$(x_0, y_0),\ldots,(x_{n-1}, y_{n-1})$

with

$x_{\nu} = x_0 + \nu h \mbox{ , } h > 0 \mbox{ , } \nu=0,\ldots,n-1$

the divided differences can be calculated via forward differences defined as

$\triangle^{(0)}y_{i} := y_{i}$

$\triangle^{(k)}y_{i} := \triangle^{(k-1)}y_{i+1} - \triangle^{(k-1)}y_{i} \mbox{ , } k \ge 1.$

[edit] Example

$\begin{matrix} y_0 & & & \\ & \triangle y_0 & & \\ y_1 & & \triangle^{2} y_0 & \\ & \triangle y_1 & & \triangle^{3} y_0\\ y_2 & & \triangle^{2} y_1 & \\ & \triangle y_2 & & \\ y_3 & & & \\ \end{matrix}$