Halley-Verfahren

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 f:\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 das Wiederkehrgesetz des nach im benannten Halleyschen Kometen bestimmte. Ein vergleichbares Verfahren ist das Euler-Tschebyschow-Verfahren.

Inhaltsverzeichnis

Beschreibung des Verfahrens

Sei f eine reelle Funktion mit stetiger zweiter Ableitung, f\in C^2(\R,\R) und sei a eine einfache Nullstelle von f, d. h. f'(a)\ne 0. Dann konvergiert für Startpunkte x0 nahe a die durch die Iteration


  x_{k+1}=x_k-\frac{2\cdot f(x_k)f'(x_k)}{2f'(x_k)^2-f(x_k)f''(x_k)}
, k=0,1,2,...

erzeugte Folge sukzessiver Näherungen (x_k)_{k\in\N} mit kubischer Konvergenzordnung gegen a.

Varianten dieses Verfahrens sind das ursprünglich von Halley verwendete irrationale bzw. parabolische Halley-Verfahren mit der Iterationsvorschrift


  x_{k+1}=x_k-\frac{2f(x_k)}{f'(x_k)}\cdot
    \left(1+\sqrt{ 1-2\frac{f(x_k)f''(x_k)}{f'(x)^2} }\right)^{-1}
,

und in Verallgemeinerung dessen das Laguerre-Verfahren


  x_{k+1}=x_k-\frac{nf(x_k)}{f'(x_k)}\cdot
    \left(1+(n-1)\sqrt{ 1-\frac{n}{n-1}\frac{f(x_k)f''(x_k)}{f'(x)^2} }\right)^{-1}
.

Für Polynome wird dabei n gleich dem Grad gesetzt. Da der Term unter der Wurzel negativ werden kann, können diese beiden Varianten auch für rein reelle Polynome und reelle Startwerte zu komplexen Nullstellen konvergieren. Bei der in nachfolgenden Iterationen notwendigen Bestimmung der Quadratwurzel aus komplexen Zahlen ist hier immer die Lösung mit positivem Realteil zu wählen, so dass der Nenner den größtmöglichen Betrag hat.

Motivation

Sei f eine reelle Funktion mit stetiger zweiter Ableitung, f\in C^2(\R,\R) und sei a eine einfache Nullstelle von f, d. h. f'(a)\ne 0. Dann wird der Funktionsverlauf von f in der Nähe von a in zweiter Ordnung „gerade gebogen“, indem statt f die Funktion  g(x)=\tfrac{f(x)}{\sqrt{|f'(x)|}} betrachtet wird. Diese Konstruktion ist von der Nullstelle unabhängig. Nun wird das Newton-Verfahren auf g angewandt. Es ist


\begin{align}
g'(x)&=\bigl(f(x)\cdot |f'(x)|^{-1/2}\bigr)'\\[0.5em]
&= f'(x)\cdot |f'(x)|^{-1/2}+f(x)\cdot(-\tfrac12)|f'(x)|^{-3/2}\text{sign}(f'(x))\,f''(x)\\[1em]
&=\frac{2f'(x)^2-f(x)f''(x)}{2f'(x)\sqrt{|f'(x)|}}
\end{align}

und daher


H_f(x)=N_g(x)=x-\frac{g(x)}{g'(x)}=x-\frac{2f(x)f'(x)}{2f'(x)^2-f(x)f''(x)}

Dieselbe Vorschrift ergibt sich aus dem allgemeineren Householder-Verfahren in der zweiten Ordnung


H_f(x)=x+2\frac{(1/f)'(x)}{(1/f)''(x)}

Beispiel

Die Iteration für die Quadratwurzel von z.B. a=5 ergibt mit f(x) = x2a die Iterationsvorschrift

H_f(x)=x\,\frac{x^2+3a}{3x^2+a}=x\,\frac{x^2+15}{3x^2+5}

und damit die Berechnungstabelle

k xk f(xk)
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:

G_f(x)=\frac{x^2+a}{2x}=\frac{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 f dreimal stetig differenzierbar. Da a als Nullstelle von f vorausgesetzt wurde, gilt näherungsweise  f(x)=f(x)-f(a)\approx f'(a)(x-a). Genauer gilt auf einem Intervall I, welches a enthält, nach dem Mittelwertsatz der Differentialrechnung die zweiseitige Abschätzung

\tfrac{|f(x)|}{\max_{z\in I}|f'(z)|}\le |x-a|\le\tfrac{|f(x)|}{\min_{z\in I}|f'(z)|},

d. h. sowohl xa = O(f(x)) als auch f(x) = O(xa). Es reicht also, das Verhältnis der Funktionswerte von einem Iterationsschritt zum nächsten zu bestimmen.

Irrationales oder parabolisches Halley-Verfahren

Die Taylorentwicklung zweiten Grades von f ist

f\bigl(x+h\bigr)=f(x)+ f'(x)\,h+\tfrac12 f''(x)\,h^2 +O\bigl(h^3\bigr).

Dies ergibt zunächst eine Näherung durch eine Parabel, die den Graphen von f im Punkt x von zweiter Ordnung berührt. Ist f(x) klein genug, so hat diese Parabel eine Nullstelle, die deutlich nahe an x liegt, nämlich bei

\begin{align}
h&=-\frac{2f(x)}{f'(x)+\text{sign}(f'(x))\sqrt{f'(x)^2-2f(x)f''(x)}}\\[0.5em]
 &=-\frac{2f(x)}{f'(x)\,\left(1+\sqrt{1-2f(x)f'(x)^{-2}f''(x)}\right)}
\end{align}

Die entsprechende Iteration ist

x_{k+1}=x_k-\frac{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 h in der Nähe einer Nullstelle von f von Null verschieden ist, gilt h = O(f(x)). Durch diese Konstruktion von h verschwinden die ersten drei Glieder der Taylor-Entwicklung, daher gilt f(xk + 1) = O(h3) = O(f(xk)3).

Diese Form des Verfahrens wurde ursprünglich von E. Halley vorgeschlagen. Entwickelt man die Wurzel nach \sqrt{1+y}=1+\tfrac12y+O(y^2), so erhält man das, heute übliche, rationale oder hyperbolische Halley-Verfahren.

Hyperbolisches Halley-Verfahren

Benutzt man in der Taylor-Entwicklung von f(x + h) die Identität (a + bh)(abh) = a2b2h2 = a2 + O(h2), so kann man diese in einen Bruch von in h linearen Funktionen verwandeln, d.h. f wird in der Nähe von x durch eine hyperbolische Funktion angenähert, und von dieser nachfolgend die Nullstelle bestimmt:


\begin{array}{rl}
f\bigl(x+h\bigr)=&f(x)+\bigl(f'(x)+\tfrac12 f''(x)h\bigr)\,h+O\bigl(h^3\bigr)\\\\
=&f(x)+\frac{f'(x)^2h}{f'(x)-\frac12 f''(x)h}+O\bigl(h^3\bigr)\\\\
=&\frac{f(x)f'(x)+h(f'(x)^2-\frac12f(x)f''(x))}{f'(x)-\frac12 f''(x)h}+O\bigl(h^3\bigr)\ .\\
\end{array}

Die Funktion f wird also durch eine Hyperbel approximiert, die f in x zu ebenfalls zweiter Ordnung berührt. Der Zähler der Hyperbelfunktion verschwindet für h=-\tfrac{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)) und damit

f(H_f(x))=O(h^3)=O(f(x)^3)\,

Daraus folgt dann für die Halley-Iteration


  x_{k+1}-a
    =H_f(x_k)-a=O(f(H_f(x_k)))
    =O\left(f(x_k)^3\right)
    =O\left((x_k-a)^3\right)\ ,

d. h. die kubische Konvergenz.

mehrdimensionale Erweiterung

Eine Erweiterung des Verfahrens auf Funktionen mehrerer Veränderlicher F: \R^n \to \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) eine Matrix ist, die als invertierbar vorausgesetzt wird,
  2. dass F''(x) ein Tensor dritter Stufe ist, genauer eine vektorwertige symmetrische Bilinearform, und
  3. dass die unvollständig ausgewertete zweite Ableitung F''(x)(v,\cdot), die ebenfalls eine Matrix ist, im Allgemeinen nicht mit der Matrix F'(x) kommutiert.

Dies sind keine Hindernisse, diese Eigenschaften machen nur die Rechnung etwas unübersichtlicher. Es bezeichne s = − F'(x) − 1F(x) den üblichen Newtonschritt, sei C(u,v)=\tfrac12 F'(x)^{-1}F''(x)(u,v) der entsprechend modifizierte Term zweiter Ordnung. Dann gilt für die Taylorentwicklung in x

\begin{align}
   F(x+t)
 &=F(x)+F'(x)t+\tfrac12F''(x)(t,t)+O(t^3)\\[0.5em]
 &=F'(x)\,\Bigl(-s+t+C(t,t)\Bigr)+O(t^3)\quad\text{d.h.}\\[0.5em]
   F'(x)^{-1}F(x+t)
 &=\Bigl(-s+\bigl(I+C(t,\cdot)\bigr)\,t+O(t^3)\Bigr)\\[0.5em]
 &=\Bigl(-s+\bigl(I-C(t,\cdot)\bigr)^{-1}\,t+O(t^3)\Bigr)\\[0.5em]
 &=\bigl(I-C(t,\cdot)\bigr)^{-1}\,\bigl(-s+C(t,s)+t+O(t^3)\bigr)
\end{align}

Der in t lineare Teil des Zählers wird nun zu Null gesetzt und weiter umgeformt. Dabei wird die Symmetrie von C(.,.) ausgenutzt:

0=-s+C(t,s)+s=-s+\bigl(I+C(s,\cdot)\bigr)\,t\quad\iff\quad t=\bigl(I+C(s,\cdot)\bigr)^{-1}\,s

Werden nun die Kurznotationen durch die ursprünglichen Ausdrücke ersetzt, so ergibt sich

\textstyle\begin{align}
  t
&=-\Bigl(I-\tfrac12F'(x)^{-1}F''(x)\bigl(F'(x)^{-1}F(x),\cdot\bigr)\Bigr)^{-1}\;F'(x)^{-1}F(x)\\[0.5em]
&=-\Bigl(F'(x)-\tfrac12F''(x)\bigl(F'(x)^{-1}F(x),\cdot\bigr)\Bigr)^{-1}\;F(x)
\end{align}.

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)sk = − F(xk)
  2. Korrektur des Newton-Schritts: Löse \left(F'(x_k)+\tfrac{1}{2}F''(x_k)(s_k,\cdot) \right)t_k = -F(x_k)
  3. Setze xk + 1 = xk + tk

Ist die 2.Ableitung Lipschitz-stetig, so konvergiert das Verfahren lokal kubisch.

Da F(x) als klein vorausgesetzt wurde, ist es nicht mehr 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)) identischen Ausdruck

\begin{align}
t=&-\Bigl(I+\tfrac12F'(x)^{-1}F''(x)\bigl(F'(x)^{-1}F(x),\cdot\bigr)\Bigr)\;F'(x)^{-1}F(x)\\[0.5em]
=&-F'(x)^{-1}F(x)-\tfrac12F'(x)^{-1}F''(x)\bigl(F'(x)^{-1}F(x),F'(x)^{-1}F(x)\bigr)
\end{align}

zu erhalten. Die daraus abgeleitete Iteration ist das Euler-Tschebyschow-Verfahren.

Weblinks

Quellen

  • T.R. Scavo and J.B. Thoo: On the geometry of Halley’s method. In:American Mathematical Monthly. Volume 102 (1995), number 5, S. 417–426.
  • Dieser Artikel wurde dem Artikel en:Halley's method der englischen Wikipedia nachempfunden (Stand 26. Januar 2007).
  • Hubert Schwetlick: Numerische Lösung nichtlinearer Gleichungen. Deutscher Verlag der Wissenschaften, 1979.

Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

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

  • Halley — bezeichnet: Halley (Arkansas), ein Ort in den USA Halley Station, eine britische Forschungsstation in der Antarktis Halley (Mondkrater), ein Einschlagkrater auf dem Mond (2688) Halley, ein Asteroid des Hauptgürtels Halleyscher Komet, ein… …   Deutsch Wikipedia

  • Numerische Verfahren — Die Liste numerischer Verfahren führt Verfahren der numerischen Mathematik nach Anwendungsgebieten auf. Inhaltsverzeichnis 1 Lineare Gleichungssysteme 2 Nichtlineare Gleichungssysteme 3 Numerische Integration 4 Approximation und Interpolation …   Deutsch Wikipedia

  • Edmond Halley — Edmund Halley um etwa 1687 auf einem Gemälde von Thomas Murray (1663–1735) Edmond Halley (* 29. Oktoberjul./ 8. November 1656greg. in Haggerston bei London; † 14. Januar 1741jul./ …   Deutsch Wikipedia

  • Euler-Tschebyschow-Verfahren — Das Euler Tschebyschow Verfahren (nach Leonhard Euler und Pafnuti Lwowitsch Tschebyschow; auch Verfahren der berührenden Parabeln) bezeichnet in der Numerischen Mathematik ein iteratives Verfahren zum Lösen nichtlinearer Gleichungen. Es ist… …   Deutsch Wikipedia

  • Liste numerischer Verfahren — Die Liste numerischer Verfahren führt Verfahren der numerischen Mathematik nach Anwendungsgebieten auf. Inhaltsverzeichnis 1 Lineare Gleichungssysteme 2 Nichtlineare Gleichungssysteme 3 Numerische Integration …   Deutsch Wikipedia

  • 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 1 Beschreibung des Verfahrens 2 Motivation 3… …   Deutsch Wikipedia

  • Robert Hooke — Robert Hooke: Kurator für Experimente an der Royal Society, Geometrieprofessor des Gresham College und Landvermesser der Stadt London; Uhrenbauer, Astronom, Mikroskopierer, Geologe, Physiologe, Architekt, Naturphilosoph und Englands Leonardo …   Deutsch Wikipedia

  • Längengradproblem — Der Ausdruck Längenproblem bezeichnet die problematische Bestimmung der geographischen Länge bei der Positionsermittlung sowohl in der Kartographie als auch im Besonderen von Schiffen auf dem offenen Meer. Während die geographische Breite relativ …   Deutsch Wikipedia

  • Liste der Erfinder — Dies ist eine Liste von Erfindern, die die Welt mit ihren Erfindungen bereichert haben. Ein Erfinder ist jemand, der ein Problem erkannt hat, es gelöst und mindestens einmal damit Erfolg gehabt hat. Er muss nicht der erste gewesen sein; eine… …   Deutsch Wikipedia

  • Newton, Sir Isaac — Isaac Newton (Godfrey Kneller, National Portrait Gallery London, 1702) Sir Isaac Newton [ˌaɪzək ˈnjuːtən] (* 25. Dezember 1642jul./ …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”