Ein-Schritt-Verfahren (one-step methods)

  • Newton-Verfahren (komplex)
  • Halley-Verfahren (komplex)
  • Schröder-Verfahren (komplex)
  • Householder-Verfahren (komplex)
  • Basto-Verfahren (komplex)
  • Whittaker I -Verfahren (komplex)
  • Whittaker II -Verfahren (komplex)
  • Euler-Chebyshev-Verfahren (komplex)
  • Chun-Kim I -Verfahren (komplex)
  • Sekanten-Verfahren (komplex)
  • Steffensen-Verfahren (komplex)

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).

Die Anwendung der Verfahren für einige komplexe Funktionen finden Sie unter Basins of Attraction.


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.

 

Die Anwendung des Verfahrens für einige komplexe Funktionen finden Sie unter Basins of Attraction.


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.

 

Die Anwendung des Verfahrens für einige komplexe Funktionen finden Sie unter Basins of Attraction.


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.

 

Die Anwendung des Verfahrens für einige komplexe Funktionen finden Sie unter Basins of Attraction.

 

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.

Die Anwendung des Verfahrens für einige komplexe Funktionen finden Sie unter Basins of Attraction.

 

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:

Die Anwendung des Verfahrens für einige komplexe Funktionen finden Sie unter Basins of Attraction.

 

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:

Die Anwendung des Verfahrens für einige komplexe Funktionen finden Sie unter Basins of Attraction.

 

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.

 

Die Anwendung des Verfahrens für einige komplexe Funktionen finden Sie unter Basins of Attraction.

 

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.

Die Anwendung des Verfahrens für einige komplexe Funktionen finden Sie unter Basins of Attraction.

 

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


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