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 {\displaystyle f\colon I\subset \mathbb {R} \to \mathbb {R} } eine mindestens (d+1)-fach stetig differenzierbare Funktion, die im Intervall I eine einfache Nullstelle a besitze, d.h. f'(a)\neq 0. Sei x_{0} ein Startwert nahe genug an 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 (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|\leq 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)\neq 0 und f(x)=g(x)(x-a). Die reziproke Funktion {\displaystyle {\frac {1}{f}}} hat einen Pol der Ordnung 1 in a. Liegt x nahe a, so wird die Taylorentwicklung von {\displaystyle {\frac {1}{f}}} in 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 x-a, also

{\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 x^{3}-2x-5=0. In einem ersten Schritt wurde beobachtet, dass es eine Nullstelle nahe x=2 geben muss. Durch Einsetzen von {\displaystyle 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

{\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 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.

Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung: Jena, den: 09.04. 2020