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
![{\displaystyle x_{k+1}=x_{k}+d{\frac {(1/f)^{(d-1)}(x_{k})}{(1/f)^{(d)}(x_{k})}}\quad {\text{mit }}k=0,1,2,\dots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/b84f51c74f2e178682978219ad2afd6f26d32add)
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,
![{\displaystyle {\begin{aligned}(1/f)(x+h)&=\sum _{k=0}^{d}(1/f)^{(k)}(x){\frac {h^{k}}{k!}}+{\mathcal {O}}(h^{d+1})\\[1em]={\frac {1}{g(x+h)(x+h-a)}}&={\frac {1}{g(x+h)(a-x)}}\sum _{k=0}^{d}\left({\frac {h}{a-x}}\right)^{k}+{\mathcal {O}}(h^{d+1})\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f779c9f0664114a33703eade94df3e72b50f37de)
Betrachtet man
als sich langsam ändernd bis nahezu konstant zu
, dann sind die Taylorkoeffizienten umgekehrt proportional zu den Potenzen von
, also
![{\displaystyle {\begin{aligned}&(1/f)^{(k)}(x)\approx {\frac {k!}{f'(a)\,(a-x)^{k+1}}}\\\implies &{\frac {(1/f)^{(k-1)}(x)}{(1/f)^{(k)}(x)}}\approx {\frac {a-x}{k}}\\\implies &a\approx x+k{\frac {(1/f)^{(k-1)}(x)}{(1/f)^{(k)}(x)}}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0968199e9bb2229588925461bbb6db4738ef0e77)
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
![{\displaystyle f(2+h)=-1+10h+6h^{2}+h^{3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/16ba5ac10d2c00ec2c9947bcfc9b71ff7b7492e4)
und anschließend durch Invertieren dieses Polynoms als Taylorreihe
![{\displaystyle {\begin{aligned}(1/f)(2+h)=&-1-10\,h-106\,h^{2}-1121\,h^{3}-11856\,h^{4}-125392\,h^{5}\\&-1326177\,h^{6}-14025978\,h^{7}-148342234\,h^{8}-1568904385\,h^{9}\\&-16593123232\,h^{10}+{\mathcal {O}}(h^{11})\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2bb24dd5be699183cf3f72be6a55b6610327c011)
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
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.)