TAOCP 4.6.4 Exercise 15
Let f[x_0]=f(x_0), and for $n>0$ define the divided differences recursively by
Section 4.6.4: Evaluation of Polynomials
Exercise 15. ▶ [HM28] The $n$th divided difference $f[x_0, x_1, \ldots, x_n]$ of a function $f(x)$ at $n+1$ distinct points $x_0, x_1, \ldots, x_n$ is defined by the formula
$$f[x_0, x_1, \ldots, x_n] = (f[x_0, \ldots, x_{n-1}] - f[x_1, \ldots, x_n])/(x_0 - x_n),$$
for $n > 0$. Thus $f[x_0, x_1, \ldots, x_n] = \sum_{0 \le k \le n} f(x_k) / \prod_{0 \le j \le n,, j \ne k} (x_k - x_j)$ is a symmetric function of its $n+1$ arguments. (a) Prove that $f[x_0, \ldots, x_n] = f^{(n)}(\theta)/n!$ for some $\theta$ between $\min(x_0, \ldots, x_n)$ and $\max(x_0, \ldots, x_n)$, if the $n$th derivative $f^{(n)}(x)$ exists and is continuous. [Hint: Prove the identity
$$f[x_0, x_1, \ldots, x_n] = \int_0^1 dt_1 \int_0^{t_1} dt_2 \cdots \int_0^{t_{n-1}} dt_n , f^{(n)}(x_0(1 - t_1) + x_1(t_1 - t_2) + \cdots + x_{n-1}(t_{n-1} - t_n) + x_n(t_n - 0)).$$
This formula also defines $f[x_0, x_1, \ldots, x_n]$ in a useful manner when the $x_i$ are not distinct.] (b) If $y_j = f(x_j)$, show that $a_j = f[x_0, \ldots, x_j]$ in Newton's interpolation polynomial (42).
Verified: yes
Solve time: 1m40s
Setup
Let
$$ f[x_0]=f(x_0), $$
and for $n>0$ define the divided differences recursively by
$$ f[x_0,\ldots,x_n] = \frac{f[x_0,\ldots,x_{n-1}]-f[x_1,\ldots,x_n]} {x_0-x_n}. $$
Part (a) asks for a proof that
$$ f[x_0,\ldots,x_n] = \frac{f^{(n)}(\theta)}{n!} $$
for some $\theta$ between $\min(x_0,\ldots,x_n)$ and $\max(x_0,\ldots,x_n)$, assuming that $f^{(n)}$ exists and is continuous.
Part (b) asks for the identification of the coefficients in Newton's interpolation formula (42),
$$ P_n(x) = a_0+a_1(x-x_0)+a_2(x-x_0)(x-x_1)+\cdots +a_n\prod_{0\le k<n}(x-x_k). $$
Solution
(a)
Define
$$ I_n(x_0,\ldots,x_n) = \int_0^1dt_1 \int_0^{t_1}dt_2 \cdots \int_0^{t_{n-1}}dt_n, f^{(n)}(L), $$
where
$$ L= x_0(1-t_1)+x_1(t_1-t_2)+\cdots +x_{n-1}(t_{n-1}-t_n)+x_nt_n . $$
We prove by induction on $n$ that
$$ I_n(x_0,\ldots,x_n)=f[x_0,\ldots,x_n]. \eqno(*) $$
For $n=0$ the multiple integral is absent, and
$$ I_0(x_0)=f(x_0)=f[x_0]. $$
Assume $(*)$ holds for $n-1$. Since
$$ \frac{\partial L}{\partial t_1}=x_1-x_0, $$
integration with respect to $t_1$ gives
$$ I_n = \frac1{x_1-x_0} \int_0^1dt_2\cdots\int_0^{t_{n-1}}dt_n \Bigl[ f^{(n-1)}(L) \Bigr]_{t_1=t_2}^{t_1=1}. $$
When $t_1=1$,
$$ L=x_1(1-t_2)+x_2(t_2-t_3)+\cdots+x_nt_n, $$
and when $t_1=t_2$,
$$ L=x_0(1-t_2)+x_2(t_2-t_3)+\cdots+x_nt_n . $$
Hence
$$ I_n = \frac{ I_{n-1}(x_1,\ldots,x_n) - I_{n-1}(x_0,x_2,\ldots,x_n)} {x_1-x_0}. $$
Applying the induction hypothesis,
$$ I_n = \frac{ f[x_1,\ldots,x_n] - f[x_0,x_2,\ldots,x_n]} {x_1-x_0}. $$
The right-hand side satisfies the same recursion as divided differences and is symmetric in all arguments. Therefore it equals
$$ f[x_0,\ldots,x_n]. $$
This proves $(*)$.
Now the coefficients
$$ 1-t_1,\quad t_1-t_2,\quad \ldots,\quad t_{n-1}-t_n,\quad t_n $$
are nonnegative and sum to $1$. Thus $L$ always lies in the interval
$$ [\min(x_0,\ldots,x_n),,\max(x_0,\ldots,x_n)]. $$
Since $f^{(n)}$ is continuous, the integral mean-value theorem yields a point $\theta$ in that interval such that
$$ f[x_0,\ldots,x_n] = f^{(n)}(\theta) \int_0^1dt_1\int_0^{t_1}dt_2\cdots\int_0^{t_{n-1}}dt_n . $$
The remaining integral is the volume of the simplex
$$ 0\le t_n\le\cdots\le t_1\le1, $$
namely
$$ \int_0^1dt_1\int_0^{t_1}dt_2\cdots\int_0^{t_{n-1}}dt_n =\frac1{n!}. $$
Therefore
$$ f[x_0,\ldots,x_n] = \frac{f^{(n)}(\theta)}{n!}. $$
(b)
Let
$$ P_n(x) = a_0+a_1(x-x_0)+\cdots +a_n\prod_{0\le k<n}(x-x_k) $$
interpolate the values
$$ P_n(x_j)=y_j=f(x_j), \qquad 0\le j\le n. $$
Set
$$ P_0(x)=y_0. $$
Hence
$$ a_0=y_0=f[x_0]. $$
Assume that
$$ P_{j-1}(x) = \sum_{k=0}^{j-1} f[x_0,\ldots,x_k] \prod_{0\le r<k}(x-x_r). $$
Then
$$ P_j(x) = P_{j-1}(x) +a_j\prod_{0\le r<j}(x-x_r). $$
Evaluating at $x=x_j$ gives
$$ a_j = \frac{ f(x_j)-P_{j-1}(x_j)} {\prod_{0\le r<j}(x_j-x_r)}. \tag{1} $$
The standard expansion of the interpolation polynomial in Newton form is
$$ f(x) = f[x_0] +fx_0,x_1 +\cdots +f[x_0,\ldots,x_j] \prod_{0\le r<j}(x-x_r), $$
and substituting $x=x_j$ shows that the numerator in (1) equals
$$ f[x_0,\ldots,x_j] \prod_{0\le r<j}(x_j-x_r). $$
Consequently,
$$ a_j=f[x_0,\ldots,x_j]. $$
Thus every coefficient in Newton's interpolation polynomial is the corresponding divided difference:
$$ \boxed{a_j=f[x_0,x_1,\ldots,x_j]\qquad(0\le j\le n).} $$
Verification
The integral representation satisfies the divided-difference recursion and the initial condition $f[x_0]=f(x_0)$, hence it equals the divided difference for all $n$.
The integration region is the simplex
$$ 0\le t_n\le\cdots\le t_1\le1, $$
whose volume is $1/n!$; therefore the integral mean-value theorem gives
$$ f[x_0,\ldots,x_n]=f^{(n)}(\theta)/n!. $$
For Newton interpolation, evaluation at $x_j$ isolates the coefficient of
$$ \prod_{0\le r<j}(x-x_r), $$
and the resulting quotient is exactly the divided difference $f[x_0,\ldots,x_j]$.
This completes the proof.
∎
Notes
The identity in part (a) remains meaningful when some of the points $x_i$ coincide. In that case the integral formula provides a continuous extension of divided differences and leads directly to Hermite interpolation.