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 d eine natürliche Zahl und eine mindestens (d+1)-fach stetig differenzierbare Funktion, die im Intervall I eine einfache Nullstelle a besitze, d. h. . Sei ein Startwert nahe genug an a. Dann konvergiert die durch die Iteration
erzeugte Folge sukzessiver Approximationen mit Konvergenzordnung d+1 gegen a. Das heißt, es gibt eine Konstante K>0 mit
- .
Für d=1 ergibt sich das Newton-Verfahren, für d=2 das Halley-Verfahren.
Motivation
Hat f eine einfache Nullstelle in a, so gibt es eine d-fach stetig differenzierbare Funktion g mit und . Die reziproke Funktion (1/f) hat einen Pol der Ordnung 1 in a. Liegt x nahe a, so wird die Taylorentwicklung von 1/f in x von diesem Pol dominiert,
Betrachtet man g(x+h) als sich langsam ändernd bis nahezu konstant zu f'(a), dann sind die Taylorkoeffizienten umgekehrt proportional zu den Potenzen von (x-a), also
für k = 1, …, d
Beispiel
Die von Newton zur Demonstration seines Verfahrens benutzte Polynomgleichung war . In einem ersten Schritt wurde beobachtet, dass es eine Nullstelle nahe x=2 geben muss. Durch Einsetzen von x=2+h erhält man erst
und anschließend durch Invertieren dieses Polynoms als Taylorreihe
Das Ergebnis des ersten Schritts des Householder-Verfahrens einer gegebenen Ordnung d erhält man auch, indem man den Koeffizienten des Grades d 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 d gültige Dezimalstellen für den ersten Schritt im Verfahren der Ordnung d.
Quellen
- Alston Scott Householder, Numerical Treatment of a Single Nonlinear Equation, McGraw Hill Text, New York, 1970. ISBN 0-07-030465-3
- Newton's method and high order iterations, Pascal Sebah and Xavier Gourdon, 2001 (Auf der Seite ist eine Postscript-Version mit korrekter Formeldarstellung verlinkt.)