imported>RaschenTechner: /* growthexperiments-addlink-summary-summary:2|0|0 */

2024-08-28T09:21:30Z

growthexperiments-addlink-summary-summary:2|0|0

Neue Seite

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
{| class="wikitable"
|-
!d
!x<sub>1</sub>=2+
|-
|1
| '''0,1'''00000000000000000000000000000000
|-
|2
| '''0,094'''339622641509433962264150943396
|-
|3
| '''0,09455'''8429973238180196253345227476
|-
|4
| '''0,094551'''282051282051282051282051282
|-
|5
| '''0,09455148'''6538216154140615031261963
|-
|6
| '''0,094551481'''438752142436492263099119
|-
|7
| '''0,09455148154'''3746895938379484125813
|-
|8
| '''0,0945514815423'''36756233561913325371
|-
|9
| '''0,09455148154232'''4837086869382419375
|-
|10
| '''0,094551481542326'''678478801765822985
|}
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 City|New York]], 1970. ISBN 0-07-030465-3
* ''[http://numbers.computation.free.fr/Constants/Algorithms/newton.html Newton's method and high order iterations]'', Pascal Sebah and Xavier Gourdon, 2001 (Auf der Seite ist eine Postscript-Version mit korrekter Formeldarstellung verlinkt.)

[[Kategorie:Numerische Mathematik]]

Householder-Verfahren - Versionsgeschichte

imported>RaschenTechner: /* growthexperiments-addlink-summary-summary:2|0|0 */