Horner's Rule for a Polynomial and Its Derivative

So far we have found an efficient procedure for evaluating a polynomial at any $x = x_0$. Next we develop a procedure for getting its derivative $P^\prime(x_0)$ at the same $x$.

Notice that for any $x_0$ we can divide $P(x)$ by $x - x_0$ to get quotient and remainder:

$$P(x) = Q(x)(x - x_0) + P(x_0)$$ (2)

where the quotient polynomial $Q(x)$ has degree $n-1$:

$$Q(x) = \sum_{i=0}^{n-1} b_i x^i.$$

It is easy to show that

$$P'(x_0) = Q(x_0).$$

So if we can find the coefficients $b_i$ of the quotient polynomial $Q(x)$, we can use Horner's algorithm to get $P^\prime(x_0)$.

If we substitute the polynomials into Eq. (), and equate coefficients of $x^i$ on the lhs and rhs and solve for the coefficients $b_i$ and remainder $P(x_0)$ we get a series of equations that can be organized as a recursion relation:

$$\begin{eqnarray*} b_{n-1} &=& a_n \\ b_{i-1} &=& a_i + x_0 b_i \mbox{for $i = 1 \ldots{} n-1$} \\ P(x_0) &=& a_0 + x_0 b_0. \end{eqnarray*}$$

These equations should look familiar, because they are nothing but Horner's algorithm, derived in a different way. But now we see that the intermediate variable $p$ in the pseudocode actually holds the coefficients $b_i$ of the quotient polynomial $Q(x)$! If we are careful, we can use them to build a dual procedure for evaluating both $P(x_0)$ and $Q(x_0)$ without the need to store them all.

Here is the pseudocode for the dual-purpose algorithm:

   Step 1: Set p = a[n] and q = 0
   Step 2: Do steps 3 and 4 for i from n-1 to 0, decreasing by 1
        Step 3: set q = p + x0 * q
        Step 4: set p = a[i] + x0 * p
   Step 5: The value of P(x_0) is p and the value of P'(x_0) is q

It is left as an exercise to check this pseudocode by playing computer with a simple example and with the special case $n = 0$.

Finally, we leave as an exercise to complete the Newton-Raphson code for finding the real roots of a general polynomial.