Module

for

Horner's Method

Evaluation of a Polynomial

Let the polynomial of degree n have coefficients .  Then has the familiar form

Horner's method (or synthetic division) is a technique for evaluating polynomials.  It can be thought of as nested multiplication.  For example, the fifth-degree polynomial

can be written in the "nested multiplication" form

.

Exploration

Theorem (Horner's Method for Polynomial Evaluation)  Assume that

(1)

and     is a number for which is to be evaluated.  Then can be computed recursively as follows.

(2)        Set   ,
and
for    .

Then    .

Moreover, the coefficients    can be used to construct    and

(3)
and
(4)        ,

where    is the quotient polynomial of degree  n-1  and    is the remainder.

Example 1.  Use synthetic division (Horner's method) to find for the polynomial
.
Solution 1.

Heuristics

In the days when "hand computations" were necessary, the Horner tableau (or table) was used.  The coefficients    of the polynomial are entered on the first row in descending order, the second row is reserved for the intermediate computation step  ()  and the bottom row contains the coefficients    and  .

Example 2.  Use the "Horner tableau" to find for the polynomial
.
Solution 2.

Lemma (Horner's Method for Derivatives)  Assume that

and is a number for which and   are to be evaluated.  We have already seen that can be computed recursively as follows.

,   and
for    .

The quotient polynomial and remainder form the relation

.

We can compute can be computed recursively as follows.

(i)        ,    and
for    .

The quotient polynomial
and remainder    form the relation

(ii)        .

The Horner tableau (or table) was used for computing the coefficients is given below.

Example 3.  Use synthetic division (Horner's method) to find for the polynomial
.
Solution 3.

Using vector coefficients

As mentioned above, it is efficient to store the coefficients    of a polynomial   of degree n in the vector  .  Notice that this is a shift of the index for and the polynomial    is written in the form

.

Given the value  ,  the recursive formulas for computing the coefficients    and   of    and , have the new form

for    .

for    .

Then

Example 4.  Use the Horner's method with vector coefficients to calculate and for the polynomial
.
Use these values to perform one step in Newton's method for approximating a root using the initial approximation  .
Solution 4.

Newton-Horner method

Assume that is a polynomial of degree and there exists a number , where .  If   , then there exists a such that the sequence defined by the Newton-Raphson iteration formula

for

will converge to  r  for any initial approximation  .  The recursive formulas in the Lemma can be adapted to compute    and    and the resulting Newton-Horner iteration formula looks like

for

Algorithm (Newton-Horner Iteration).  To find a root of    given an initial approximation    using the iteration

for    .

Computer Programs  Newton-Horner Method  Newton-Horner Method

Mathematica Subroutine (Newton-Horner Iteration).

``````

``````

Mathematica Subroutine (Newton-Raphson Iteration).

``````

``````

Example 5.  Use the Newton-Horner's subroutine and the starting value to find a root of the polynomial
.
Run the Newton-Raphson subroutine and compare the two results (they should be close).
Solution 5.

Example 6.  Compare the Horner method and ordinary method of polynomial evaluation for

Solution 6.

Lemma (Horner's Method for Higher Derivatives)  Assume that the coefficients    of a polynomial   of degree n are stored in the first row of the matrix  .  Then the polynomial    can written in the form

.

Given the value  ,  the subroutine for computing all the derivatives    is

and

for    .

Example 7.  Use the Horner's method for higher derivatives to calculate all the derivatives    for the polynomial
.
Solution 7.

Polynomial Deflation

Given the polynomial    in example 5,  the iteration

will converge to the root    of  .  The Mathematica command NewtonHorner[3.0,6] produces the above sequence, then the quotient polynomial     is constructed with the command  .

```
```

The root stored in the computer is located in the variable  r1.

``````
```
```

The coefficients of  Q[x]  printed above have been rounded off.  Actually there is a little bit of round off error in the coefficients forming   ,  we will have to dig them out to look at them.

``````

```

```

```
```

Now we have a computer approximation for the factorization  .

``````

```
```

We should carry out one more step in the iteration using the command  NewtonHorner[3.0,7]  and get a more accurate calculation for the coefficients of  .   When this is done the result will be:

If the other roots of    are to be found, then they must be the roots of the quotient polynomial  .   The polynomial    is referred to as the deflated polynomial, because its degree is one less than the degree of  .  For this example it is possible to factor     as the product of two quadratic polynomials  .  Therefore,   has the factorization

,

and the five roots of      are

.

This can be determined by using Mathematica and the command Factor.

``````

```
```

This still leaves some unanswered questions that we will answer in other modules.  The quadratic factors can be determined using the Lin-Bairstow method.  Or if one prefers complex arithmetic, then Newton's method can be used.  For example, starting with the imaginary number    Newton's method will create a complex sequence converging to the complex root    of  .

``````

```

```

However, starting with purely imaginary number    will create a divergent sequence.

``````

```
```

For cases involving complex numbers the reader should look at the Lin-Bairstow and the Fundamental Theorem of Algebra modules.

Getting Real Roots

The following example illustrates polynomial deflation and shows that the order in which the roots are located could be important.  In light of example 6 we know that better calculations are made for evaluating when  x  is small.  The Newton-Horner subroutine is modified to terminate early if   evaluates close to zero (when a root is located).

Mathematica Subroutine (Newton-Horner Iteration).

``````
``````

Example 8.  Use the Newton-Horner method and find all the real roots of the polynomial

Solution 8.

Horner's Method  Horner's Method  Internet hyperlinks to web sites and a bibliography of articles.

(c) John H. Mathews 2004