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.
Dandelin–Graeffe iteration Let p(x) be a polynomial of degree n
p ( x ) = ( x − x 1 ) ⋯ ( x − x n ) . {\displaystyle p(x)=(x-x_{1})\cdots (x-x_{n}).}
Then
p ( − x ) = ( − 1 ) n ( x + x 1 ) ⋯ ( x + x n ) . {\displaystyle p(-x)=(-1)^{n}(x+x_{1})\cdots (x+x_{n}).}
Let q(x) be the polynomial which has the squares x 1 2 , ⋯ , x n 2 {\displaystyle x_{1}^{2},\cdots ,x_{n}^{2}} as its roots,
q ( x ) = ( x − x 1 2 ) ⋯ ( x − x n 2 ) . {\displaystyle q(x)=\left(x-x_{1}^{2}\right)\cdots \left(x-x_{n}^{2}\right).}
Then we can write:
… excerpt ends here. Continue reading the full article.
