Divided Differences

There are two disadvantages to using the Lagrangian polynomial or Neville's method for interpolation. First, it involves more arithmetic operations than does the divided-difference method we now discuss. Second, and more importantly, if we desire to add or subtract a point from the set used to construct the polynomial, we essentially have to start over in the computations. Both the Lagrangian polynomials and Neville's method also must repeat all of the arithmetic if we must interpolate at a new x-value. The divided-difference method avoids all of this computation.

 Actually, we will not get a polynomial different from that obtained by Lagrange's technique. As we will show later on, every nth-degree polynomial that passes through the same n + 1 points is identical. Only the way that the polynomial is expressed is different.

 Our treatment of divided-difference tables assumes that the function, f(x), is known at several values for x:

$$ x_0 \qquad f_0 \ x_1 \qquad f_1 \ x_2 \qquad f_2 \ x_3 \qquad f_3 \ $$

We do not assume that the x's are evenly spaced or even that the values are arranged in any particular order (but some ordering may be advantageous).

 Consider the nth-degree polynomial written in a special way:

$$ P_n(x) = a_0 + (x-x_0)a_1 + (x-x_0)(x-x_1)a_2 + ... + (x-x_0)(x-x_1) ...(x-x_{n-1})a_n \qquad ...equ(1) $$

If we chose the a_i so that P_n(x) = f(x) at the n + 1 known points, (x_i,f_i),i = 0, . . . .n, then P_n(x) is an interpolating polynomial. We will show that the a_i's are readily determined by using what are called the divided differences of the tabulated values.

A special standard notation for divided differences is

$$ f[x_0,x_1] = \frac{f_1-f_0}{x_1-x_0}, $$

called the first divided difference between x₀ and x₁. The function

$$ f[x_1,x_2] = \frac{f_2-f_1}{x_2-x_1}, $$

is the first divided difference between x₁ and x₂ (We use f[x₀] = f₀ = f(x₀)).

In general,

$$ \boxed{f[x_s,x_t] = \frac{f_t - f_s}{x_t - x_s}} $$

is the first divided difference between x_s and x_t. Observe that the order of the points is immaterial:

$$ f[x_s,x_t] = \frac{f_t - f_s}{x_t -x_s} = \frac{f_s - f_t}{x_s - x_t} = f[x_t, x_s] $$

Second- and higher-order differences are defined in terms of lower-order differences. For example,

$$ f[x_0, x_1, x_2] = \frac{f[x_1,x_2] - f[x_0, x_1]}{x_2 - x_0} $$

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

The concept is even extended to a zero-order difference:

$$ f[x_s] = f_s $$

Using the standard notation, a divided-difference table is shown in symbolic form in Table 3.1.

$$ \begin{array}{|c|c|c|c|c|} \hline \ \mathbf{x_i} & \mathbf{f_i} & \mathbf{f[x_i, x_{i+1}]} & \mathbf{f[x_i,x_{i+1},x_{i+2}]} & \mathbf{f[x_i,x_{i+1},x_{i+2},x_{i+3}]} \[4px] \hline \ x_0 & f_0 & f[x_0,x_1] & f[x_0,x_1,x_2] & f[x_0,x_1,x_2,x_3] \[4px] \hline \ x_1 & f_1 & f[x_1,x_2] & f[x_1,x_2,x_3] & f[x_1,x_2,x_3,x_4] \[4px] \hline \ x_2 & f_2 & f[x_2,x_3] & f[x_2,x_3,x_4] & \[4px] \hline \ x_3 & f_3 & f[x_3,x_4] & & \[4px] \hline \ x_4 & f_4 & & & \[4px] \hline \end{array} $$

$$Table\ 3.1$$

  We are now ready to establish that the a_i of Eq.(1) are given by these divided differences. We write Eq.(1) with x set equal to x₀, x₁, ..., x_n in succession, giving

$$ \begin{aligned} x = x_0: \qquad &P_n(x_0) = a_0, \ x = x_1: \qquad &P_n(x_1) = a_0 + (x_1 - x_0)a_1, \ x = x_2: \qquad &P_n(x_2) = a_0 + (x_2-x_0)a_1 + (x_2-x_0)(x_2-x_1)a_2, \ ⋮ \ x = x_n: \qquad &P_n(x_n) = a_0 + (x_n-x_0)a_1 + (x_n-x_0)(x_n-x_1)a_2 + ... + (x_n - x_0)...(x_n-x_{n-1})a_n \end{aligned} $$

If P_n(x) is to be an interpolating polynomial, it must match the table for all n + 1 entries:

$$ P_n(x_i) = f_i \quad for\ i =0,1,2,...,n $$

If the P_n(x_i) in each equation is replaced by f_i, we get a triangular system, and each a_i, can be computed in turn.

  From the first equation,

$$ a_0 = f_0 = f[x_0] \quad makes \quad P_n(x_0) = f_0 $$

If a₁ = f[x₀, x₁], then

$$ P_n(x_1) = f_0 + (x_1 - x_0)\frac{f_1 - f_0}{x_1 - x_0} = f_1 $$

If a₂ = f[x₀, x₁, x₂], then

$$ P_n(x_2) = f_0 + (x_2 - x_0)\frac{f_1 - f_0}{x_1 - x_0} + (x_2 - x_0)(x_2 - x_1)\frac{(f_2 - f_1)/(x_2 - x_1) - (f_1 - f_0)/(x_1 - x_0)}{x_2 - x_0} = f_2 $$

One can show in similar fashion that each P_n(x_i) will equal f_i if a_i = f[x₀, x₁, ..., x_i].

We then can write:

$$\boxed{ \begin{aligned} P_n(x) = &f[x_0] + (x-x_0)f[x_0, x_1] + (x-x_0)(x-x_1)f[x_0...x_2] \ &+ (x-x_0)(x-x_1)(x-x_2)f[x_0...x_3] + ... \ &+ (x-x_0)(x-x_1)... (x-x_{n-1})f[x_0...x_n] \end{aligned} } \qquad \qquad ...equ(2)$$