Dandelin-Gräffe-Verfahren

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:

$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 $x_1,x_2,\dots ,x_n$. Dann ist

$p(-x)=(-1{)}^n(x+x_1)(x+x_2)\cdots (x+x_n).$

und

$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 $x^2-x_k^2=(x-x_k)(x+x_k)$ benutzt wurde.

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

Man hat nach der n-ten Iteration

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

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

$b_1=-(y_1+y_2+\cdots +y_n)$

$b_2=y_1{y}_2+y_1{y}_3+\cdots +y_{n-1}{y}_n$

$\cdots$

$b_n=(-1{)}^n{y}_1{y}_2\cdots y_n$

Da nach Wurzeltrennung der führende Term $y_1$ dominiert, kann man nähern:

$b_1\approx -y_1$

$b_2\approx y_1{y}_2$

$\dots$

$b_n=(-1{)}^n{y}_1{y}_2\cdots y_n$

und damit:

$y_1\approx -b_1$

$y_2\approx -\frac{b_2}{b_1}$

$\dots$

$y_n\approx -\frac{b_n}{b_{n-1}}$

Für die Wurzeln der Ausgangsgleichung $p(x)$ ergibt sich:

$x_1\approx \sqrt[2^n]{-b_1}$

$x_2\approx \sqrt[2^n]{-\frac{b_2}{b_1}}$

$\dots$

$x_n\approx \sqrt[2^n]{-\frac{b_n}{b_{n-1}}}$

Eine nützliche Beziehung beim Übergang von

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

zu

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

ist die Beziehung zwischen den Koeffizienten:

$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