TAOCP 4.6.4 Exercise 16
Newton's interpolation polynomial (42) has the form u_n(x) = a_0 +a_1(x-x_0)
Section 4.6.4: Evaluation of Polynomials
Exercise 16. [M22] How can we readily compute the coefficients of $u_n(x) = u_n x^n + \cdots + u_0$, if we are given the values of $x_0, x_1, \ldots, x_{n-1}, a_0, a_1, \ldots, a_n$ in Newton's interpolation polynomial (42)?
Verified: yes
Solve time: 1m11s
Solution
Newton's interpolation polynomial (42) has the form
$$ u_n(x) = a_0 +a_1(x-x_0) +a_2(x-x_0)(x-x_1) +\cdots +a_n\prod_{0\le j<n}(x-x_j). $$
We are given the numbers
$$ x_0,x_1,\ldots,x_{n-1},\qquad a_0,a_1,\ldots,a_n, $$
and we wish to compute the coefficients
$$ u_n(x)=u_nx^n+u_{n-1}x^{n-1}+\cdots+u_0. $$
The coefficients can be obtained by applying Horner's rule to the Newton form itself.
Define polynomials
$$ P_n(x)=a_n, $$
and for $k=n-1,n-2,\ldots,0$ let
$$ P_k(x)=a_k+(x-x_k)P_{k+1}(x). \eqno(1) $$
Then
$$ P_0(x)=u_n(x). $$
Write
$$ P_{k+1}(x) = b^{(k+1)}_{n-k-1}x^{,n-k-1} +\cdots+ b^{(k+1)}_1x +b^{(k+1)}_0 . $$
Equation (1) gives
$$ P_k(x) = a_k+xP_{k+1}(x)-x_kP_{k+1}(x). $$
Hence the coefficients of $P_k$ are obtained from those of $P_{k+1}$ by
$$ b^{(k)}_0 = a_k-x_k b^{(k+1)}_0, $$
and
$$ b^{(k)}j = b^{(k+1)}{j-1} -x_k b^{(k+1)}_j, \qquad 1\le j\le n-k-1, $$
while
$$ b^{(k)}{,n-k} = b^{(k+1)}{,n-k-1}. $$
Starting with the single coefficient
$$ P_n(x)=a_n, $$
and applying these recurrences for
$$ k=n-1,n-2,\ldots,0, $$
produces all coefficients of $P_0(x)=u_n(x)$.
Equivalently, if the coefficients of the current polynomial are stored in an array, the conversion from Newton form to ordinary power-series form is performed by the nested multiplication
$$ u_n(x) = a_0+(x-x_0)\Bigl(a_1+(x-x_1)\bigl(\cdots +(x-x_{n-1})a_n\bigr)\Bigr), $$
which is Horner's rule with the linear factors $(x-x_k)$ in place of the common factor $x$. At each stage the coefficients are updated by multiplying the current polynomial by $(x-x_k)$ and then adding $a_k$.
Thus the coefficients $u_n,u_{n-1},\ldots,u_0$ are readily computed by repeated application of the recurrence
$$ P_k(x)=a_k+(x-x_k)P_{k+1}(x), \qquad k=n-1,n-2,\ldots,0, $$
working entirely with coefficient vectors. ∎