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

Basins of Attraction (z^2-1)^2=0 Newton Verfahren, a=1 oder a=2

Konvergenzgeschwindigkeit (z^2-1)^2=0 Newton Verfahren, a=1

Konvergenzgeschwindigkeit (z^2-1)^2=0 Newton Verfahren, a=2

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 (x_n | y_n) 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 z₀ ϵ B noch einen zweiten Startwert z₁ ϵ B, der bei der Berechnung der Einzugsbereiche für verschiedene komplexe Funktionen (Basins of Attraction) in der Regel zu z₁ = (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 z^3-1=0, Steffensen-Verfahren, B=[-10, 10] x [-10, 10], beta=1

Basins of Attraction, β = 0.1

Basins of Attraction z^3-1=0, Steffensen-Verfahren, B=[-10, 10] x [-10, 10], beta=0.1

Basins of Attraction, β = 0.01

Basins of Attraction z^3-1=0, Steffensen-Verfahren, B=[-10, 10] x [-10, 10], beta=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