Dandelin–Gräffe method

In mathematics, Graeffe's method or Dandelin–Lobachesky–Graeffe method is an algorithm for finding all of the roots of a polynomial. It was developed independently by Germinal Pierre Dandelin in 1826 and Lobachevsky in 1834. In 1837 Karl Heinrich Gräffe also discovered the principal idea of the method. The method separates the roots of a polynomial by squaring them repeatedly. This squaring of the roots is done implicitly, that is, only working on the coefficients of the polynomial. Finally, Viète's formulas are used in order to approximate the roots.

Let $p (x)$ be a polynomial of degree $n$

Then

Let $q (x)$ be the polynomial which has the squares $x_{1}^{2},\cdots ,x_{n}^{2}$ as its roots,

Then we can write:

$q (x)$ can now be computed by algebraic operations on the coefficients of the polynomial $p (x)$ alone. Let:

then the coefficients are related by

Graeffe observed that if one separates $p (x)$ into its odd and even parts:

then one obtains a simplified algebraic expression for $q (x)$ :

This expression involves the squaring of two polynomials of only half the degree, and is therefore used in most implementations of the method.

Iterating this procedure several times separates the roots with respect to their magnitudes. Repeating k times gives a polynomial of degree $n$ :

...
Wikipedia