Background
    
    We use the following important result from the study of the theory of equations.

Theorem (Vieta's Formulas).   Consider a polynomial of    of degree  n  with roots     

        ,  
        
        .  
        
Let    be the   elementary symmetric function or symmetric polynomial for the variables ,    

          
          
          
          
        ...  
          
          
then
        .  

Moreover, we have the important identities relating the coefficients of    

            for   .  

Exploration  Graeffe's Method

Separated Roots
    
    If the roots of    are widely separated in magnitude, then they can be approximated using ratios of the coefficients of  .  This is the heart of the Graeffe method.  
    
Theorem (Separated Real Roots).  If    is a polynomial with real roots that are widely separated in magnitude  

        
then
           for   .   

Exploration  Graeffe's Method

Example 1.  Approximate the roots of the following polynomials using the separated root theorem.  

1 (a).  

1 (b).    

1 (c).    

Solution 1.

Graeffe Root Squaring Method

    The root-finding method was popular in the 19th and 20th centuries.  It was invented independently by Karl Heinrich Gräffe (1799-1873), Germinal Pierre Dandelin (1794-1847), and  Nikolai Ivanovich Lobachevsky (1792-1856)  (See the article Dandelin, Lobacevskii, or Graeffe  by Alston S. Householder,   The American Mathematical Monthly, Vol. 66, No. 6. (Jun. - Jul., 1959), pp. 464-466, Jstor. )  Graeffe's method has the shortcoming that it proceeds to calculations where the exponents exceed the maximum allowed by floating-point arithmetic computation of most software packages.  The extended precision in Mathematica is adequate to investigate the method.  

    A necessary condition for the  separated root theorem produce a good approximation  ,  is that the roots must be widely separated in magnitude, we would need the separation to be more than    for   .  The heart of the Graeffe method is to start with "mildly" separated roots and construct a related polynomial with sufficiently widely separated roots.  This leads into the topic of root squaring.

Theorem (Root Squaring).  Given the polynomial   of degree n in factored form    with roots  .  Then    is defined by  
    
    .  

is a polynomial of degree n with roots  .  

Proof  Graeffe's Method

Example 2.  Consider the polynomial  

       

Explore the process of root squaring for .

Solution 2.

The Goal

    If the roots of   are real and distinct then successive root squaring will generate a sequence of polynomials  ,  where each polynomial    has degree  n.  The roots of    are   ,  and if  v  is large enough, then the roots of    will be widely separated.  The roots    of    are all positive.  The roots of   can be obtained by taking a root  , where the appropriate sign can be determined by evaluating  .    The goal is to separate roots!

Theorem (Graeffe's Method).  Given the polynomial   of degree n with real distinct roots  .  Define the sequence    as follows:
    
        

is a polynomial of degree n with roots    for  .  Furthermore, the roots of   are approximated by

           for   .  

Where the appropriate sign can be determined by evaluating  .  

Proof  Graeffe's Method

Algorithm (Graeffe's Method).  To find all the roots of  the polynomial   of degree n which has real distinct roots  .  Use the Graeffe iteration

        .

Computer Programs  Graeffe's Method

Mathematica Subroutine (Graeffe's Method)).

Example 3.  Use Graeffe's root squaring method to find the roots of  .  
Show each step in the process.

Solution 3.

Example 4.  Use Graeffe's root squaring method to find the roots of  .  
Use the subroutine Graeffe.

Solution 4.

Example 5.  Use Graeffe's root squaring method to find the roots of  .  
Use the subroutine Graeffe.

Solution 5.

Extending Graeffe's Method

    The literature on Graeffe's method contains a myriad of rules for treating cases other than distinct, separated real roots.  The rules involve detailed study of the behavior of the coefficients of   , which are to be listed in rows, and the coefficients of the powers of x in columns.  Hutchinson lists 11 rules for special cases, and his list was later refined by Cronvich.  There are special cases for distinct real roots, double roots, triple roots, one pair of imaginary roots, two pairs of imaginary roots, a pair of imaginary roots whose modulus is equal to the absolute value of a real root, etc.  It is not our purpose to study these cases and leave them for the reader to investigate.  We will look at two of the easier cases which give a glimpse of what might happen.

Repeated Real Roots

    The standard Graeffe iteration given in the Mathematica subroutine is robust enough to treat the case of repeated real roots.  However, knowing that a double root appears is essential information that will be used.   If    is a root of order  j,  then    and the magnitude of the repeated roots are given by the following computation.   After v iterations the polynomial is constructed
    
    

The magnitude of the multiple root    of order  j,  is computed with the formula

      .  

Example 6.  Repeated Real Roots Use Graeffe's root squaring method to find the roots of  .
As in the case of Newton's method, the iteration will proceed linearly for the repeated root and quadratically for the simple roots.  

Solution 6.

Example 7.  Repeated Real Roots Use Graeffe's root squaring method to find the roots of  .
As in the case of Newton's method, the iteration will proceed linearly for the repeated root and quadratically for the simple roots.  

Solution 7.

The Efficient Graeffe Subroutine

    It can be observed that the functions    are never used in Graeffe's method, only their coefficients.  So it is an unnecessary step to form the polynomials.  The following streamlined version of the subroutine uses only the coefficients.  Also, this version can be used with decimal entries for the coefficients, where the previous version will not.  

Computer Programs  Graeffe's Method

Mathematica Subroutine (Graeffe's Method)).

Example 8.  Use Graeffe's root squaring method to find the roots of  .  
Use the subroutine Graeffe2.

Solution 8.

Example 9.  Unequal Real Roots of Equal Magnitude Use Graeffe's root squaring method to find the roots of  .
Use the subroutine Graeffe2.

Solution 9.

Research Experience for Undergraduates

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

Download this Mathematica Notebook Graeffe's Method

(c) John H. Mathews 2005