info prev up next book cdrom email home

Graeffe's Method

A Root-finding method which proceeds by multiplying a Polynomial $f(x)$ by $f(-x)$ and noting that

$\displaystyle f(x)$ $\textstyle =$ $\displaystyle (x-a_1)(x-a_2)\cdots(x-a_n)$ (1)
$\displaystyle f(-x)$ $\textstyle =$ $\displaystyle (-1)^n(x+a_1)(x+a_2)\cdots(x+a_n)$ (2)

so the result is
\begin{displaymath}
f(x)f(-x)=(-1)^n(x^2-{a_1}^2)(x^2-{a_2}^2)\cdots(x^2-{a_n}^2).
\end{displaymath} (3)

Repeat $\nu$ times, then write this in the form
\begin{displaymath}
y^n+b_1y^{n-1}+\ldots+b_n=0
\end{displaymath} (4)

where $y\equiv x^{2\nu}$. Since the coefficients are given by Newton's Relations
$\displaystyle b_1$ $\textstyle =$ $\displaystyle -(y_1+y_2+\ldots+y_n)$ (5)
$\displaystyle b_2$ $\textstyle =$ $\displaystyle (y_1y_2+y_1y_3+\ldots+y_{n-1}y_n)$ (6)
$\displaystyle b_n$ $\textstyle =$ $\displaystyle (-1)^n y_1y_2\cdots y_n,$ (7)

and since the squaring procedure has separated the roots, the first term is larger than rest. Therefore,
$\displaystyle b_1$ $\textstyle \approx$ $\displaystyle -y_1$ (8)
$\displaystyle b_2$ $\textstyle \approx$ $\displaystyle y_1 y_2$ (9)
$\displaystyle b_n$ $\textstyle \approx$ $\displaystyle (-1)^n y_1y_2\cdots y_n,$ (10)

giving
$\displaystyle y_1$ $\textstyle \approx$ $\displaystyle -b_1$ (11)
$\displaystyle y_2$ $\textstyle \approx$ $\displaystyle -{b_2\over b_1}$ (12)
$\displaystyle y_n$ $\textstyle \approx$ $\displaystyle -{b_n\over b_{n-1}}.$ (13)

Solving for the original roots gives
$\displaystyle a_1$ $\textstyle \approx$ $\displaystyle {\root {2\nu} \of {-b_1}}$ (14)
$\displaystyle a_2$ $\textstyle \approx$ $\displaystyle {\root {2\nu} \of {-{b_2\over b_1}}}$ (15)
$\displaystyle a_n$ $\textstyle \approx$ $\displaystyle {\root {2\nu} \of {-{b_n\over b_{n-1}}}}.$ (16)

This method works especially well if all roots are real.


References

von Kármán, T. 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.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-25