Graeffe's Method

A Root-finding method which proceeds by multiplying a Polynomial by 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.