Householder-Verfahren
Die Householder-Verfahren sind eine Gruppe von numerischen Verfahren zur Bestimmung von Nullstellen einer skalaren reellen Funktion. Sie sind nach Alston Scott Householder benannt.
Beschreibung des Verfahrens
Sei eine natürliche Zahl und eine mindestens -fach stetig differenzierbare Funktion, die im Intervall eine einfache Nullstelle besitze, d.h. . Sei ein Startwert nahe genug an . Dann konvergiert die durch die Iteration
erzeugte Folge sukzessiver Approximationen mit Konvergenzordnung gegen . Das heißt, es gibt eine Konstante mit
- .
Für ergibt sich das Newton-Verfahren, für das Halley-Verfahren.
Motivation
Hat eine einfache Nullstelle in , so gibt es eine -fach stetig differenzierbare Funktion mit und . Die reziproke Funktion hat einen Pol der Ordnung in . Liegt nahe , so wird die Taylorentwicklung von in von diesem Pol dominiert,
Betrachtet man als sich langsam ändernd bis nahezu konstant zu , dann sind die Taylorkoeffizienten umgekehrt proportional zu den Potenzen von , also
für
Beispiel
Die von Newton zur Demonstration seines Verfahrens benutzte Polynomgleichung war . In einem ersten Schritt wurde beobachtet, dass es eine Nullstelle nahe geben muss. Durch Einsetzen von erhält man erst
und anschließend durch Invertieren dieses Polynoms als Taylorreihe
Das Ergebnis des ersten Schritts des Householder-Verfahrens einer gegebenen Ordnung erhält man auch, indem man den Koeffizienten des Grades durch seinen linken Nachbarn in dieser Entwicklung teilt. Dies ergibt folgende Näherungen aufsteigender Ordnung
d | x1=2+ |
---|---|
1 | 0,100000000000000000000000000000000 |
2 | 0,094339622641509433962264150943396 |
3 | 0,094558429973238180196253345227476 |
4 | 0,094551282051282051282051282051282 |
5 | 0,094551486538216154140615031261963 |
6 | 0,094551481438752142436492263099119 |
7 | 0,094551481543746895938379484125813 |
8 | 0,094551481542336756233561913325371 |
9 | 0,094551481542324837086869382419375 |
10 | 0,094551481542326678478801765822985 |
Es ergeben sich also in diesem Beispiel etwas mehr als gültige Dezimalstellen für den ersten Schritt im Verfahren der Ordnung
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 09.04. 2020