Dandelin-Gräffe method

The Dandelin-Gräffe method , also known as Gräffe method , is a method for the approximate determination of the zeros (roots) of a polynomial of the nth degree and is based on separating the roots by iteratively squaring the roots, the squaring being carried out implicitly by transformation of the initial polynomial.

It was developed independently by Karl Heinrich Gräffe (1837), Germinal Pierre Dandelin (1826) and Nikolai Iwanowitsch Lobatschewski (1834). It works best for polynomials with real, simple roots, but can be fitted to more general cases as well. Various variants of the classic Dandelin-Graeffe process were later developed.

Since it does not require an initial estimate of the location of the roots, it can serve as a starting point for more precise methods of root determination that require such an initial estimate.

description

The polynomial of the nth degree whose roots one wants to determine is:

${\displaystyle p(x)=(x-x_{1})(x-x_{2})\cdots (x-x_{n})=x^{n}+a_{1}x^{n-1}+\cdots +a_{n-1}x+a_{n}\,}$

with roots . Then ${\displaystyle x_{1},\,x_{2},\dots ,\,x_{n}}$

${\displaystyle p(-x)=(-1)^{n}\,(x+x_{1})(x+x_{2})\cdots (x+x_{n}).\,}$

and

${\displaystyle q(x)=p(x)\cdot p(-x)=(x^{2}-x_{1}^{2})(x^{2}-x_{2}^{2})\cdots (x^{2}-x_{n}^{2})(-1)^{n}}$

where was used. ${\displaystyle x^{2}-x_{k}^{2}=(x-x_{k})(x+x_{k})}$

If you write, you have the squares of the roots of the output equation as the solution. If two roots of p (x) were previously separated by a factor , they are separated by a factor for and for the roots are quickly separated when the method is iterated: ${\displaystyle y=x^{2}}$ ${\displaystyle q(y)}$ ${\displaystyle p(x)}$ ${\displaystyle \rho }$ ${\displaystyle q(y)}$ ${\displaystyle \rho ^{2}}$ ${\displaystyle \rho >1}$

One has after the nth iteration

${\displaystyle q(y)=y^{n}+b_{1}y^{n-1}+\cdots +b_{n-1}y+b_{n},\,}$

with one has with the Vieta formulas : ${\displaystyle y=x^{2n}}$

${\displaystyle b_{1}=-(y_{1}+y_{2}+\cdots +y_{n})}$

${\displaystyle b_{2}=y_{1}y_{2}+y_{1}y_{3}+\cdots +y_{n-1}y_{n}}$

${\displaystyle \cdots }$

${\displaystyle b_{n}=(-1)^{n}y_{1}y_{2}\cdots y_{n}}$

Since the leading term dominates after the root separation , one can approximate: ${\displaystyle y_{1}}$

${\displaystyle b_{1}\approx -y_{1}}$

${\displaystyle b_{2}\approx y_{1}y_{2}}$

${\displaystyle \dots }$

${\displaystyle b_{n}=(-1)^{n}y_{1}y_{2}\cdots y_{n}}$

and thus:

${\displaystyle y_{1}\approx -b_{1}}$

${\displaystyle y_{2}\approx -{\frac {b_{2}}{b_{1}}}}$

${\displaystyle \dots }$

${\displaystyle y_{n}\approx -{\frac {b_{n}}{b_{n-1}}}}$

For the roots of the initial equation we get: ${\displaystyle p(x)}$

${\displaystyle x_{1}\approx {\sqrt[{2n\,}]{-b_{1}}}}$

${\displaystyle x_{2}\approx {\sqrt[{2n\,}]{-{\frac {b_{2}}{b_{1}}}}}}$

${\displaystyle \dots }$

${\displaystyle x_{n}\approx {\sqrt[{2n\,}]{-{\frac {b_{n}}{b_{n-1}}}}}}$

A useful relationship when transitioning from

${\displaystyle p(x)=x^{n}+a_{1}x^{n-1}+\cdots +a_{n-1}x+a_{n}\,}$

to

${\displaystyle q(y)=y^{n}+b_{1}y^{n-1}+\cdots +b_{n-1}y+b_{n},\,}$

is the relationship between the coefficients:

${\displaystyle b_{k}=(-1)^{k}\,a_{k}^{2}+2\sum _{j=0}^{k-1}(-1)^{j}\,a_{j}a_{2k-j},{\text{ mit }}a_{0}=b_{0}=1.\,}$

See also

• Separation circle method

Web links

• Graeffe method at Mathworld

Individual evidence

1. ^ Alston Scott Householder : Dandelin, Lobačevskiǐ, or Graeffe? , Amer. Math. Monthly, Vol. 66, 1959, pp. 464-466