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.  

Proof  Horner's Method  Horner's Method  

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.  

Proof  Horner's Method  Horner's Method  

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.

Research Experience for Undergraduates

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

Download this Mathematica Notebook Horner's Method

(c) John H. Mathews 2004