TAOCP 4.6.4 Exercise 17

We are asked to simplify the interpolation formula (45) when the nodes are equally spaced, that is, when $x_k = x_0 + kh, \qquad 0 \le k \le n.$ Formula (45) in Section 4.

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.6.4: Evaluation of Polynomials

Exercise 17. [M20] Show that the interpolation formula (45) reduces to a very simple expression involving binomial coefficients when $x_k = x_0 + kh$ for $0 \le k \le n$. [Hint: See exercise 1.2.6–48.]

Verified: yes
Solve time: 1m13s

Solution

We are asked to simplify the interpolation formula (45) when the nodes are equally spaced, that is, when

$x_k = x_0 + kh, \qquad 0 \le k \le n.$

Formula (45) in Section 4.6.4 expresses the Newton interpolation polynomial as

$u(x) = \sum_{j=0}^n f[x_0, x_1, \ldots, x_j] \prod_{i=0}^{j-1} (x - x_i), \eqno(45)$

where the product over an empty set is interpreted as 1.

Set

$t = \frac{x - x_0}{h},$

so that

$x - x_i = x_0 + t h - (x_0 + i h) = h(t - i).$

Therefore the product in (45) becomes

$\prod_{i=0}^{j-1} (x - x_i) = \prod_{i=0}^{j-1} h(t - i) = h^j \prod_{i=0}^{j-1} (t - i). \eqno(1)$

Next, consider the divided differences for equally spaced nodes. For a function $f$ evaluated at $x_k = x_0 + k h$, the first divided difference is

$f[x_0, x_1] = \frac{f(x_1) - f(x_0)}{x_1 - x_0} = \frac{f(x_0 + h) - f(x_0)}{h} = \frac{\Delta f_0}{h},$

where $\Delta f_0 = f_1 - f_0$ is the first forward difference. By induction on $j$, the $j$th divided difference satisfies

$f[x_0, x_1, \ldots, x_j] = \frac{\Delta^j f_0}{h^j}, \eqno(2)$

where $\Delta^j f_0$ denotes the $j$th forward difference at $x_0$. This follows directly from the recurrence

$f[x_0, \ldots, x_j] = \frac{f[x_1, \ldots, x_j] - f[x_0, \ldots, x_{j-1}]}{x_j - x_0} = \frac{\Delta^j f_0}{h^j}.$

Substituting (1) and (2) into (45) gives

$$ \begin{aligned} u(x) &= \sum_{j=0}^n f[x_0, \ldots, x_j] \prod_{i=0}^{j-1} (x - x_i) \ &= \sum_{j=0}^n \frac{\Delta^j f_0}{h^j} \cdot h^j \prod_{i=0}^{j-1} (t - i) \ &= \sum_{j=0}^n \Delta^j f_0 \prod_{i=0}^{j-1} (t - i). \end{aligned} $$

Finally, observe that

$\prod_{i=0}^{j-1} (t - i) = t(t-1)(t-2)\cdots(t-j+1) = t^{\underline{j}},$

where $t^{\underline{j}}$ is the falling factorial. Therefore the interpolation polynomial reduces to

$u(x) = \sum_{j=0}^n \Delta^j f_0 , t^{\underline{j}}, \qquad t = \frac{x - x_0}{h}. \eqno(3)$

If desired, we may rewrite $t^{\underline{j}}$ in terms of binomial coefficients:

$t^{\underline{j}} = j! \binom{t}{j},$

so that the final expression becomes

$\boxed{u(x) = \sum_{j=0}^n \Delta^j f_0 , j! \binom{\frac{x - x_0}{h}}{j}}.$

This completes the solution. ∎