TOPICS
Search

Graeffe's Method

A root-finding method which was among the most popular methods for finding roots of univariate polynomials in the 19th and 20th centuries. It was invented independently by Graeffe, Dandelin, and Lobachevsky (Householder 1959, Malajovich and Zubelli 2001). Graeffe's method has a number of drawbacks, among which are that its usual formulation leads to exponents exceeding the maximum allowed by floating-point arithmetic and also that it can map well-conditioned polynomials into ill-conditioned ones. However, these limitations are avoided in an efficient implementation by Malajovich and Zubelli (2001).

The method proceeds by multiplying a polynomial f(x) by f(-x) and noting that

f(x)=(x-a_1)(x-a_2)...(x-a_n)
(1)
f(-x)=(-1)^n(x+a_1)(x+a_2)...(x+a_n)
(2)

so the result is

f(x)f(-x)=(-1)^n(x^2-a_1^2)(x^2-a_2^2)...(x^2-a_n^2).
(3)

repeat nu times, then write this in the form

y^n+b_1y^(n-1)+...+b_n=0
(4)

where y=x^(2nu). Since the coefficients are given by Vieta's formulas

b_1=-(y_1+y_2+...+y_n)
(5)
b_2=(y_1y_2+y_1y_3+...+y_(n-1)y_n)
(6)
b_n=(-1)^ny_1y_2...y_n,
(7)

and since the squaring procedure has separated the roots, the first term is larger than rest. Therefore,

b_1 approx -y_1
(8)
b_2 approx y_1y_2
(9)
b_n approx (-1)^ny_1y_2...y_n,
(10)

giving

y_1 approx -b_1
(11)
y_2 approx -(b_2)/(b_1)
(12)
y_n approx -(b_n)/(b_(n-1)).
(13)

Solving for the original roots gives

a_1 approx RadicalBox[{-, {b, _, 1}}, {2, nu}]
(14)
a_2 approx RadicalBox[{-, {{(, {b, _, 2}, )}, /, {(, {b, _, 1}, )}}}, {2, nu}]
(15)
a_n approx RadicalBox[{-, {{(, {b, _, n}, )}, /, {(, {b, _, {(, {n, -, 1}, )}}, )}}}, {2, nu}].
(16)

This method works especially well if all roots are real.

Explore with Wolfram|Alpha

References

Bini, D. and Pan, V. Y. "Graeffe's, Chebyshev-Like, and Cardinal's Processes for Splitting a Polynomial Into Factors." J. Complexity 12, 492-511, 1996.Brodetsky, S. and Smeal, G. "on Graeffe's Method for Complex Roots of Algebraic Equations." Proc. Cambridge Philos. Soc. 22, 83-87, 1924.Cajori, F. "The Dandelin-Gräffe Method." A History of Mathematics, 5th ed. New York: Chelsea, p. 364, 1962.Dedieu, J.-P. "À Propos de la méthode de Dandelin-Graeffe." C. R. Acad. Sci. Paris Sér. I Math 309, 1019-1022, 1989.Grau, A. A. "On the Reduction of Number Range in the Use of the Graeffe Process." J. Assoc. Comput. Mach. 10, 538-544, 1963.Householder, A. S. "Dandelin, Lobačevskiĭ, or Graeffe?" Amer. Math. Monthly 66, 464-466, 1959.Jana, P. and Sinha, B. "Fast Parallel Algorithms for Graeffe's Root Squaring." Comput. Math. Appl. 35, 71-80, 1998.Kármán, T. Von and Biot, M. a. "Squaring the Roots (Graeffe's Method)." §5.8.C in Mathematical Methods in Engineering: An Introduction to the Mathematical Treatment of Engineering Problems. New York: Mcgraw-Hill, pp. 194-196, 1940.Malajovich, G. and Zubelli, J. P. "Tangent Graeffe Iteration." 27 Aug 1999. http://arxiv.org/abs/math.AG/9908150.Malajovich, G. and Zubelli, J. P. "On the Geometry of Graeffe Iteration." J. Complexity 17, 541-573, 2001.Ostrowski, A. "Recherches sur la méthode de Graeffe et les zéros des polynomes et des séries de Laurent." Acta Math. 72, 99-155, 1940.Ostrowski, A. "Recherches sur la méthode de Graeffe et les zéros des polynomes et des séries de Laurent. Chapitres III et IV." Acta Math. 72, 157-257, 1940.Pan, V. Y. "Solving a Polynomial Equation: Some History and Recent Progress." SIAM Rev. 39, 187-220, 1997.Runge, C. "The Dandelin-Gräffe Method." In Praxis der Gleichungen. Berlin and Leipzig, Germany: de Gruyter, pp. 136-158, 1921.Whittaker, E. T. and Robinson, G. "The Root-Squaring Method of Dandelin, Lobachevsky, and Graeffe." §54 in The Calculus of Observations: A Treatise on Numerical Mathematics, 4th ed. New York: Dover, pp. 106-112, 1967.

Referenced on Wolfram|Alpha

Graeffe's Method

Cite this as:

Weisstein, Eric W. "Graeffe's Method." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GraeffesMethod.html

Subject classifications