**for**

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

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

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

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

Use the subroutine **Graeffe**.

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

Use the subroutine **Graeffe**.

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

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

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

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

Use the subroutine **Graeffe2**.

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