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)=0f(x)=0 reeller Funktionen f:R→Rf:\R\to\R. Im Gegensatz zum Newton-Verfahren hat es die Konvergenzordnung 3, benötigt dazu aber zusätzlich zur ersten auch die zweite Ableitung. Es ist nach dem Astronomen Edmond Halley benannt, der auch den Halleyschen Kometen entdeckte. Ein vergleichbares Verfahren ist das Euler-Tschebyschow-Verfahren.
 
 

Beschreibung des Verfahrens

Sei ff eine reelle Funktion mit stetiger zweiter Ableitung, f∈C2(R,R)f\in C^2(\R,\R) und sei aa eine einfache Nullstelle von ff, d.h. f′(a)≠0f'(a)\ne 0. Dann wird der Funktionsverlauf von ff in der Nähe von aa gerade gebogen, indem statt ff die Funktion g(x)=f(x)∣f ′(x)∣ g(x)=\dfrac{f(x)}{\sqrt{|f\, '(x)|}} betrachtet wird. Diese Konstruktion ist von der Nullstelle unabhängig. Nun wird das Newton-Verfahren auf gg angewandt. Es ist
g′(x)=(f(x)⋅∣f′(x)∣−1/2)′ g'(x)=\left(f(x)\cdot |f'(x)|^{-1/2}\right)' =f′(x)⋅∣f′(x)∣−1/2+f(x)⋅(−12)∣f′(x)∣−3/2sgn⁡(f′(x)) f′′(x) = f'(x)\cdot |f'(x)|^{-1/2}+f(x)\cdot(-\dfrac12)|f'(x)|^{-3/2}\sgn(f'(x))\,f''(x)=2f′(x)2−f(x)f′′(x)2f′(x)∣f′(x)∣ =\dfrac{2f'(x)^2-f(x)f''(x)}{2f'(x)\sqrt{|f'(x)|}}
und daher Hf(x)=Ng(x)=x−g(x)g′(x)=x−2f(x)f′(x)2f′(x)2−f(x)f′′(x) H_f(x)=N_g(x)=x-\dfrac{g(x)}{g'(x)}=x-\dfrac{2f(x)f'(x)}{2f'(x)^2-f(x)f''(x)}
Daraus ergibt sich die Iteration des Halley-Verfahrens wie folgt: Es wird ein geeigneter Startwert x0x_0 gewählt, wobei sich dieselben Schwierigkeiten und Strategien wie beim Newton-Verfahren ergeben. Mit diesem wird die Folge (xk)k∈N(x_k)_{k\in\N} der sukzessiven Näherungen durch die Iterationsvorschrift
xk+1=Hf(xk)=xk−2f(xk)f′(xk)2f′(xk)2−f(xk)f′′(xk)x_{k+1}=H_f(x_k)=x_k-\dfrac{2f(x_k)f'(x_k)}{2f'(x_k)^2-f(x_k)f''(x_k)}
bestimmt.

Beispiel

Die Iteration für die Quadratwurzel von 5 ergibt mit f(x)=x2−5f(x)=x^2-5 die Iterationsvorschrift
Hf(x)=x x2+153x2+5H_f(x)=x\,\dfrac{x^2+15}{3x^2+5}
und damit die Berechnungstabelle
kk xkx_k f(xk)f(x_k)
0 3.00000000000000000000000000000000000000000000000000000000000 4.00000000000
1 2.25000000000000000000000000000000000000000000000000000000000 0.0625000000000
2 2.23606811145510835913312693498452012383900928792569659442724 5.99066414899E-7
3 2.23606797749978969640929385361588622700967141237081284965284 5.37483143712E-22
4 2.23606797749978969640917366873127623544061835961152572427090 0.000000000000
Es ergibt sich eine Folge von 0, 1, 5, 21, >60 gültigen Stellen, d.h. eine Verdreifachung in jedem Schritt. Das Newtonverfahren hat die Verfahrensvorschrift:
Gf(x)=x2+52xG_f(x)=\dfrac{x^2+5}{2x}
Im direkten Vergleich zeigt das Halley Verfahren die schnellere Konvergenz. Es benötigt jedoch mehr Rechenoperationen pro Schritt.

Kubische Konvergenz

Sei ff dreimal stetig differenzierbar. Da aa als Nullstelle von ff vorausgesetzt wurde, gilt näherungsweise f(x)=f(x)−f(a)≈f´(a)(x−a) f(x)=f(x)-f(a)\approx f´(a)(x-a). Genauer gilt auf einem Intervall II, welches aa enthält, nach dem Mittelwertsatz der Differentialrechnung die zweiseitige Abschätzung
∣f(x)∣max⁡z∈I∣f′(z)∣≤∣x−a∣≤∣f(x)∣min⁡z∈I∣f′(z)∣\dfrac{|f(x)|}{\max_{z\in I}|f'(z)|}\le |x-a|\le\dfrac{|f(x)|}{\min_{z\in I}|f'(z)|},
d.h. sowohl x−a=O(f(x))x-a=O(f(x)) als auch f(x)=O(x−a)f(x)=O(x-a). Es reicht also, das Verhältnis der Funktionswerte von einem Iterationsschritt zum nächsten zu bestimmen.
Die Taylorentwicklung zweiten Grades von ff ist
f(x+h)=f(x)+f′(x) h+12f′′(x) h2+O(h3)f\left(x+h\right)=f(x)+ f'(x)\,h+\dfrac12 f''(x)\,h^2 +O\left(h^3\right).
Dies ergibt zunächst eine Näherung durch eine Parabel, die ff im Punkt xx von zweiter Ordnung berührt. Ist f(x)f(x) klein genug, so hat diese Parabel eine Nullstelle, die deutlich nahe an xx liegt, nämlich bei
h=−2f(x)f′(x)+sign(f′(x))f′(x)2−2f(x)f′′(x)h=-\dfrac{2f(x)}{f'(x)+\text{sign}(f'(x))\sqrt{f'(x)^2-2f(x)f''(x)}}
Die entsprechende Iteration ist
xk+1=xk−2f(xk)f′(xk)+sign(f′(xk))f′(xk)2−2f(xk)f′′(xk)x_{k+1}=x_k-\dfrac{2f(x_k)}{f'(x_k)+\text{sign}(f'(x_k))\sqrt{f'(x_k)^2-2f(x_k)f''(x_k)}}.
Da der Nenner von hh in der Nähe einer Nullstelle von ff von Null verschieden ist, gilt h=O(f(x))h=O(f(x)). Durch diese Konstruktion von hh verschwinden die ersten drei Glieder der Taylor-Entwicklung, daher gilt f(xk+1)=O(h3)=O(f(xk)3)f(x_{k+1})=O(h^3)=O(f(x_k)^3).
Benutzt man in der Taylor-Entwicklung die Identität (a+bh)(a−bh)(a+bh)(a-bh)=a2−b2h2=a2+O(h2) =a^2-b^2h^2=a^2+O(h^2), so kann man diese in einen Bruch von in hh linearen Funktionen verwandeln:
f(x+h)=f(x)+(f′(x)+12f′′(x)h) h+O(h3)f\left(x+h\right)=f(x)+\left(f'(x)+\dfrac12 f''(x)h\right)\,h+O\left(h^3\right) =f(x)+f′(x)2hf′(x)−12f′′(x)h+O(h3)=f(x)+\dfrac{f'(x)^2h}{f'(x)-\dfrac12 f''(x)h}+O\left(h^3\right)=f(x)f′(x)+h(f′(x)2−12f(x)f′′(x))f′(x)−12f′′(x)h+O(h3)  =\dfrac{f(x)f'(x)+h(f'(x)^2-\dfrac12f(x)f''(x))}{f'(x)-\dfrac12 f''(x)h}+O\left(h^3\right)\
Die Funktion ff wird also durch eine Hyperbel approximiert, die ff in xx zu ebenfalls zweiter Ordnung berührt. Der Zähler der Hyperbelfunktion verschwindet für h=−2f(x)f′(x)2f′(x)2−f(x)f′′(x)h=-\dfrac{2f(x)f'(x)}{2f'(x)^2-f(x)f''(x)}, woraus sich die Halley-Iteration (s.o.) ergibt. Wieder gilt h=O(f(x))h=O(f(x)) und damit
f(Hf(x))=O(h3)=O(f(x)3) f(H_f(x))=O(h^3)=O(f(x)^3)\,
Daraus folgt dann für die Halley-Iteration
xk+1−a=Hf(xk)−a=O(f(Hf(xk)))x_{k+1}-a=H_f(x_k)-a=O(f(H_f(x_k)))=O(f(xk)3)=O((xk−a)3) =O(f(x_k)^3)=O((x_k-a)^3),
d.h. die kubische Konvergenz.

mehrdimensionale Erweiterung

Eine Erweiterung des Verfahrens auf Funktionen mehrerer Veränderlicher F:Rn→RnF: \mathbb{R}^n \to \mathbb{R}^n ist möglich. Es kann der gleiche binomische Trick zur Herstellung einer Hyperbelfunktion verwendet werden. Dabei ist aber zu beachten,
  1. dass F ′(x)F\, '(x) eine Matrix ist, die als invertierbar vorausgesetzt wird,
  2. dass F ′′(x)F\, ''(x) ein Tensor dritter Stufe ist, genauer eine vektorwertige symmetrische Bilinearform, und
  3. dass die unvollständig ausgewertete zweite Ableitung F ′′(x)(v,⋅)F\, ''(x)(v,\cdot), die ebenfalls eine Matrix ist, im Allgemeinen nicht mit der Matrix F ′(x)F\, '(x) kommutiert.
Dies sind keine Hindernisse, diese Eigenschaften machen nur die Rechnung etwas unübersichtlicher. Es bezeichne t=−F´(x)−1F(x)t=-F´(x)^{-1}F(x) den üblichen Newtonschritt, sei C(u,v)=12F′(x)−1F′′(x)(u,v)C(u,v)=\dfrac12 F'(x)^{-1}F''(x)(u,v) der entsprechend modifizierte Term zweiter Ordnung. Dann gilt für die Taylorentwicklung in xx
F(x+s)=F(x)+F′(x)s+12F′′(x)(s,s)+O(s3) F(x+s)=F(x)+F'(x)s+\dfrac12F''(x)(s,s)+O(s^3)=F′(x) (−t+s+C(s,s))+O(s3) =F'(x)\,\left(-t+s+C(s,s)\right)+O(s^3) d.h. F′(x)−1F(x+s)=(−t+(I+C(s,⋅)) s+O(s3))F'(x)^{-1}F(x+s)=\left(-t+\left(I+C(s,\cdot)\right)\,s+O(s^3)\right)=(−t+(I−C(s,⋅))−1 s+O(s3)) =\left(-t+\left(I-C(s,\cdot)\right)^{-1}\,s+O(s^3)\right)=(I−C(s,⋅))−1 (−t+C(s,t)+s+O(s3)) =\left(I-C(s,\cdot)\right)^{-1}\,\left(-t+C(s,t)+s+O(s^3)\right)
Der in ss lineare Teil des Zählers wird nun zu Null gesetzt und weiter umgeformt. Dabei wird die Symmetrie von C(⋅,⋅)C(\cdot ,\cdot ) ausgenutzt:
0=−t+C(s,t)+s=−t+(I+C(t,⋅)) s0=-t+C(s,t)+s=-t+\left(I+C(t,\cdot)\right)\,s\quad  ⟺  s=(I+C(t,⋅))−1 t \iff\quad s=\left(I+C(t,\cdot)\right)^{-1}\,t
Werden nun die Kurznotationen durch die ursprünglichen Ausdrücke ersetzt, so ergibt sich
s=−(I−12F′(x)−1F′′(x)(F′(x)−1F(x),⋅))−1  F′(x)−1F(x)s =-\left(I-\dfrac12F'(x)^{-1}F''(x)\left(F'(x)^{-1}F(x),\cdot\right)\right)^{-1}\;F'(x)^{-1}F(x)=−(F′(x)−12F′′(x)(F′(x)−1F(x),⋅))−1  F(x) =-\left(F'(x)-\dfrac12F''(x)\left(F'(x)^{-1}F(x),\cdot\right)\right)^{-1}\;F(x) .
Man überzeugt sich leicht, dass diese Formel sich im eindimensionalen Fall zur Halley-Iteration reduziert. Der sich daraus ergebende Iterationsschritt des mehrdimensionalen Halley-Verfahrens kann in 3 einfacheren Schritten bestimmt werden:
  1. Newton-Schritt: Löse F′(xk)tk=−F(xk)F'(x_k)t_k=-F(x_k)
  2. Korrektur des Newton-Schritts: Löse (F′(xk)+12F′′(xk)(tk,⋅))sk=−F(xk)\left(F'(x_k)+\dfrac{1}{2}F''(x_k)(t_k,\cdot) \right)s_k = -F(x_k)
  3. Setze xk+1=xk+skx_{k+1}=x_k+s_k
Ist die 2.Ableitung Lipschitz-stetig, so konvergiert das Verfahren lokal kubisch.
Da F(x)F(x) als klein vorausgesetzt wurde, ist es nicht wirklich notwendig, die Inverse der großen Klammer zu bestimmen. Es kann wieder der binomische Trick (bzw. die Taylorformel 1. Grades) benutzt werden, um den einfacheren, aber bis auf Terme dritter Ordnung (nun in F(x)F(x)) identischen Ausdruck
s=−(I+12F′(x)−1F′′(x)(F′(x)−1F(x),⋅))  F′(x)−1F(x)s=-\left(I+\dfrac12F'(x)^{-1}F''(x)\left(F'(x)^{-1}F(x),\cdot\right)\right)\;F'(x)^{-1}F(x)=−F′(x)−1F(x)−12F′(x)−1F′′(x)(F′(x)−1F(x),F′(x)−1F(x)) =-F'(x)^{-1}F(x)-\dfrac12F'(x)^{-1}F''(x)(F'(x)^{-1}F(x),F'(x)^{-1}F(x))
zu erhalten. Die daraus abgeleitete Iteration ist das Euler-Tschebyschow-Verfahren.

Literatur

  • T.R. Scavo and J.B. Thoo, On the geometry of Halley's method. American Mathematical Monthly, volume 102 (1995), number 5, pages 417-426.
  • Hubert Schwetlick: Numerische Lösung nichtlinearer Gleichungen Deutscher Verlag der Wissenschaften 1979

Scherzhafte Beispiele haben manchmal größere Bedeutung als ernste.

Michael Stifel

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Halley-Verfahren aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Numerische Verfahren