TAOCP 4.6.4 Exercise 26
Let the coefficients of a cubic polynomial be denoted by $\beta_1,\beta_2,\beta_3,\beta_4$.
Section 4.6.4: Evaluation of Polynomials
Exercise 26. ▶ [**] [M21] (a) Give the polynomial chain construction using Homer's rule for evaluating polynomials of degree $n = 3$. (b) Using the construction that appears in the text's proof of Theorem A, express $\kappa_1$, $\kappa_2$, $\kappa_3$, and the result polynomial $u(x)$ in terms of $\beta_1$, $\beta_2$, $\beta_3$, $\beta_4$, and $x$. (c) Show that the result set obtained in (b), as $\beta_1$, $\beta_2$, $\beta_3$, $\beta_4$, and $x$ independently assume all real values, omits certain vectors in the result set of (a).
Verified: yes
Solve time: 4m37s
Let the coefficients of a cubic polynomial be denoted by $\beta_1,\beta_2,\beta_3,\beta_4$.
(a)
For $n=3$, Horner's rule evaluates
$$ u(x)=\beta_1x^3+\beta_2x^2+\beta_3x+\beta_4 $$
by the polynomial chain
$$ \kappa_1 \leftarrow \beta_1x+\beta_2, $$
$$ \kappa_2 \leftarrow \kappa_1x+\beta_3, $$
$$ \kappa_3 \leftarrow \kappa_2x+\beta_4, $$
$$ u(x)\leftarrow \kappa_3. $$
Thus the result vector produced by the chain is
$$ (\kappa_1,\kappa_2,\kappa_3,u). $$
(b)
Using the construction in the proof of Theorem A, we successively substitute the preceding values.
First,
$$ \kappa_1=\beta_1x+\beta_2. $$
Next,
$$ \kappa_2 =(\beta_1x+\beta_2)x+\beta_3 =\beta_1x^2+\beta_2x+\beta_3. $$
Then,
$$ \kappa_3 =(\beta_1x^2+\beta_2x+\beta_3)x+\beta_4 =\beta_1x^3+\beta_2x^2+\beta_3x+\beta_4. $$
Since $u(x)=\kappa_3$,
$$ u(x) =\beta_1x^3+\beta_2x^2+\beta_3x+\beta_4. $$
Hence
$$ \boxed{\kappa_1=\beta_1x+\beta_2,} $$
$$ \boxed{\kappa_2=\beta_1x^2+\beta_2x+\beta_3,} $$
$$ \boxed{\kappa_3=\beta_1x^3+\beta_2x^2+\beta_3x+\beta_4,} $$
$$ \boxed{u(x)=\beta_1x^3+\beta_2x^2+\beta_3x+\beta_4.} $$
(c)
The result set of part (b) consists of all vectors
$$ (\kappa_1,\kappa_2,\kappa_3,u) $$
that satisfy
$$ u=\kappa_3. $$
Indeed, from part (b),
$$ u(x)=\kappa_3 $$
for every choice of $\beta_1,\beta_2,\beta_3,\beta_4,x$.
Now consider the more general polynomial-chain construction of part (a). Its result set contains vectors obtained from arbitrary intermediate values $\kappa_1,\kappa_2,\kappa_3$ together with the final value $u$. In particular, there is no requirement in the general result set that the fourth component equal the third component.
For example, the vector
$$ (0,0,0,1) $$
belongs to the result set of the general construction: take
$$ \kappa_1=0,\qquad \kappa_2=0,\qquad \kappa_3=0,\qquad u=1. $$
However, this vector cannot arise from the parametrization of part (b), because every vector in the image of part (b) satisfies
$$ u=\kappa_3, $$
whereas for $(0,0,0,1)$ we have
$$ u=1\neq 0=\kappa_3. $$
Therefore $(0,0,0,1)$ is omitted by the parametrization of part (b).
Hence the image of
$$ (\beta_1,\beta_2,\beta_3,\beta_4,x) \longmapsto (\kappa_1,\kappa_2,\kappa_3,u) $$
is a proper subset of the result set of part (a). Consequently, the result set obtained in part (b) omits certain vectors occurring in the result set of part (a). ∎