Algorithmus zu Nullstellen von Polynomen 4. Grades

09/09/2007 - 18:47 von Paul Wellner Bou | Report spam
Hallo und einen schönen Sonntag abend und einen
schönen Montag morgen.

Ich stehe vor einem Problem, bei dem ich Nullstellen eines Polynoms 4.
Grades (im Programm in Matlab/Fortran) berechnen muss. Im Augenblick
suche ich diese über das Newton-Verfahren, was mir allerdings nicht für
alle Bedingungen zufriedenstellende Ergebnisse liefert.

Ich suche nun ein Verfahren, wie man durch "raten" von Nullstellen --
auch wenn dies nur iterativ und nicht exakt geschieht (und wenn, wie
wirkt sich diese Ungenauheit auf die folgenden gefundenen Nullstellen
aus?) -- und dann durch Polynomdivision/Horner-Schema das Polynom
reduzieren kann. Mein Ziel ist einfach, dass ich sicher gehen will,
_alle_ Nullstellen herauszufinden (was beim Newton-Verfahren ja nicht
gegeben ist).

Gibt es in dieser Hinsicht ein schon bekanntes Verfahren? Ich wàre für
Links und/oder Stichwörter, nach denen ich Suchen kann, sehr dankbar.

Im Prinzip suche ich einen Algoritmus, der das auch für Polynome höheren
Grades kann, aber momentan suche ich nur einen, der für Polynome 4.
Grades funktioniert und obendrein bin ich mir auch sicher, dass es genau
zwei verschiedene reelle Nullstellen gibt.

Vielen Dank und beste Grüße
Paul Wellner Bou
 

Lesen sie die antworten

#1 Thomas Nordhaus
09/09/2007 - 19:52 | Warnen spam
Paul Wellner Bou schrieb:
Hallo und einen schönen Sonntag abend und einen
schönen Montag morgen.

Ich stehe vor einem Problem, bei dem ich Nullstellen eines Polynoms 4.
Grades (im Programm in Matlab/Fortran) berechnen muss. Im Augenblick
suche ich diese über das Newton-Verfahren, was mir allerdings nicht für
alle Bedingungen zufriedenstellende Ergebnisse liefert.

Ich suche nun ein Verfahren, wie man durch "raten" von Nullstellen --
auch wenn dies nur iterativ und nicht exakt geschieht (und wenn, wie
wirkt sich diese Ungenauheit auf die folgenden gefundenen Nullstellen
aus?) -- und dann durch Polynomdivision/Horner-Schema das Polynom
reduzieren kann. Mein Ziel ist einfach, dass ich sicher gehen will,
_alle_ Nullstellen herauszufinden (was beim Newton-Verfahren ja nicht
gegeben ist).



Das ist das übliche Verfahren: Nullstelle numerisch berechnen (was
sonst? - ich würde das nicht "Raten" nennen), Polynomdivision, nàchste
Nullstelle berechnen usw. So stellst du sicher, dass immer neue
Nullstellen berechnet werden. Man macht oft noch einen Zwischenschritt
("Polieren" genannt), in dem man eine gefundene Nàherungslösung wieder
in das Ausgangspolynom steckt und dann mit einem schnellen Verfahren
(also Newton...) die Nullstelle genauer berechnet. Durch Polynomdivision
können sich nàmlich numerische Abweichungen ergeben.

Zur iterativen Berechnung der Nullstellen kannst du jedes Verfahren
benutzen. Am besten natürlich eines, das mit *Sicherheit* gegen eine
Nullstelle konvergiert. In den "Numerical Recipes" habe ich eine
FORTRAN-Implementierung des *Laguerre-Verfahrens* gefunden. Das arbeitet
komplex und liefert für jeden Startwert eine (i.a. komplexe) Nullstelle
des Polynoms.


Gibt es in dieser Hinsicht ein schon bekanntes Verfahren? Ich wàre für
Links und/oder Stichwörter, nach denen ich Suchen kann, sehr dankbar.



Ja, google mal nach Laguerre-Verfahren.


Im Prinzip suche ich einen Algoritmus, der das auch für Polynome höheren
Grades kann, aber momentan suche ich nur einen, der für Polynome 4.
Grades funktioniert und obendrein bin ich mir auch sicher, dass es genau
zwei verschiedene reelle Nullstellen gibt.




Vielleicht funktioniert's ja auch schon mit einem einfachen
Bisektions-Verfahren. Dazu brauchst du Anfangswerte an denen die
Polynomfunktion unterschiedliches Vorzeichen hat. Wenn du solche Werte
kennst, kannst du eine Nullstelle schnell berechnen. Die zweite relle
Nullstelle làsst sich dann durch Diskussion des resultierenden
reduzierten kubischen Polynoms schnell eingrenzen und




Vielen Dank und beste Grüße
Paul Wellner Bou




Thomas Nordhaus

Ähnliche fragen