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.[1] 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.
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}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d08b100d022d15de03e91dcc0bb7aefd017ad1e)
mit Wurzeln
. Dann ist
![{\displaystyle p(-x)=(-1)^{n}\,(x+x_{1})(x+x_{2})\cdots (x+x_{n}).\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef461c015582ffa3e8a3aea47a21932dbc164bab)
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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6c040506e7cf0fde7ef26a179c80b4361a0e63b)
wobei
benutzt wurde.
Schreibt man
, hat
die Quadrate der Wurzeln der Ausgangsgleichung
als Lösung. Waren zwei Wurzeln von p(x) vorher durch einen Faktor
getrennt, sind sie es bei
durch einen Faktor
und für
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},\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/478eda1ecda66b5cae138a512053258873f10deb)
mit
hat man mit den Vieta-Formeln:
![{\displaystyle b_{1}=-(y_{1}+y_{2}+\cdots +y_{n})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9075cb22b77e76f3668077b73a4654f00b463664)
![{\displaystyle b_{2}=y_{1}y_{2}+y_{1}y_{3}+\cdots +y_{n-1}y_{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae698637a957c97ab91ae6e1f6c5a090c197dcec)
![{\displaystyle \cdots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1d67495288eac0fa90d5bbcad7d9a343c15ad56)
![{\displaystyle b_{n}=(-1)^{n}y_{1}y_{2}\cdots y_{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/04f82c4ceb201dc8d6c63bc0e3a7e7910ff3b7e9)
Da nach Wurzeltrennung der führende Term
dominiert, kann man nähern:
![{\displaystyle b_{1}\approx -y_{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cbb0bee5a541b4d9c788da25d1f13ad5aaa895fd)
![{\displaystyle b_{2}\approx y_{1}y_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c49fc8b32d935ad1e484cbe8e5828caf640cc5ca)
![{\displaystyle \dots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/5411a9d9722322917df8faecb6e01b72e3ecede4)
![{\displaystyle b_{n}=(-1)^{n}y_{1}y_{2}\cdots y_{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/04f82c4ceb201dc8d6c63bc0e3a7e7910ff3b7e9)
und damit:
![{\displaystyle y_{1}\approx -b_{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce02b5496cf293348be7cb561407775b2c2d533a)
![{\displaystyle y_{2}\approx -{\frac {b_{2}}{b_{1}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1c214d3d1b46a86c91a51a33dca2a2a8688fcc5)
![{\displaystyle \dots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/5411a9d9722322917df8faecb6e01b72e3ecede4)
![{\displaystyle y_{n}\approx -{\frac {b_{n}}{b_{n-1}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/49252d93eb8e76f75142fe0264175f58452593df)
Für die Wurzeln der Ausgangsgleichung
ergibt sich:
![{\displaystyle x_{1}\approx {\sqrt[{2^{n}\,}]{-b_{1}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/131aadf25fec11cc3d0da67cf1440c3be5b41b1b)
![{\displaystyle x_{2}\approx {\sqrt[{2^{n}\,}]{-{\frac {b_{2}}{b_{1}}}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6d66de4b0c83dc599ad2665179e9b02e574f13f5)
![{\displaystyle \dots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/5411a9d9722322917df8faecb6e01b72e3ecede4)
![{\displaystyle x_{n}\approx {\sqrt[{2^{n}\,}]{-{\frac {b_{n}}{b_{n-1}}}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e0ba27ee0588bf0dc951f2a00434edd8724ef6a)
Eine nützliche Beziehung beim Übergang von
![{\displaystyle p(x)=x^{n}+a_{1}x^{n-1}+\cdots +a_{n-1}x+a_{n}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bba1fbe743131ca0879482750628ab999d74b283)
zu
![{\displaystyle q(y)=y^{n}+b_{1}y^{n-1}+\cdots +b_{n-1}y+b_{n},\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/478eda1ecda66b5cae138a512053258873f10deb)
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.\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/30cda2098c3e522873929ee66292745d76f6ea10)
- ↑ Alston Scott Householder: Dandelin, Lobačevskiǐ, or Graeffe?, Amer. Math. Monthly, Band 66, 1959, S. 464–466