Module

for

Graeffe's Method

 

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

Theorem (Vieta's Formulas).   Consider a polynomial of  [Graphics:Images/GraeffeMethodMod_gr_1.gif]  of degree  n  with roots  [Graphics:Images/GraeffeMethodMod_gr_2.gif]   

        [Graphics:Images/GraeffeMethodMod_gr_3.gif],  
        
        [Graphics:Images/GraeffeMethodMod_gr_4.gif].  
        
Let  [Graphics:Images/GraeffeMethodMod_gr_5.gif]  be the  [Graphics:Images/GraeffeMethodMod_gr_6.gif] elementary symmetric function or symmetric polynomial for the variables [Graphics:Images/GraeffeMethodMod_gr_7.gif],    

        [Graphics:Images/GraeffeMethodMod_gr_8.gif]  
        [Graphics:Images/GraeffeMethodMod_gr_9.gif]  
        [Graphics:Images/GraeffeMethodMod_gr_10.gif]  
        [Graphics:Images/GraeffeMethodMod_gr_11.gif]  
        ...  
        [Graphics:Images/GraeffeMethodMod_gr_12.gif]  
        [Graphics:Images/GraeffeMethodMod_gr_13.gif]  
then
        [Graphics:Images/GraeffeMethodMod_gr_14.gif].  

Moreover, we have the important identities relating the coefficients of  [Graphics:Images/GraeffeMethodMod_gr_15.gif]  

        [Graphics:Images/GraeffeMethodMod_gr_16.gif]    for   [Graphics:Images/GraeffeMethodMod_gr_17.gif].  

Exploration  Graeffe's Method

 

Separated Roots
    
    If the roots of  [Graphics:Images/GraeffeMethodMod_gr_18.gif]  are widely separated in magnitude, then they can be approximated using ratios of the coefficients of  [Graphics:Images/GraeffeMethodMod_gr_19.gif].  This is the heart of the Graeffe method.  
    
Theorem (Separated Real Roots).  If  [Graphics:Images/GraeffeMethodMod_gr_20.gif]  is a polynomial with real roots that are widely separated in magnitude  

        [Graphics:Images/GraeffeMethodMod_gr_21.gif]
then
        [Graphics:Images/GraeffeMethodMod_gr_22.gif]   for   [Graphics:Images/GraeffeMethodMod_gr_23.gif].   

Exploration  Graeffe's Method

 

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

1 (a).  [Graphics:Images/GraeffeMethodMod_gr_24.gif]

1 (b).  [Graphics:Images/GraeffeMethodMod_gr_25.gif]  

1 (c).  [Graphics:Images/GraeffeMethodMod_gr_26.gif]  

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  [Graphics:Images/GraeffeMethodMod_gr_39.gif],  is that the roots must be widely separated in magnitude, we would need the separation to be more than  [Graphics:Images/GraeffeMethodMod_gr_40.gif]  for   [Graphics:Images/GraeffeMethodMod_gr_41.gif].  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  [Graphics:Images/GraeffeMethodMod_gr_42.gif] of degree n in factored form  [Graphics:Images/GraeffeMethodMod_gr_43.gif]  with roots  [Graphics:Images/GraeffeMethodMod_gr_44.gif].  Then  [Graphics:Images/GraeffeMethodMod_gr_45.gif]  is defined by  
    
    [Graphics:Images/GraeffeMethodMod_gr_46.gif].  

is a polynomial of degree n with roots  [Graphics:Images/GraeffeMethodMod_gr_47.gif].  

Proof  Graeffe's Method

 

Example 2.  Consider the polynomial  

    [Graphics:Images/GraeffeMethodMod_gr_48.gif]   

Explore the process of root squaring for [Graphics:Images/GraeffeMethodMod_gr_49.gif].

Solution 2.

 

The Goal

    If the roots of  [Graphics:Images/GraeffeMethodMod_gr_103.gif] are real and distinct then successive root squaring will generate a sequence of polynomials  [Graphics:Images/GraeffeMethodMod_gr_104.gif],  where each polynomial  [Graphics:Images/GraeffeMethodMod_gr_105.gif]  has degree  n.  The roots of  [Graphics:Images/GraeffeMethodMod_gr_106.gif]  are  [Graphics:Images/GraeffeMethodMod_gr_107.gif] ,  and if  v  is large enough, then the roots of  [Graphics:Images/GraeffeMethodMod_gr_108.gif]  will be widely separated.  The roots  [Graphics:Images/GraeffeMethodMod_gr_109.gif]  of  [Graphics:Images/GraeffeMethodMod_gr_110.gif]  are all positive.  The roots of  [Graphics:Images/GraeffeMethodMod_gr_111.gif] can be obtained by taking a root  [Graphics:Images/GraeffeMethodMod_gr_112.gif], where the appropriate sign can be determined by evaluating  [Graphics:Images/GraeffeMethodMod_gr_113.gif].    The goal is to separate roots!

Theorem (Graeffe's Method).  Given the polynomial  [Graphics:Images/GraeffeMethodMod_gr_114.gif] of degree n with real distinct roots  [Graphics:Images/GraeffeMethodMod_gr_115.gif].  Define the sequence  [Graphics:Images/GraeffeMethodMod_gr_116.gif]  as follows:
    
        [Graphics:Images/GraeffeMethodMod_gr_117.gif]

is a polynomial of degree n with roots  [Graphics:Images/GraeffeMethodMod_gr_118.gif]  for  [Graphics:Images/GraeffeMethodMod_gr_119.gif].  Furthermore, the roots of  [Graphics:Images/GraeffeMethodMod_gr_120.gif] are approximated by

         [Graphics:Images/GraeffeMethodMod_gr_121.gif]  for   [Graphics:Images/GraeffeMethodMod_gr_122.gif].  

Where the appropriate sign can be determined by evaluating  [Graphics:Images/GraeffeMethodMod_gr_123.gif].  

Proof  Graeffe's Method

 

Algorithm (Graeffe's Method).  To find all the roots of  the polynomial  [Graphics:Images/GraeffeMethodMod_gr_124.gif] of degree n which has real distinct roots  [Graphics:Images/GraeffeMethodMod_gr_125.gif].  Use the Graeffe iteration

        [Graphics:Images/GraeffeMethodMod_gr_126.gif].

Computer Programs  Graeffe's Method

Mathematica Subroutine (Graeffe's Method)).

[Graphics:Images/GraeffeMethodMod_gr_127.gif]

Example 3.  Use Graeffe's root squaring method to find the roots of  [Graphics:Images/GraeffeMethodMod_gr_128.gif].  
Show each step in the process.

Solution 3.

 

Example 4.  Use Graeffe's root squaring method to find the roots of  [Graphics:Images/GraeffeMethodMod_gr_156.gif].  
Use the subroutine Graeffe.

Solution 4.

 

Example 5.  Use Graeffe's root squaring method to find the roots of  [Graphics:Images/GraeffeMethodMod_gr_197.gif].  
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   [Graphics:Images/GraeffeMethodMod_gr_256.gif], 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  [Graphics:Images/GraeffeMethodMod_gr_257.gif]  is a root of order  j,  then  [Graphics:Images/GraeffeMethodMod_gr_258.gif]  and the magnitude of the repeated roots are given by the following computation.   After v iterations the polynomial [Graphics:Images/GraeffeMethodMod_gr_259.gif] is constructed
    
    [Graphics:Images/GraeffeMethodMod_gr_260.gif]

The magnitude of the multiple root  [Graphics:Images/GraeffeMethodMod_gr_261.gif]  of order  j,  is computed with the formula

    [Graphics:Images/GraeffeMethodMod_gr_262.gif]  .  

 

Example 6.  Repeated Real Roots Use Graeffe's root squaring method to find the roots of  [Graphics:Images/GraeffeMethodMod_gr_263.gif].
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  [Graphics:Images/GraeffeMethodMod_gr_434.gif].
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  [Graphics:Images/GraeffeMethodMod_gr_520.gif]  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)).

[Graphics:Images/GraeffeMethodMod_gr_521.gif]

Example 8.  Use Graeffe's root squaring method to find the roots of  [Graphics:Images/GraeffeMethodMod_gr_522.gif].  
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  [Graphics:Images/GraeffeMethodMod_gr_534.gif].
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