|
Die Newton-Maehly-Methode |
| |
- Um alle Nullstellen eines reellen Polynoms, das nur
reelle Nullstellen besitzt, zu berechnen, kann man
das Newton Verfahren verwenden. Dabei wird eine berechnete Nullstelle durch
Polynomdivision abgespalten und das Newtonverfahren fortgesetzt, bis alle
Nullstellen gefunden sind.
Weil das Newtonverfahren in diesem Fall rechts von der grössten Nullstelle
streng monoton konvergiert, hat man hier globale Konvergenz vorliegen.
Deshalb werden hier die Nullstellen von rechts nach links abgearbeitet.
Diese Abspaltung (auch ''Deflation'' genannt) kann sich aber durch Rundungsfehler
und die Ungenauigkeit der abgespaltenen Nullstelle sehr
ungünstig auswirken (Bsp.: Wilkinsons ''perfides'' Polynom mit den
Nullstellen 1,2,...,20)
- Alternativ wird beim Newton-Maehly-Verfahren diese Abspaltung nur formal
vorgenommen und damit eine neue Verfahrensvorschrift erzeugt.
- Da unter den angegebenen Bedingungen das Newton-Verfahren bei
Startwert rechts von der grössten Nullstelle monoton gegen diese
konvergiert, hat man ein sicheres Abbruchkriterium, nämlich die
Verletzung der Monotonie in der berechneten Folge. Demgemäß
brechen wir die Iteration mit einer Fehlermeldung ab, wenn die Monotonie
verletzt ist, aber der Polynomwert betragsmässig deutlich über
dem Rundungsfehlerniveau liegt.
|
| |
|
Die Eingaben |
| |
- Anzugeben ist der Grad n des Polynoms.
- Sie haben die Wahl, die Polynomkoeffizienten durch Vorgabe nur
reeller Nullstellen erzeugen zu lassen und dann die Nullstellen
zurückzurechnen oder die Koeffizienten direkt einzugeben.
Im letzteren Fall:
- n+1 Koeffizienten an,
... ,a0, in dieser Reihenfolge. an ist der Höchstkoeffizient.
Wichtig : an*a0 ungleich 0
!
|
| |
|
Die Ausgaben |
| |
- Ausgegeben werden die Eingabedaten.
- Das Resultat des Newton-Maehly-Verfahrens.
- Zum Vergleich das Resultat des Newton-Verfahrens mit expliziter Abspaltung der
Nullstellen.
- Ferner wird ein Funktionsplot der Situation ausgegeben.
|
| |
|
Fragen ?! |
| |
- Wie steht es mit dem Rechenaufwand und der Genauigkeit ?
- Was geschieht, wenn ein Paar konjugiert komplexer Nullstellen vorliegt ?
- Wie verhält sich das Verfahren bei mehrfachen reellen Nullstellen ?
|
| |
|
|
| |
|
|