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

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 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.

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.

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

      .  

The Coefficient Table

    The nature of the roots of   can be determined by the rules of Hutchinson and Cronvich and refer to the coefficients of  .  For example, if
    
    
    
    
    
    
    
    

Then the coefficient table is

	x

  

Hutchinson's Rules

    In conclusion, we give as a summary a list of several of the simpler behaviors of the coefficients of the transformed equations in the root-squaring process. The terminology used has already been explained. Not all of the cases in the list have been discussed in this paper, but all are routine results of the method of investigation used.

1. All signs plus after the given equation, and all columns increase at normal rate: all roots real, and of unequal absolute values.

2. A single column irregular in sign: one pair of complex roots.

3. Two adjacent columns irregular in sign: one pair of complex roots, with modulus equal to the modulus of a real root.

4. One column increases eventually at one-half of normal rate: doublet.

5. Two adjacent columns each increase eventually at one-third of normal rate: triplet.

6. Two non-adjacent columns each increase at one-half of normal rate: two doublets (not a quadruplet).

7. Three adjacent columns increase at one-fourth, one-sixth, and one-fourth of normal rate, respectively: quadruplet.

8. One column increases at one-half of normal rate, and a non-adjacent column is irregular in sign: doublet and pair of complex roots.

9. Two non-adjacent columns irregular in sign: two pairs of complex roots, with unequal moduli.

10. Three adjacent columns irregular in sign: two pairs of complex roots, with equal moduli.

11. One column irregular in sign, and one column adjacent on each side regular in sign, but irregular in magnitude: doublet and a pair of complex roots with the same modulus as the doublet.

Cronvich's Rules

    In the following summary it is understood that the peculiarly behaving columns mentioned always occur in a group of columns which have a regular column adjacent on each side of the group, thus separating it from any other groups.

1. No oscillating columns, and all coefficients positive after the given equation. All real roots.

a. All columns regular. Distinct real roots.

b. Adjacent irregular columns, (n-1) in number, increasing at rates proportional to the reciprocals of the binomial coefficients. n multiple roots of equal absolute value.

2. One oscillating column.

a. One oscillating column only. A pair of imaginary roots.

b. An oscillating column with an irregular column adjacent on each side having an indefinite rate and no possibility of having negative signs. A pair of imaginary roots whose modulus is equal to the absolute value of two real roots of equal absolute value.

3. Two oscillating columns.

a. Two adjacent oscillating columns with approximately equal rates. A pair of imaginary roots whose modulus is equal to the absolute value of a real root.

b. Two adjacent oscillating columns with exactly equal rates of oscillation and having one irregular column adjacent on each side with an indefinite rate and no possibility of having negative signs. A pair of imaginary roots whose modulus is equal to the absolute value of three real roots of equal absolute value.

c. Two alternate oscillating columns with exactly the same rates separated by an irregular column with an indefinite rate of increase and no possibility of having negative signs. Two identical pairs of imaginary roots.

d. Two oscillating columns with approximately equal rates of oscillation separated by two irregular columns with indefinite rates and no possibility of having negative signs. Two identical pairs of imaginary roots with modulus equal to the absolute value of a real root.

4. Three oscillating columns.

a. Three adjacent oscillating columns with the outer two having approximately the same rate of oscillation and the intervening column having a very slow rate. Two pairs of imaginary roots with equal moduli but unequal amplitudes.

b. Two alternate columns with negative coefficients for the first transformed equation and positive coefficients thereafter and with no definite rate of increase, and an intervening oscillating column.-A pair of pure imaginary roots and a pair of imaginary roots with equal moduli. (This is a special case of 4a.)

5. Four oscillating columns.

a. Four adjacent oscillating columns with the first and fourth, and second and third having approximately equal rates respectively. Two pairs of imaginary roots with equal moduli and a real root whose absolute value is equal to the modulus of the imaginary roots.

    Pure imaginary roots, as special cases of imaginary roots, constitute exceptions to the above rules. One case, rule 4b, has already been given in the above list. In general, the columns which are oscillating for ordinary imaginary roots become, in this case, columns which show a minus sign in the first transformed equation with positive signs for the rest of the transformed equations, and which, in most cases, eventually show the characteristics usually attributed to multiple roots of equal absolute value.

Comparison with Hutchinson's Rules

    The (Cronvich) rules presented in the above Summary cover all the cases considered by Hutchinson in his Summary and also several other cases not mentioned by him. Some of the rules in my Summary are almost identical with those stated by Hutchinson, except for the terminology used. These are rules 1a, 2a, 3a, and 2b, which correspond to Hutchinson's rules 1, 2, 3, and 11, respectively.

References

1. On Graeffe's Method for the Numerical Solution of Algebraic Equations  
   C. A. Hutchinson  
   American Mathematical Monthly, Vol. 42, No. 3. (Mar., 1935), pp. 149-161, Jstor.  
2. On the Graeffe Method of Solution of Equations  
   L. L. Cronvich  
   American Mathematical Monthly, Vol. 46, No. 4. (Apr., 1939), pp. 185-190. Jstor.  

(c) John H. Mathews 2005