TAOCP 4.6.4 Exercise 7

Section 4.6.4: Evaluation of Polynomials

Exercise 7. [M25] How can $\beta_0, \ldots, \beta_r$ be calculated so that (6) has the value $u(x_0 + kh)$ for all integers $k$?

Verified: yes
Solve time: 1m09s

Solution

We wish to compute $\beta_0, \ldots, \beta_r$ so that the polynomial

$u(x_0 + kh) = \beta_0 + \beta_1 k + \cdots + \beta_r k^r \eqno(6)$

for all integers $k$. The key is to recognize that the $\beta_j$ are the coefficients of the expansion of $u(x_0 + kh)$ in powers of $k$, or equivalently, they are the values of the forward differences of $u$ at $x_0$ divided by the appropriate factorials.

Define the forward difference operator $\Delta_h$ by

$\Delta_h u(x) = u(x + h) - u(x),$

and its iterates

$\Delta_h^j u(x) = \Delta_h(\Delta_h^{j-1} u(x)), \qquad \Delta_h^0 u(x) = u(x).$

By Newton's forward difference formula, we have

$u(x_0 + kh) = \sum_{j=0}^r \binom{k}{j} \Delta_h^j u(x_0), \qquad \text{for integer } k \ge 0,$

where $\binom{k}{j} = \frac{k(k-1)\cdots(k-j+1)}{j!}$. Comparing this with (6), we obtain

$\beta_j = \sum_{i=0}^j s(j,i) \frac{\Delta_h^i u(x_0)}{i!},$

where $s(j,i)$ are the Stirling numbers of the first kind, relating powers $k^j$ to falling factorials $k(k-1)\cdots(k-i+1)$. Equivalently, one may write the explicit formula

$\beta_j = \frac{\Delta_h^j u(x_0)}{j!}, \qquad 0 \le j \le r,$

because the transformation from falling factorials to powers of $k$ is triangular with ones on the diagonal.

Thus the computation proceeds as follows:

1. Compute the forward differences $\Delta_h u(x_0), \Delta_h^2 u(x_0), \ldots, \Delta_h^r u(x_0)$ recursively:

$\Delta_h^j u(x_0) = \Delta_h^{j-1} u(x_0 + h) - \Delta_h^{j-1} u(x_0).$

1. Divide each $\Delta_h^j u(x_0)$ by $j!$ to obtain $\beta_j$.

This ensures that the polynomial in $k$ defined by (6) agrees with $u(x_0 + kh)$ for all integers $k$. The recursion is well-defined because $\deg u \le r$, so $\Delta_h^{r+1} u(x_0) = 0$, and the triangular transformation from forward differences to powers of $k$ guarantees uniqueness of the coefficients $\beta_0, \ldots, \beta_r$.

This completes the solution.

∎