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 <math>d</math> eine natürliche Zahl und <math>f \colon I\subset\R\to\R</math> eine mindestens <math>(d+1)</math>-fach stetig differenzierbare Funktion, die im Intervall <math>I</math> eine einfache Nullstelle <math>a</math> besitze, d. h. <math>f'(a)\ne0</math>. Sei <math> x_0</math> ein Startwert nahe genug an <math>a</math>. Dann konvergiert die durch die Iteration

<math>

 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

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

<math>|x_{k+1}-a|\le K\cdot |x_k-a|^{d+1}</math>.

Für <math>d=1</math> ergibt sich das Newton-Verfahren, für <math>d=2</math> das Halley-Verfahren.

Motivation

Hat <math>f</math> eine einfache Nullstelle in <math>a</math>, so gibt es eine <math>d</math>-fach stetig differenzierbare Funktion <math>g</math> mit <math>g(a)=f'(a)\ne 0</math> und <math>f(x)=g(x)(x-a)</math>. Die reziproke Funktion <math>\frac{1}{f}</math> hat einen Pol der Ordnung <math>1</math> in <math>a</math>. Liegt <math>x</math> nahe <math>a</math>, so wird die Taylorentwicklung von <math>\frac{1}{f}</math> in <math>x</math> von diesem Pol dominiert,

<math>\begin{align}

 (1/f)(x+h)
 &=\sum_{k=0}^d (1/f)^{(k)}(x)\frac{h^k}{k!} + \mathcal 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 + \mathcal O(h^{d+1})

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

<math>\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}</math> für <math>k = 1, \ldots , d.</math>

Beispiel

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

<math>f(2+h)=-1 + 10 h + 6 h^2 + h^3</math>

und anschließend durch Invertieren dieses Polynoms als Taylorreihe

<math>\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} + \mathcal O(h^{11})

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

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