Graeffe's method

Redirect to:

• Root-squaring method

1. REDIRECT Dandelin-Gräffe method
2. REDIRECT Dandelin-Graeffe method
3. REDIRECT Graeffe-Lobachevsky method

Graeffe's method is an algorithm for finding multiple roots of a polynomial. It was developed independently by Graeffe, Dandelin, and Lobachevsky (MathWorld). The method separates the roots of a polynomial by squaring them repeatedly, and uses the Vieta relations in order to approximate the roots.

Let $p(x)$ be an $n^{th}$ degree polynomial.

$p(x)=(x-x_{1})(x-x_{2})...(x-x_{n})$

Then $p(-x)=(-1)^{n}(x+x_{1})(x+x_{2})...(x+x_{n})$

Hence $q(x^{2})=p(x)p(-x)=(-1)^{n}(x^{2}-x_{1}^{2})(x^{2}-x_{2}^{2})...(x^{2}-x_{n}^{2})$

The roots of $q(x^{2})$ (when viewed as a polynomial in the variable $x^{2}$) are $x_{1}^{2},x_{2}^{2},...,x_{n}^{2}$. We have sqaured the roots of our original polynomial $p(x)$. Iterating this procedure several times separates the roots with respect to their magnitudes. Repeating k times gives a polynomial in the variable $y:=x^{2k}$ of degree n. Write this polynomial as

$q^{k}(y)=y^{n}+a_{1}y^{n-1}+...+a_{n}$

Next the Vieta relations are used

$a_{1}=-(y_{1}+y_{2}+...+y_{n})$

$a_{2}=y_{1}y_{2}+y_{1}y_{3}+...+y_{n-1}y_{n}$

$a_{n}=(-1)^{n}(y_{1}y_{2}...y_{n})$

So that if the roots are sufficiently separated

$a_{1}\approx -y_{1}$

$a_{2}\approx y_{1}y_{2}$ and so on.

Finally logarithms are used in order to find the roots of the original polynomial. Graeffe's method works best for polynomials with real simple roots, though it can be adapted for polynomials with complex roots and double roots.

See also

Root-finding algorithm Vieta relations

External links

MathWorld: Graeffe's Method