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 $f:I\subset\R\to\R$ eine mindestens (d+1)-fach stetig differenzierbare Funktion, die im Intervall I eine einfache Nullstelle a besitze, d.h. $f'(a)\ne0$. Sei x₀ ein Startwert nahe genug an a. Dann konvergiert die durch die Iteration

$x_{k+1}=x_k+d\frac{(1/f)^{(d-1)}(x_k)}{(1/f)^{(d)}(x_k)}$, k=0,1,2,...,

erzeugte Folge $(x_k)_{k\in\N}$ sukzessiver Approximationen mit Konvergenzordnung d+1 gegen a. Das heißt, es gibt eine Konstante K>0 mit

$|x_{k+1}-a|\le K\cdot |x_k-a|^{d+1}$.

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 $g(a)=f'(a)\ne 0$ und f(x) = g(x)(x − a). 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,

$\begin{align} (1/f)(x+h) &=\sum_{k=0}^d (1/f)^{(k)}(x)\frac{h^k}{k!}+O(h^{d+1})\\[1em] = \frac1{g(x+h)(x+h-a)} &=\frac1{g(x+h)(a-x)}\sum_{k=0}^d\left(\frac{h}{a-x}\right)^k+O(h^{d+1}) \end{align}$

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

$\begin{align} &(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{align}$

für k=1,...,d

Beispiel

Die von Newton zur Demonstration seines Verfahrens benutzte Polynomgleichung war x³ − 2x − 5 = 0. 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

f(2 + h) = − 1 + 10h + 6h² + h³

und anschließend durch Invertieren dieses Polynoms als Taylorreihe

$\begin{align} (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} +O(h^{11}) \end{align}$

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.)