Quelltext der Seite Dandelin-Gräffe-Verfahren

Das '''Dandelin-Gräffe-Verfahren''', auch '''Gräffe-Verfahren''', ist eine Methode der näherungsweisen Bestimmung der [[Nullstelle]]n (Wurzeln) eines [[Polynom]]s 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.<ref>[[Alston Scott Householder]]: ''Dandelin, Lobačevskiǐ, or Graeffe?'', Amer. Math. Monthly, Band 66, 1959, S.  464–466</ref>  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:

:<math>p(x) = (x-x_1)(x-x_2)\cdots(x-x_n) = x^n+a_1x^{n-1}+\cdots+a_{n-1}x+a_n \, </math>

mit Wurzeln <math>x_1,\,x_2,\dots,\, x_n</math>.  Dann ist

:<math>p(-x) = (-1)^n\, (x+x_1)(x+x_2)\cdots(x+x_n). \, </math>

und

:<math>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</math>

wobei <math>x^2-x_k^2=(x-x_k)(x+x_k)</math> benutzt wurde.

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

Man hat nach der n-ten Iteration

:<math>q(y)=y^n+b_1y^{n-1}+\cdots+b_{n-1}y+b_n, \,</math>

mit <math>y=x^{2n}</math> hat man mit den [[Satz von Vieta|Vieta-Formeln]]:

:<math>b_1= -(y_1+y_2+\cdots+y_n)</math>
:<math>b_2= y_1 y_2 + y_1 y_3+\cdots+y_{n-1} y_n</math>
:<math>\cdots</math>
:<math>b_n= (-1)^n y_1 y_2 \cdots y_n</math>

Da nach Wurzeltrennung der führende Term <math>y_1</math> dominiert, kann man nähern:

:<math>  b_1\approx -y_1</math>
:<math> b_2\approx y_1 y_2</math>
:<math>\dots</math>
:<math> b_n = (-1)^n y_1 y_2 \cdots y_n</math>

und damit:
:<math>y_1\approx -b_1</math>
:<math> y_2\approx - \frac {b_2}{b_1}</math>
:<math>\dots</math>
:<math>y_n\approx - \frac {b_n}{b_{n-1}}</math>

Für die Wurzeln der Ausgangsgleichung <math>p(x)</math> ergibt sich:
:<math>x_1\approx \sqrt[2^n\,]{ -b_1}</math>
:<math> x_2\approx \sqrt[2^n\,]{- \frac {b_2}{b_1}}</math>
:<math>\dots</math>
:<math>x_n\approx  \sqrt[2^n\,]{- \frac {b_n}{b_{n-1}}}</math>

Eine nützliche Beziehung beim Übergang von

:<math>p(x)=x^n+a_1x^{n-1}+\cdots+a_{n-1}x+a_n \, </math>

zu

:<math>q(y)=y^n+b_1y^{n-1}+\cdots+b_{n-1}y+b_n, \,</math>

ist die Beziehung zwischen den Koeffizienten:

:<math>b_k=(-1)^k\,a_k^2+2\sum_{j=0}^{k-1}(-1)^j\,a_ja_{2k-j},\text{ mit }a_0=b_0=1. \, </math>

== Siehe auch ==
*[[Trennkreisverfahren]]
== Weblinks ==
*[https://mathworld.wolfram.com/GraeffesMethod.html Graeffe-Methode bei Mathworld]

== Einzelnachweise ==
<references />
[[Kategorie:Numerische Mathematik]]
[[Kategorie:Wurzel (Mathematik)]]