Ein-Schritt-Verfahren (one-step methods)

Die Anwendung der im folgenden betrachteten Verfahren für eine Vielzahl komplexer Funktionen finden Sie unter Basins of Attraction.


•  Newton-Verfahren für komplexe Funktionen

Das Newton-Verfahren für komplexe Funktionen f : D   mit  D ⊆ ℂ beruht auf der Iterationsvorschrift

Für die Herleitung, weitere Details, Konvergenzordnung q, Effizienzindex CE siehe unter Newton-Verfahren für reelle Funktionen.

•  Modifiziertes Newton-Verfahren

Im Falle einer mehrfachen Nullstelle konvergiert das Newton-Verfahren nur noch linear. Besitzt die Funktion eine a-fache Nullstelle (a |N, a ≥ 2), so liefert das modifizierte Verfahren

aber wieder lokal quadratische Konvergenz. Sehr schön kann man das am folgendem Beispiel erkennen.

 

Die Funktion f (z) = (z² - 1) ² = 0 besitzt die beiden doppelten Nullstellen ζ1,2 = -1 ζ3,4 = 1. Sowohl das Newton- als auch das modifizierte Newton-Verfahren (a = 2) liefern für B = [-4, 4] × [-4, 4] ⊆ ℂ die gleichen Basins of Attraction (s. erstes Bild in folgender Galerie). Stellt man jedoch die Konvergenzgeschwindigkeit für diesen Bereich B mit Hilfe einer Regenbogen-Farbpalette dar (s. dazu Basins of Attraction - Algorithmen), so zeigt sich an Hand der vorherrschenden Blautöne, dass das Verfahren mit a = 1 deutlich langsamer konvergiert (s. mittleres Bild in Galerie) als das Vefahren mit a = 2 und vorherrschenden Rot-/Gelb-Tönen (s. letztes Bild in Galerie).



•  Halley-Verfahren für komplexe Funktionen

Die Iterationsvorschrift für das Halley-Verfahren für komplexe Funktionen f : D   mit  D ⊆ ℂ lautet

Für die Herleitung, weitere Details, Konvergenzordnung q, Effizienzindex CE siehe unter Halley-Verfahren für reelle Funktionen.



•  Schröder-Verfahren für komplexe Funktionen

Das Schröder-Verfahren für komplexe Funktionen f : D   mit  D ⊆ ℂ beruht auf der Iterationsvorschrift

 

Für die Herleitung, weitere Details, Konvergenzordnung q, Effizienzindex CE siehe unter Schröder-Verfahren für reelle Funktionen.



•  Householder-Verfahren für komplexe Funktionen

Das hier betrachtete Householder-Verfahren [1], [2] für komplexe Funktionen f : D   mit  D ⊆ ℂ beruht auf der Iterationsvorschrift

Es hat die Konvergenzordnung q = 3 und den Effizienzindex CE = 1.442.

 

Quellenverweise

 

[1]   https://mathworld.wolfram.com/HouseholdersMethod.html

[2]   https://de.wikipedia.org/wiki/Householder-Verfahren



•  Basto-Verfahren für komplexe Funktionen

Die Iterationsvorschrift für das Basto-Verfahren für komplexe Funktionen f : D   mit  D ⊆ ℂ lautet [1]:

Das Verfahren besitzt die Konvergenzordnung q = 3 bei einem Effizienzindex CE = 1.442.

 

Quellenverweise

 

[1]     M. Basto et al., A new iterative method to compute nonlinear equations (2006),
         Applied Mathematics and Computation 173 (2006), (468–483)



•  Whittaker- Verfahren (I) für komplexe Funktionen

Das von Whittaker entwickelte Verfahren mit konvexer Beschleunigung (engl. convex acceleration) beruht auf dem Newton-Verfahren und besitzt die Konvergenzordnung q = 2 und den Effizienzindex CE = 1.26.

Angewandt auf komplexe Funktionen f : D   mit  D ⊆ ℂ lautet die Iterationsvorschrift:

 

Quellenverweise

 

[1]   J. M. Ortega, W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables (1970),
       Monographs Textbooks Comput. Sci. Appl. Math., Academic Press, New York, 1970, S.181 ff



•  Whittaker-Verfahren (II) für komplexe Funktionen

Whittaker entwickelte sein Verfahren mit konvexer Beschleunigung  (s. Whittaker I - Verfahren) weiter zu einem Verfahren mit doppelt konvexer Beschleunigung (engl. double convex acceleration) [1]. Das neue Verfahren hat die höhere Konvergenzordnung q = 3 bei einem Effizienzindex CE = 1.442. Die neue Iterationsvorschrift, angewandt auf komplexe Funktionen f : D   mit  D ⊆ ℂ, lautet:

 

Quellenverweise

 

[1]   M. Heydari, G.B. Loghmani (2014) Third-Order and Fourth-Order Iterative Methods Free from Second
       Derivative for Finding Multiple Roots of Nonlinear Equations
, CJMS 3(1)(2014), (67-85)

 

[2]   B. Neta, C. Chun, (2013) On a family of Laguerre methods to find multiple roots of nonlinear equations,
       Applied Mathematics and Computation 219 (2013) 10987–11004

http://dx.doi.org/10.1016/j.amc.2013.05.002



•  Euler-Chebyshev-Verfahren für komplexe Funktionen

Das Euler-Chebyshev-Verfahren beruht auf der Iterationsvorschrift

und ist insbesondere für mehrfache Nullstellen, d.h. Nullstellen der Vielfachheit m geeignet, lässt sich aber auch für einfache Nullstellen einsetzen. Es handelt sich um ein Verfahren der Konvergenzordnung q = 3 bei einem Effizienzindex von CE = 1.442.

 

Quellenverweise

 

[1]   M. A. Hernandez, An acceleration procedure of the Whittaker method by means of convexity (1990),
       Zb. Rad. Prirod.-Mat. Fak. Ser. Mat. 20 (1990), 27–38



•  Chun-Kim I -Verfahren für komplexe Funktionen

Die Verfasser konstruieren in [1] ein neues Verfahren basierend auf einer geometrischen Herangehensweise, ähnlich wie der mit der Tangente beim Newton-Verfahren und einer Hyperbel beim Halley-Verfahren (s. die dortigen Animationen). Hierbei nehmen sie aber den Krümmungskreis zur Hilfe, der im Punkt (xn | yn) die gleiche Tangente wie die Funktion f  besitzt. SIe leiten die folgende  Iterationsvorschrift für komplexe Funktionen f : D   mit  D ⊆ ℂ her:

Das Verfahren besitzt die Konvergenzordnung q = 3, der Effizienzindex beträgt CE = 1.442.

 

Quellenverweise

 

[1]   C. Chun · Y. I. Kim, Several New Third-Order Iterative Methods for Solving Nonlinear Equations (2010),
       Acta Appl. Math. (2010) 109: 1053–1063, DOI 10.1007/s10440-008-9359-3



•  Laguerre-Verfahren für komplexe Funktionen

M. Laguerre: Über eine Methode, um per Approximation die Lösungen einer algebraischen Gleichung zu finden, die nur relle Lösungen hat

Das Verfahren von Laguerre ist ein hauptsächlich auf Polynome zugeschnittenes einstufiges Verfahren. In seiner Publikation "Über eine Methode, um per Approximation die Lösungen einer algebraischen Gleichung zu finden, die nur relle Lösungen hat" von 1880 (!) schreibt Laguerre dazu [1]:

 

     "Ausgehend von einem Näherungswert für die Lösung einer Gleichung bieten das Newton'sche Approximationsverfahren und das Proportionalteilungsverfahren bequeme Wege für eine schnelle Annäherung an diese Lösung. Die Hauptschwierigkeit besteht darin, diesen ersten ungefähren Wert zu erhalten, der als Ausgangspunkt genommen werden muss.

     Ich glaube - in Anbetracht der Frage in ihrer ganzen Allgemeinheit - ist dem, was wir bereits wissen, nicht viel hinzuzufügen; es scheint mir, dass das Problem anders gestellt werden muss, und zwar wie folgt:

     Finde für eine gegebene Gleichung […] eine Methode, die am sichersten und schnellsten zu Näherungswerten ihrer Lösungen führt. Der Zweck der folgenden Abhandlung besteht darin, eine Lösung dieses Problems für den Fall bereitzustellen, dass die vorgeschlagene Gleichung algebraisch ist und alle Lösungen reell sind. Wie wir wissen, kommen Gleichungen dieser Art sehr häufig in einer Vielzahl von Fragen zu wichtigen Aspekten der Analyse vor."  

 

Für ein komplexes Polynom p (z) vom Grad n ≥ 2 lautet die Iterationsvorschrift des Laguerre-Verfahrens:

mit

   

wobei das Vorzeichen der Wurzel so gewählt wird, dass der absolute Betrag der Nenner maximal ist.

 

Quellenverweise

 

[1]   M. Laguerre, Sur une méthode pour obtenir par approximation les racines d’une équation

       algébrique qui a toutes ses racines réelles, Nouvelles annales de mathématiques 2e série, tome 19

       (1880), S. 161-171

       http://www.numdam.org/item?id=NAM_1880_2_19__161_1

 



•  Sekantenverfahren für komplexe Funktionen

Das Sekantenverfahren für komplexe Funktionen f : D   mit  D ⊆ ℂ beruht auf der Iterationsvorschrift

Das Verfahren benötigt außer dem Startwert z0 ϵ B noch einen zweiten Startwert z1 ϵ B, der bei der Berechnung der Einzugsbereiche für verschiedene komplexe Funktionen (Basins of Attraction) in der Regel zu z1 = (0, 0) gesetzt wurde.

 

Für weitere Details, Herleitung, Konvergenzordnung q und Effizienzindex CE siehe Sekantenverfahren für reelle Funktionen. Die Anwendung des Verfahrens für einige komplexe Funktionen finden Sie unter Basins of Attraction.



•  Steffensen-Verfahren für komplexe Funktionen

Die Iterationsvorschrift für das Steffensen-Verfahren für komplexe Funktionen f : D   mit  D ⊆ ℂ ergibt sich, wenn man beim Newton-Verfahren die Ableitung durch den (rechtsseitigen) Differenzenquotienten ersetzt:

Für weitere Details, Konvergenzordnung q, Effizienzindex CE siehe unter Steffensen-Verfahren bei Diverse Verfahren für reelle Funktionen.

 

Eine Variante des Steffensen-Verfahrens hat einen zusätzlichen Parameter β und besitzt die folgende Iterationsvorschrift [1]:

Es ist bekannt, dass dieses Verfahren für jeden von Null verschiedenen Wert des Parameters β eine quadratische Konvergenz hat, jedoch spielt der Parameter β eine wichtige Rolle in Bezug auf die Stabilität der Methode.

 

Zum einen können bei dieser Variante des Steffensen-Verfahrens die Basins of Attraction durch Wahl eines kleinen Wertes für β stark verbessert werden. Die folgenden Grafiken zeigen dies am Beispiel für z³ - 1 = 0 mit einem Bereich B = [-10, 10] x [-10, 10] und unterschiedlichen Werten für β.

  

Basins of Attraction,  β = 1

Basins of Attraction,  β = 0.1

Basins of Attraction,  β = 0.01


Zum anderen lässt sich zeigen (s. [1], S. 5) und eyperimentell beobachten, dass für sehr kleine Werte für β die berechneten Basins of Attraction ähnlich denen des Newton-Verfahrens werden wie in der folgenden Galerie am Beispiel für z³ - 1 = 0 und einem Bereich B = [-2, 2] x [-2, 2] dargestellt. Das linke Bild zeigt das Ergebnis mit dem Newton-Verfahren; bei der Animation im rechten Bild durchläuft der Parameter β die Werte von 1, 0.9, 0.8, ..., 0.1, 0.01, 0.001, ..., 0.000001. 

Basins of Attraction z^3-1=0 Newton-Verfahren, B=[-2, 2]x[-2, 2]
Basins of Attraction z^31=0 Steffensen-Verfahren, B=[-2, 2]x[-2, 2], beta=1, ..., 0.000001

Mit kleinen Werten für β ergibt sich ein weiterer Effekt: die Rechenzeiten werden auf Grund der kleineren Bereiche, in denen das Verfahren nicht konvergiert, drastisch verkürzt. So erfolgt z.B. die Berechnung für
z^4 - 1 = 0 und B = [-10, 10] x [-10, 10]
für β = 0.000001 ca. 6-mal schneller als für β = 0.01.

 

Basins of Attraction für z^4 - 1 = 0

β = 0.01   N = 1024   ε = 10-6   1024 x 1024 Pixel

 ~ 4.74 sec.

Basins of Attraction für z^4 - 1 = 0

β = 0.000001  N = 1024  ε = 10-6  1024 x 1024 Pixel

 ~ 0.81 sec.


Quellenverweise

 

[1]   A. Cordero, F. Soleymani, J. R. Torregrosa, S. Shateyi (2014) Basins of Attraction for Various
       Steffensen-Type Methods,
Journal of Applied Mathematics, Volume 2014, Article ID 539707,
       http://dx.doi.org/10.1155/2014/539707