Householder-Verfahren

Die Householder-Verfahren s​ind eine Gruppe v​on numerischen Verfahren z​ur Bestimmung v​on Nullstellen e​iner skalaren reellen Funktion. Sie s​ind nach Alston Scott Householder benannt.

Beschreibung des Verfahrens

Sei ${\displaystyle d}$ eine natürliche Zahl und ${\displaystyle f\colon I\subset \mathbb {R} \to \mathbb {R} }$ eine mindestens ${\displaystyle (d+1)}$-fach stetig differenzierbare Funktion, die im Intervall ${\displaystyle I}$ eine einfache Nullstelle ${\displaystyle a}$ besitze, d. h. ${\displaystyle f'(a)\neq 0}$. Sei ${\displaystyle x_{0}}$ ein Startwert nahe genug an ${\displaystyle a}$. 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 }$

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

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

Für ${\displaystyle d=1}$ ergibt sich das Newton-Verfahren, für ${\displaystyle d=2}$ das Halley-Verfahren.

Motivation

Hat ${\displaystyle f}$ eine einfache Nullstelle in ${\displaystyle a}$, so gibt es eine ${\displaystyle d}$-fach stetig differenzierbare Funktion ${\displaystyle g}$ mit ${\displaystyle g(a)=f'(a)\neq 0}$ und ${\displaystyle f(x)=g(x)(x-a)}$. Die reziproke Funktion ${\displaystyle {\frac {1}{f}}}$ hat einen Pol der Ordnung ${\displaystyle 1}$ in ${\displaystyle a}$. Liegt ${\displaystyle x}$ nahe ${\displaystyle a}$, so wird die Taylorentwicklung von ${\displaystyle {\frac {1}{f}}}$ in ${\displaystyle x}$ 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}}}$

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

für ${\displaystyle k=1,\ldots ,d.}$

Beispiel

Die von Newton zur Demonstration seines Verfahrens benutzte Polynomgleichung war ${\displaystyle x^{3}-2x-5=0}$. In einem ersten Schritt wurde beobachtet, dass es eine Nullstelle nahe ${\displaystyle x=2}$ geben muss. Durch Einsetzen von ${\displaystyle x=2+h}$ erhält man erst

${\displaystyle f(2+h)=-1+10h+6h^{2}+h^{3}}$

und anschließend d​urch Invertieren dieses Polynoms a​ls 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}}}$

Das Ergebnis des ersten Schritts des Householder-Verfahrens einer gegebenen Ordnung ${\displaystyle d}$ erhält man auch, indem man den Koeffizienten des Grades ${\displaystyle 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 ${\displaystyle d}$ gültige Dezimalstellen für den ersten Schritt im Verfahren der Ordnung ${\displaystyle 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.)