In mathematics, Graeffe's method or Dandelin–Lobachesky–Graeffe method is an algorithm for finding all of the roots of a polynomial. It was developed independently by Germinal Pierre Dandelin in 1826 and Lobachevsky in 1834. In 1837 Karl Heinrich Gräffe also discovered the principal idea of the method. The method separates the roots of a polynomial by squaring them repeatedly. This squaring of the roots is done implicitly, that is, only working on the coefficients of the polynomial. Finally, Viète's formulas are used in order to approximate the roots.
Contents
Dandelin–Graeffe iteration
Let p(x) be a polynomial of degree n
Then
Let q(x) be the polynomial which has the squares
Then we can write:
q(x) can now be computed by algebraic operations on the coefficients of the polynomial p(x) alone. Let:
then the coefficients are related by
Graeffe observed that if one separates p(x) into its odd and even parts:
then one obtains a simplified algebraic expression for q(x):
This expression involves the squaring of two polynomials of only half the degree, and is therefore used in most implementations of the method.
Iterating this procedure several times separates the roots with respect to their magnitudes. Repeating k times gives a polynomial of degree n:
with roots
If the magnitudes of the roots of the original polynomial were separated by some factor
Classical Graeffe's method
Next the Vieta relations are used
If the roots
The coefficients of the iterated polynomial can then be approximated by their leading term,
implying
Finally, logarithms are used in order to find the absolute values of the roots of the original polynomial. These magnitudes alone are already useful to generate meaningful starting points for other root-finding methods.
To also obtain the angle of these roots, a multitude of methods has been proposed, the most simple one being to successively compute the square root of a (possibly complex) root of
Graeffe's method works best for polynomials with simple real roots, though it can be adapted for polynomials with complex roots and coefficients, and roots with higher multiplicity. For instance, it has been observed that for a root
for
From a numerical point of view, this method is problematic since the coefficients of the iterated polynomials span very quickly many orders of magnitude, which implies serious numerical errors. One second, but minor concern is that many different polynomials lead to the same Graeffe iterates.
Tangential Graeffe method
This method replaces the numbers by truncated power series of degree 1, also known as dual numbers. Symbolically, this is achieved by introducing an "algebraic infinitesimal"
Thus the value of
This kind of computation with infinitesimals is easy to implement analogous to the computation with complex numbers. If one assumes complex coordinates or an initial shift by some randomly chosen complex number, then all roots of the polynomial will be distinct and consequently recoverable with the iteration.
Renormalization
Every polynomial can be scaled in domain and range such that in the resulting polynomial the first and the last coefficient have size one. If the size of the inner coefficients is bounded by M, then the size of the inner coefficients after one stage of the Graeffe iteration is bounded by
To overcome the limit posed by the growth of the powers, Malajovich–Zubelli propose to represent coefficients and intermediate results in the kth stage of the algorithm by a scaled polar form
where
Multiplication of two numbers of this type is straightforward, whereas addition is performed following the factorization
The coefficients