Das Dandelin-Gräffe-Verfahren, auch Gräffe-Verfahren, ist eine Methode der näherungsweisen Bestimmung der Nullstellen (Wurzeln) eines Polynoms n-ten Grades und beruht darauf, durch iteratives Quadrieren der Wurzeln diese zu trennen, wobei das Quadrieren implizit ausgeführt wird durch Transformation des Ausgangspolynoms.

Es wurde unabhängig von Karl Heinrich Gräffe (1837), Germinal Pierre Dandelin (1826) und Nikolai Iwanowitsch Lobatschewski (1834) entwickelt. Es funktioniert am besten für Polynome mit reellen, einfachen Wurzeln, kann aber auch an allgemeinere Fälle angepasst werden. Später wurden verschiedene Varianten des klassischen Dandelin-Graeffe-Verfahrens entwickelt.

Da es keine Anfangsabschätzung der Lage der Wurzeln erfordert, kann es als Ausgangspunkt genauerer Methoden der Wurzelbestimmung dienen, die eine solche Anfangsabschätzung fordern.

Beschreibung

Das Polynom n-ten Grades, dessen Wurzeln man bestimmen will, sei:

${\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}\,}$

mit Wurzeln ${\displaystyle x_{1},\,x_{2},\dots ,\,x_{n}}$. Dann ist

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

und

${\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}}$

wobei ${\displaystyle x^{2}-x_{k}^{2}=(x-x_{k})(x+x_{k})}$ benutzt wurde.

Schreibt man ${\displaystyle y=x^{2}}$, hat ${\displaystyle q(y)}$ die Quadrate der Wurzeln der Ausgangsgleichung ${\displaystyle p(x)}$ als Lösung. Waren zwei Wurzeln von p(x) vorher durch einen Faktor ${\displaystyle \rho }$ getrennt, sind sie es bei ${\displaystyle q(y)}$ durch einen Faktor ${\displaystyle \rho ^{2}}$ und für ${\displaystyle \rho >1}$ werden die Wurzeln bei Iteration des Verfahrens schnell getrennt:

Man hat nach der n-ten Iteration

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

mit ${\displaystyle y=x^{2n}}$ hat man mit den Vieta-Formeln:

${\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}}$

Da nach Wurzeltrennung der führende Term ${\displaystyle y_{1}}$ dominiert, kann man nähern:

${\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}}$

und damit:

${\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}}}}$

Für die Wurzeln der Ausgangsgleichung ${\displaystyle p(x)}$ ergibt sich:

${\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}}}}}}$

Eine nützliche Beziehung beim Übergang von

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

zu

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

ist die Beziehung zwischen den Koeffizienten:

${\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.\,}$

Siehe auch

• Trennkreisverfahren

Weblinks

• Graeffe-Methode bei Mathworld

Einzelnachweise

1. ↑ Alston Scott Householder: Dandelin, Lobačevskiǐ, or Graeffe?, Amer. Math. Monthly, Band 66, 1959, S. 464–466