Divided Differences

So far we have looked at polynomial interpolation using the Lagrange Formula $P_n(x) = y_0L_0(x) + y_1L_1(x) + ... + y_nL_n(x)$ for interpolating the $n + 1$ distinct points $(x_0, y_0)$, $(x_1, y_1)$, …, $(x_n, y_n)$. We will now look at another way to obtain these interpolation polynomials using divided differences. The first order divided difference of $f(x)$ with respect to the distinct numbers $x_0$ and $x_1$ is denoted by $f[x_0, x_1]$ and is given by the following formula:

(1)

\begin{align} f[x_0, x_1] = \frac{f(x_1) - f(x_0)}{x_1 - x_0} \end{align}

Note that if $f$ is differentiable on an interval $[a, b]$ and $x_0, x_1 \in [a, b]$ then by the Mean Value Theorem, there exists a $\xi \in (a, b)$ such that $f'(\xi) = \frac{f(x_1) - f(x_0)}{x_1 - x_0}$ which implies that $f[x_0, x_1] = f'(\xi)$. Furthermore, if $x_0$ and $x_1$ are close together, then $\xi \approx \frac{x_0 + x_1}{2}$ and so:

(2)

\begin{align} f[x_0, x_1] \approx f' \left ( \frac{x_0 + x_1}{2} \right ) \end{align}

Higher order divided differences are defined recursively. If $x_0$, $x_1$, and $x_2$ are distinct numbers, then the second order divided difference is given by:

(3)

\begin{align} \quad f[x_0, x_1, x_2] = \frac{f[x_1, x_2] - f[x_0, x_1]}{x_2 - x_0} \end{align}

We define the divided difference of order $n$ below.

Definition: Let $y = f(x)$ be a function and let $x_0$, $x_1$, …, $x_n$ be $n + 1$ distinct numbers. Then the Divided Difference of Order $n$ is $f[x_0, x_1, ..., x_n] = \frac{f[x_1, x_2, ..., x_n] - f[x_0, x_1, ..., x_{n-1}]}{x_n - x_0}$.

Another name for the Divided Difference is the "Newton's Divided Difference".

We will now observe a very important property regarding divided differences which says the order of the numbers $x_0$, $x_1$, …, $x_n$ does not matter.

Lemma 1: Let $y = f(x)$ be a function and let $x_0$, $x_1$, …, $x_n$ be $n + 1$ distinct numbers. Then $f[x_0, x_1, ..., x_n] = f[x_{i_0}, x_{i_1}, ..., x_{i_n}]$ where $i_0$, $i_1$, …, $i_n$ is any permutation of $0$, $1$, …, $n$.

We will not go deeply into the proof of Lemma 1, however, it is easy enough to verify the case when $n = 1$.

• Partial Proof: Let $y = f(x)$ be a function and let $x_0$ and $x_1$ be distinct numbers. Then:

(4)

\begin{align} \quad f[x_0, x_1] = \frac{f(x_1) - f(x_0)}{x_1 - x_0} = \frac{-1(f(x_0) - f(x_1))}{-1(x_0 - x_1)} = \frac{f(x_0) - f(x_1)}{x_0 - x_1} = f[x_1, x_0] \end{align}

Now suppose that some of the points $x_0$, $x_1$, …, $x_n$ are not distinct. For example, consider the divided difference $f[x_0, x_0]$. With the current definition of the divided difference, we see that $f[x_0, x_0]$ would be undefined. However, if $f$ is differentiable then we can extend the definition of the divided difference and:

(5)

\begin{align} \quad f[x_0, x_0] = \lim_{x_1 \to x_0} f[x_0, x_1] = \lim_{x_1 \to x_0} \frac{f(x_1) - f(x_0)}{x_1 - x_0} = f'(x_0) \end{align}

Furthermore, if only some of the points are coincident, then we can still evaluate the divided differences using the recursive formula for the divided difference and Lemma 1 above. For example:

(6)

\begin{align} \quad f[x_0, x_0, x_1] = \frac{f[x_0, x_1] - f[x_0, x_0]}{x_1 - x_0} = \frac{f[x_0, x_1] - f'(x_0)}{x_1 - x_0} \end{align}

Theorem 1: Let $y = f(x)$ be $n ≥ 1$ times continuously differentiable on an interval $[\alpha, \beta]$ and let $x_0$, $x_1$, …, $x_n$ be $n + 1$ distinct numbers where $x_j \in [\alpha, \beta]$ for $j = 0, 1, ..., n$. Let $m = \mathrm{min} \{ x_0, x_1, ..., x_n \}$ and let $M = \mathrm{max} \{ x_0, x_1, ..., x_n \}$. Then for some $\xi \in (m, M)$ the divided difference of order $n$ can be computed as $f[x_0, x_1, ..., x_n] = \frac{1}{n!} f^{(n)} (\xi)$.