Halley-Verfahren

Das Halley-Verfahren - benannt nach dem Astronomen Edmond Halley, der auch den Halleyschen Kometen entdeckte - ist ein numerisches Verfahren zur näherungsweisen Berechnung der Nullstelle einer reellen stetigen Funktion f (x), d.h. der Lösung der reellen Gleichung f (x) =0.

Für eine zweifach stetig differenzierbare Funktion f lautet die Iterationsvorschrift

 

 

Außer der ersten Ableitung f ' wie beim Newton-Verfahren wird hier auch die zweite Ableitung f '' benötigt.

 

Die Iterationsvorschrift lässt sich zum einen herleiten durch eine Taylor-Reihenentwicklung [1].

Alternativ dazu ergibt sie sich, indem man die Funktion f in der Nähe der Nullstelle "gerade biegt" mit Hilfe von

 

f* (s. orangener Graph in Animation) hat die gleichen Nullstellen wie die zu untersuchende Funktion f.

Wendet man nun auf f* das Newton-Verfahren an, so ergibt sich

 

woraus die obige Iterationsvorschrift für das Halley-Verfahren folgt.

Eine weitere - und "direkter einsehbare" - Herleitung ist die Idee, die Funktion f an der Nullstelle nicht durch eine Sekante wie beim Sekantenverfahren oder durch eine Tangente wie beim Newton-Verfahren zu approximieren, sondern durch eine Hyperbel, z.B. der Form

 

Da eine Hyperbel eine Kurve zweiter Ordnung ist, müssen zu ihrer Bestimmung die folgenden Gleichungen an der Stelle xi gelten:

 

mit den Lösungen

was dann zur Iterationsvorschrift des Halley-Verfahrens führt [1].

 

Um für den i-ten Iterationsschritt die Hyperbel hi (x) grafisch darstellen zu können (s. blauer Graph in obiger Animation), werden a, b und c in die obige Hyperbelgleichung eingesetzt; es ergibt sich somit die folgende Funktionsgleichung:

 

 

Konvergenzbetrachtungen

Das Halley-Verfahren besitzt eine kubische Konvergenzordnung (einen Beweis findet man bei [2]).

 

Die folgende Bildsequenz zeigt den Einzugsbereich mit den jeweils erforderlichen Iterationsschritten für eine Genauigkeit von 10-15 für die Funktionen x2-1, x3-1 und x4-1 mit ihren einfachen Nullstellen.

Wie auch beim Sekanten- und Newton-Verfahren erhöht sich die Anzahl der Iterationsschritte zum Erreichen der geforderten Genauigkeit deutlich, falls man den Startwert in die Nähe eines Extremwertes der Funktion legt oder es sich bei der gesuchten Nullstelle um eine mehrfache Nullstelle handelt.

 

Als Beispiel dafür zeigt die folgende linke Grafik den Einzugsbereich mit den jeweils erforderlichen Iterationsschritten für eine Genauigkeit von 10-15 für eine Funktion mit einfacher bei -1, doppelter bei 0 und dreifacher Nullstelle bei 1 sowie das gleiche für die Funktion f(x) =  x4 mit vierfacher Nullstelle (rechte Grafik).

Ebenfalls verschlechert sich das Konvergenzverhalten, falls die Funktion Extremwerte oder Terassen-punkte besitzt und sich der Startwert der Iteration nahe bei diesen befindet. DiIe folgende Sequenz zeigt dies für die Funktion f (x) = x5 - 10 x + 50 für unterschiedliche Maximalwerte imax der Iterationsschritte bei einer geforderten Genauigkeit von 10-15.

Wendet man das Halley-Verfahren auf das Polynom f (x) = x5 - 3x4 - 5x3 + 15x2 + 4x - 12 oder auf die Funktion f (x) = sin (x) an, so stellt man fest, dass es im Gegensatz zum Sekanten- oder Newton-Verfahren im Bereich zwischen je zwei aufeinanderfolgenden Nullstellen ξk und ξk+1 zu keinen Sprüngen bei der berechneten Nullstelle kommt - das Verfahren liefert "stabil" die Nullstelle im Einzugsbereich nahe der jeweiligen Nullstelle:

Das ist jedoch nicht immer der Fall:

  • Bei der Funktion f (x) = x4 - x2 - 1 treten Sprünge der berechneten Nullstelle im Bereich innerhalb der beiden Nullstellen der Funktion auf (s. folgende linke Grafik).
  • Bei der Funktion  x6 + 7 x3 +x + 1 kommt es zu Sprüngen der berechneten Nullstelle außerhalb der beiden Nullstellen (s. folgende rechte Grafik).

Insbesondere für Polynome lässt sich das Folgende feststellen, wobei in den Grafiken für die Funktion f folgende Punkte farblich markiert:

Nullstelle       Extrempunkt       Wendepunkt       Terrassenpunkt   

Bei einem Funktion mit mindestens zwei aufeinanderfolgenden Nullstellen ξ1 und ξ2 mit ξ1 < ξ2 treten keine mehrfachen Sprünge der berechneten Nullstelle im Intervall [ξ1 , ξ2] auf, wenn in diesem Intervall das Polynom genau einen Extrempunkt besitzt. Folglich weist das Verfahren bei allen quadratischen Funktionen (Parabeln), bei Funktionen des Typs f (x) = a x2n - b, n |N mit zwei Nullstellen sowie bei reinen Sinus- und Cosinus-Funktionen keine Sprünge auf (vgl. oben für  x2 x4 sowie sin(x) ).

 

Insbesondere bei Polynomen mit mindestens zwei aufeinanderfolgenden Nullstellen ξ1 und ξ2 mit ξ1 < ξ2 treten mehrfache Sprünge der berechneten Nullstelle innerhalb des Intervalls [ξ1 , ξ2] auf, wenn in diesem Intervall die Funktion

  • mindestens zwei Extrempunkte oder
  • mindestens einen Extrempunkt und mindestens einen Terrassenpunkt besitzt.

Bei einem Polynom mit n 2 Nullstellen ξ1, ... ,ξn mit ξ1 < ξ2 < ... < ξn treten mehrfache Sprünge der berechneten Nullstelle ausserhalb der Intervalle [ξ1 , ξ2] und [ξn-1 , ξn] auf, wenn die Funktion dort  Extrempunkte oder Terrassenpunkte besitzt:



Download

 

 Halley Method.gc3