Graeffe's method

From Wikipedia, the free encyclopedia

Graeffe's method is an algorithm for finding multiple roots of a polynomial. It was developed independently by Karl Heinrich Gräffe, Dandelin, and Lobachevsky. 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 t h$ 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 squared 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^{2^k}$ of degree n. Write this polynomial as $q k (y) = y n + a 1 y n - 1 + ... + a n$
with roots $y 1, y 2,..., y 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 simple real roots, though it can be adapted for polynomials with complex roots and double roots.