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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} eine natürliche Zahl und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f \colon I\subset\R\to\R} eine mindestens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (d+1)} -fach stetig differenzierbare Funktion, die im Intervall $I$ eine einfache Nullstelle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} besitze, d. h. $f'(a)\neq 0$. Sei $x_{0}$ 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})}}\quad {\text{mit }}k=0,1,2,\dots$

erzeugte Folge $(x_{k})_{k\in \mathbb {N} }$ sukzessiver Approximationen mit Konvergenzordnung Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d=1} ergibt sich das Newton-Verfahren, für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d=2} das Halley-Verfahren.

Motivation

Hat $f$ eine einfache Nullstelle in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} , so gibt es eine Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} -fach stetig differenzierbare Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g(a)=f'(a)\ne 0} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(x)=g(x)(x-a)} . Die reziproke Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac{1}{f}} hat einen Pol der Ordnung $1$ in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} . Liegt $x$ nahe $a$, so wird die Taylorentwicklung von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac{1}{f}} in $x$ von diesem Pol dominiert,

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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}}

Betrachtet man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g(x+h)} als sich langsam ändernd bis nahezu konstant zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f^\prime(a)} , dann sind die Taylorkoeffizienten umgekehrt proportional zu den Potenzen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x-a} , also

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k = 1, \ldots , d.}

Beispiel

Die von Newton zur Demonstration seines Verfahrens benutzte Polynomgleichung war Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle x^{3}-2x-5=0} . In einem ersten Schritt wurde beobachtet, dass es eine Nullstelle nahe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x=2} geben muss. Durch Einsetzen von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x=2+h} erhält man erst

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(2+h)=-1 + 10 h + 6 h^2 + h^3}

und anschließend durch Invertieren dieses Polynoms als Taylorreihe

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \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}}

Das Ergebnis des ersten Schritts des Householder-Verfahrens einer gegebenen Ordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d} erhält man auch, indem man den Koeffizienten des Grades Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 $d$ gültige Dezimalstellen für den ersten Schritt im Verfahren der Ordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.)