Divided differences

In mathematics divided differences is a recursive division process.

Definition

Given n data points

<math>(x_0, y_0),\ldots,(x_{n-1}, y_{n-1})<math>

the divided differences are defined as

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

<math>[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<math>

Notes

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

<math>(x_0, f(x_0)),\ldots,(x_{n-1}, f(x_{n-1}))<math>

we sometimes write

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

<math>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<math>

Example

For the first few [y_ν] this yields

<math>[y_0] = y_0<math>

<math>[y_0,y_1] = \frac{y_1-y_0}{x_1-x_0}<math>

<math>[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}<math>

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

<math>

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

Peano form

The divided differences can be expressed as

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

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.

Forward differences

When the data points are equidistantly distributed we get the special case called forward differences. They are easier to calculate then the more general divided differences.

Definition

Given n data points

<math>(x_0, y_0),\ldots,(x_{n-1}, y_{n-1})<math>

with

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

the divided differences can be calculated via forward differences defined as

<math>\triangle^{(0)}y_{i} := y_{i}<math>

<math>\triangle^{(k)}y_{i} := \triangle^{(k-1)}y_{i+1} – \triangle^{(k-1)}y_{i} \mbox{ , } k \ge 1<math>

Example

<math>

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

Application

The method of divided differences can be used to calculate the coefficients in the interpolation polynomial in the Newton form.