Graeffe's Method

The Goal

If the roots of are real and distinct then successive root squaring will generate a sequence of polynomials,where each polynomialhas degreen.The roots ofare ,and ifvis large enough, then the roots ofwill be widely separated.The rootsofare 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 sequenceas follows:



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

for.

Where the appropriate sign can be determined by evaluating.

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

.

Mathematica Subroutine (Graeffe's Method)).

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.Ifis a root of orderj,thenand the magnitude of the repeated roots are given by the following computation.After v iterations the polynomial is constructed



The magnitude of the multiple rootof orderj,is computed with the formula

.

The Efficient Graeffe Subroutine

It can be observed that the functionsare 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.

Mathematica Subroutine (Graeffe's Method)).