Theorem on Horner's Method: Prove that $p(x)=\alpha_0$, $p'(x)=\beta_0$, and $p''(x)=2\gamma_0$.

Question

Concerning the polynomial $p(x)=a_0+a_1x+\dots+a_nx^n$, prove the following result. For a given $x$, we set $(\alpha_n,\beta_n,\gamma_n)=(a_n,0,0)$ and define inductively $$(\alpha_j,\beta_j,\gamma_j)=(a_j+x\alpha_{j+1},\alpha_{j+1}+x\beta_{j+1},\beta_{j+1}+x\gamma_{j+1})$$ for $j=n-1,n-2,\dots,0$. Then $p(x)=\alpha_0$, $p'(x)=\beta_0$, and $p''(x)=2\gamma_0$.

So the proof for the first derivative is in my textbook, which I have provided below. I have been able to modify the proof for $n=0,$ and $n=1$, but I am unsure what to do for the second derivative. It seems to me that there is a sudden detail that I am overlooking.

Proof: If $n=0$, then $p(x)=a_0$ and $$(\alpha_0,\beta_0,\gamma_0)=(a_0,0,0).$$ So, $\alpha_0=p(x)$, $0=\beta_0=p'(x)$, and $0=2\gamma_0=p''(x)$. Thus, the statement is true for $n=0$. If $n=1$, then $p(x)=a_1x+a_0$ and $$(\alpha_0,\beta_0,\gamma_0)=(a_0+x\alpha_1,\alpha_1+x\beta_1,\beta_1+x\gamma_1)=(a_0+xa_1, a_1, 0)=(p(x),p'(x),p''(x))$$ Thus, the statement is true for $n=1$. Suppose the statement is true for all indices $n$ less than $m$. Let $$p(x)=c_mx^m+\dots+c_1x+c_0=c_0+x(c_mx^{m-1}+\dots +c_2x+c_1)=c_0+xq(x).$$ Set $n=m-1$, $a_n=c_m$, $a_{n-1}=c_{m-1}$, \dots, $a_2=c_3$, $a_1=c_2$, and $a_0=c_1$. Since the statement is true for $q$, we apply the algorithm to $q(x)=a_nx^n+\dots+a_1x+a_0$. We get $\alpha_0=q(x)$ and $\beta_0=q'(z)$ by the induction hypothesis. If the algorithm is applied to $p$, we get the same set of pairs $(\alpha_n,\beta_n), \dots, (\alpha_1,\beta_1), (\alpha_0,\beta_0)$ (because $(c_m,\dots,c_2,c_1)=(a_n,\dots, a_1,a_0)$), but there is one more pair to be computed at the end for $p$; namely, \begin{equation*} \begin{aligned} (\alpha_{-1},\beta_{-1}) & =(a_{-1}+x\alpha_0,\alpha_0+x\beta_0) \\ & = (c_0+xq(x),q(x)+xq'(x))\\ & = (p(x),p'(x)) \end{aligned} \end{equation*}

Answer 1

I will risk using an increasing loop index rather than a decreasing one as it helps me to keep track of the order of the current polynomials.

Let us first consider the familiar case of Horner's method for $$p(x) = \sum_{j=0}^n a_j x^j.$$ Given $x$, we define $$p_0 = a_n$$ and compute recursively $$p_j = p_{j-1} x + a_{n-j}, \quad j=1,2,\dots,n.$$ As expected, we have $$p_n = p(x).$$

Since we are interested in derivatives, I would like to treat $x$ as a variable and restate the algorithm as $$ p_0(x) = a_n, \quad p_j(x) = p_{j-1}(x)x + a_{n-j}, \quad j=1,2,\dots,n.$$ We now seek to extend the iteration to produce polynomials $q_j$ and $r_j$, such that $$ q_j(x) = p_j'(x), \quad r_j(x) = q_j'(x), \quad j=0,1,2, \dots n$$ We are primarily interested in the last values, i.e. the case of $j=n$. It is clear that the extended iteration can only be initialized in one particular manner, we must choose $$p_0(x) = a_n, \quad q_0(x) = 0, \quad r_0(x) = 0,$$ because the derivative of a constant is zero. As for the remaining steps, we apply the product rule of differentiation. From $$ p_j(x) = p_{j-1}(x)x + a_{n-j}$$ and the demand that $$ q_k(x) = p_k'(x), \quad k = j-1,j$$ we deduce that $$ q_j(x) = p_j'(x) = (p_{j-1}(x)x + a_{n-j})' = p_{j-1}'(x)x + p_{j-1}(x) = q_{j-1}(x)x+p_{j-1}(x).$$ Similarly, we deduce that $$ r_j(x) = q_{j-1}'(x)x + q_{j-1}(x) + p_{j-1}'(x) = r_{j-1}(x)x + 2q_{j-1}(x)$$ is the way to recursively compute $r_j$. In short, the proposed extension is $$ p_0(x) = a_n, \quad q_0(x) = 0, \quad r_0(x) = 0,$$ followed by \begin{align} p_j(x) &= p_{j-1}(x)x + a_{n-j} \\ q_j(x) &= q_{j-1}(x)x+p_{j-1}(x) \\ r_j(x) &= r_{j-1}(x)x + 2q_{j-1}(x) \end{align} for $j=1,2,\dotsc,n$.

There are two differences between this iteration and the one proposed in your textbook. One is irrelevant, i.e. the increasing ordering of the indices. The second is slightly more important as the algorithm given above requires an extra multiplication with $2$ for every iteration.

This deficiency is however easily remedied.

Instead of computing $r_j$, we settle for $s_j = \frac{1}{2}r_j$. Then the iteration becomes $$ p_0(x) = a_n, \quad q_0(x) = 0, \quad s_0(x) = 0,$$ followed by \begin{align} p_j(x) &= p_{j-1}(x)x + a_{n-j} \\ q_j(x) &= q_{j-1}(x)x+p_{j-1}(x) \\ s_j(x) &= s_{j-1}(x)x + q_{j-1}(x) \end{align} for $j=1,2,\dotsc,n$.

In the end, we have to compensate for the missing multiplication and return $$ p_n(x), \quad q_n(x), \quad 2s_n(x)$$ to the user.

---

Please note that this approach allows you to extend Horner's method at will and compute any number of derivatives.

I changed the direction of the for loop, not to confuse or annoy, but to create a situation where the loop index tracks the order of the current polynomial. It does not matter to the compiler, but makes it easier for a human to verify that a computer program is correct.