Householder-Verfahren


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.

Inhaltsverzeichnis

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 x0 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)(xa). 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 x3 − 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 + 6h2 + h3

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

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Householder-Matrix — In der Mathematik beschreibt die Householdertransformation die Spiegelung eines Vektors an der Hyperebene durch Null in einem euklidischen Raum. Im dreidimensionalen Raum ist sie eine lineare Abbildung, die eine Spiegelung an einer Ebene (durch… …   Deutsch Wikipedia

  • Householder-Spiegelung — In der Mathematik beschreibt die Householdertransformation die Spiegelung eines Vektors an der Hyperebene durch Null in einem euklidischen Raum. Im dreidimensionalen Raum ist sie eine lineare Abbildung, die eine Spiegelung an einer Ebene (durch… …   Deutsch Wikipedia

  • Householder-Transformation — In der Mathematik beschreibt die Householdertransformation die Spiegelung eines Vektors an der Hyperebene durch Null in einem euklidischen Raum. Im dreidimensionalen Raum ist sie eine lineare Abbildung, die eine Spiegelung an einer Ebene (durch… …   Deutsch Wikipedia

  • Halley-Verfahren — Das Halley Verfahren (auch Verfahren der berührenden Hyperbeln) ist, ähnlich wie das Newton Verfahren, eine Methode der numerischen Mathematik zur Bestimmung von Nullstellen f(x)=0 reeller Funktionen . Im Gegensatz zum Newton Verfahren hat es die …   Deutsch Wikipedia

  • GMRES-Verfahren — Das GMRES Verfahren (für Generalized minimal residual method) ist ein iteratives numerisches Verfahren zur Lösung großer, dünnbesetzter linearer Gleichungssysteme. Das Verfahren ist aus der Klasse der Krylow Unterraum Verfahren und insbesondere… …   Deutsch Wikipedia

  • Hessenberg-Verfahren — Das Hessenberg Verfahren ist ein Verfahren der numerischen linearen Algebra zur Transformation einer quadratischen Matrix in Hessenberggestalt. Die Eigenwerte der entstehenden Hessenbergmatrix lassen sich anschließend einfach berechnen. Es ist… …   Deutsch Wikipedia

  • Gram-Schmidt-Verfahren — Das Gram Schmidtsche Orthogonalisierungsverfahren ist ein Algorithmus aus dem mathematischen Teilgebiet der linearen Algebra. Er erzeugt zu jedem System linear unabhängiger Vektoren aus einem Prähilbertraum, d. h. einem Vektorraum mit… …   Deutsch Wikipedia

  • Householdertransformation — In der Mathematik beschreibt die Householdertransformation die Spiegelung eines Vektors an einer Hyperebene durch Null im euklidischen Raum. Im dreidimensionalen Raum ist sie somit eine Spiegelung an einer Ebene (durch den Ursprung). Die… …   Deutsch Wikipedia

  • Householdermatrix — In der Mathematik beschreibt die Householdertransformation die Spiegelung eines Vektors an der Hyperebene durch Null in einem euklidischen Raum. Im dreidimensionalen Raum ist sie eine lineare Abbildung, die eine Spiegelung an einer Ebene (durch… …   Deutsch Wikipedia

  • QR-Algorithmus — Der QR Algorithmus ist ein numerisches Verfahren zur Berechnung aller Eigenwerte und eventuell der Eigenvektoren einer quadratischen Matrix. Das auch QR Verfahren oder QR Iteration genannte Verfahren basiert auf der QR Zerlegung und wurde im… …   Deutsch Wikipedia