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 ℝ\to ℝ$ eine mindestens $(d+1)$-fach stetig differenzierbare Funktion, die im Intervall $I$ eine einfache Nullstelle $a$ besitze, d. h. $f^{\prime }(a)\ne 0$. Sei $x_0$ 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)}\text{mit }k=0,1,2,\dots$

erzeugte Folge $(x_k{)}_{k\in \mathbb{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^{\prime }(a)\ne 0$ und $f(x)=g(x)(x-a)$. Die reziproke Funktion $\frac{1}{f}$ hat einen Pol der Ordnung $1$ in $a$. Liegt $x$ nahe $a$, so wird die Taylorentwicklung von $\frac{1}{f}$ in $x$ von diesem Pol dominiert,

$\begin{array}{cc}(1/f)(x+h)& =\sum _{k=0}^d(1/f{)}^{(k)}(x)\frac{h^k}{k!}+𝒪(h^{d+1})\\ =\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+𝒪(h^{d+1})\end{array}$

Betrachtet man $g(x+h)$ als sich langsam ändernd bis nahezu konstant zu $f^{\prime }(a)$, dann sind die Taylorkoeffizienten umgekehrt proportional zu den Potenzen von $x-a$, also

$\begin{array}{cc}& (1/f{)}^{(k)}(x)\approx \frac{k!}{f^{\prime }(a)(a-x{)}^{k+1}}\\ ⟹& \frac{(1/f{)}^{(k-1)}(x)}{(1/f{)}^{(k)}(x)}\approx \frac{a-x}{k}\\ ⟹& a\approx x+k\frac{(1/f{)}^{(k-1)}(x)}{(1/f{)}^{(k)}(x)}\end{array}$

für $k=1,\dots ,d.$

Beispiel

Die von Newton zur Demonstration seines Verfahrens benutzte Polynomgleichung war $x^3-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^2+h^3$

und anschließend durch Invertieren dieses Polynoms als Taylorreihe

$\begin{array}{cc}(1/f)(2+h)=& -1-10h-106h^2-1121h^3-11856h^4-125392h^5\\ & -1326177h^6-14025978h^7-148342234h^8-1568904385h^9\\ & -16593123232h^{10}+𝒪(h^{11})\end{array}$

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