Zwei-Schritt-Verfahren (two-step methods)

Bei den Zwei-Schritt-Verfahren (two-step methods) wird für jeden Iterationsschritt i zunächst ein Zwischenwert (predictor) berechnet. Üblicherweise wird hierzu das Newton-Verfahren verwendet. Der Zwischenwert wird dann mit dem "eigentlichen" Verfahren verbessert (corrector) (vgl. Erklärung beim Ostrowski-Verfahren für reelle Funktionen).

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

Das Ostrowski-Verfahren ist ein 2-Schritt-Verfahren; für  komplexe Funktionen f : D → ℂ  mit  D ⊆ ℂ beruht es auf der Iterationsvorschrift

Für weitere Details, Konvergenzordnung q und Effizienzindex CE siehe Ostrowski-Verfahren für reelle Funktionen.

Kou, Li und Wang stellten zur Nullstellenbestimmung komplexer Funktionen f : D → ℂ  mit  D ⊆ ℂ folgende Iterationsvorschrift auf:

Es handelt sich um ein 2-Schritt-Verfahren mit der Konvergenzordnung q = 4 und dem Effizienz-Index CE = 1.587.

Das Verfahren ist identisch mit dem King-Verfahren für β = 1.

Quellenverweise

[1]   J. Kou, Y. Li, X. Wang (2007), A composite fourth-order iterative method for solving non-linear
       equations, Applied Mathematics and Computation, Vol. 184, Issue 2, Jan. 2007, (471-475)
       https://doi.org/10.1016/j.amc.2006.05.181

In [1] (Gleichung 10) publizierte C. Chun ein Verfahren zur Nullstellenbestimmung, das für komplexe Funktionen f : D → ℂ  mit  D ⊆ ℂ auf folgender Iterationsvorschrift basiert: 

Es besitzt die Konvergenzordnung q = 4 bei einem Effizienzindex CE = 1.414.
Das Verfahren ist identisch mit dem King-Verfahren für β = 2.

Quellenverweise

[1]   C. Chun (2005), Iterative Methods Improving Newton's Method by the Decomposition Method,
       Computers and Mathematics with Applications 50 (2005) 1559-1568,
       doi:10A016/j.camwa.2005.08.022

R. F. King [1], [2] erzeugt für komplexe Funktionen f : D → ℂ  mit  D ⊆ ℂ mit der Iterationsvorschrift

und dem Parameter β eine Familie von 2-Schritt-Verfahren mit der Konvergenzordnung q = 4 und dem Effizienz-Index CE = 1.587 (s. dazu auch Iterative Verfahren zur Bestimmung von Nullstellen).

Für einige Werte β von  ergeben sich folgende andere Verfahren:

• β = 0:  es ergibt sich das Ostrowski-Verfahren
• β = 1:  identisch mit dem Verfahren Verfahren von Kou-Li-Wang
  
• β = 2:  entspricht dem Verfahren von Chun I

Quellenverweise

[1]   R.F. King, A family of fourth order methods for nonlinear equations (1973),
       SIAM J. Numer. Anal. 10 (1973), (876–879), https://www.jstor.org/stable/2156321

[2]   J. R. Sharma et al. 2012), Improved King’s methods with optimal order of convergence based on
       rational approximations, Applied Mathematics Letters, Volume 26, Issue 4, April 2013, (473-480),
       https://www.sciencedirect.com/science/article/pii/S0893965912004739

Das von C. Chung entwickelte zweistufige Verfahren [1] ist eine Weiterentwicklung des Newton-Verfahren mit der Konvergenzordnung q = 3 und dem Effizienzindex CE = 1.316. (s. dazu auch Iterative Verfahren zur Bestimmung von Nullstellen). Angewandt auf komplexe Funktionen f : D → ℂ  mit  D ⊆ ℂ lautet die Iterationsvorschrift:

Quellenverweise

[1]   C. Chun (2006), Construction of Newton-like iteration methods for solving nonlinear equations,
       Numer. Math. (2006) 104: 297–315, DOI 10.1007/s00211-006-0025-2

Eine Weiterentwicklung des Newton-Verfahren von C. Chung ist das zweistufige Verfahren (s. [1], Gleichung (57) mit h = -1) mit folgender Iterationsvorschrift für komplexe Funktionen f : D → ℂ  mit  D ⊆ ℂ:

Es besitzt die Konvergenzordnung q = 3 und den Effizienzindex CE = 1.442 (s. dazu auch Iterative Verfahren zur Bestimmung von Nullstellen).

Quellenverweise

[1]   C. Chun, Construction of Newton-like iteration methods for solving nonlinear equations, Numer. Math,
       104 (2006), 297-315

Das von J. Feng aufgestellte 2-stufige Verfahren basiert für komplexe Funktionen f : D → ℂ  mit  D ⊆ ℂ auf der Iterationsvorschrift [1]:  

Es besitzt lediglich quadratische Konvergenz (q = 2) und hat den Effizienzfaktor CE = 1.189 (s. dazu auch Iterative Verfahren zur Bestimmung von Nullstellen).

Quellenverweise

[1]   J. Feng, A New Two-step Method for Solving Nonlinear Equations (2009),
       International Journal of Nonlinear Science, Vol.8 (2009) No.1, (40-44)

In [1] stellt der Verfasser eine Erweiterung des Newton-Verfahrens vor, das er auf Grund des verwendeten Mittelwertes "Contra Harmonic Newton-Verfahren" nennt (s. auch [2] zum contra-harmonischen Mittelwert). Das zweistufige Verfahren hat für komplexe Funktionen f : D → ℂ  mit  D ⊆ ℂ die Iterationsvorschrift

und besitzt die Konvergenzordnung q = 3 bei einem Effizienzindex von CE = 1.442.

Quellenverweise

[1]   O. Y. Ababneh (2012),

New Newton’s Method with Third-order Convergence for Solving Nonlinear Equations (2012),

International Journal of Mathematical and Computational Sciences, Vol. 6, No. 1, 2012,

https://publications.waset.org/13005/pdf

[2]   https://en.wikipedia.org/wiki/Contraharmonic_mean

Kung und Traub stellten 1974 ein zweistufiges Iterationsverfahren vor mit folgender Iterationsvorschrift für komplexe Funktionen f : D → ℂ  mit  D ⊆ ℂ:

Mit der Konvergenzordnung q = 4 und dem Effizienzindex CE = 1.587  ist es ein optimales Verfahren.

Quellenverweise

[1]    H. T. Kung, J. F. Traub, (1974), Optimal Order of One-Point and Multipoint Iteration,
        Journal of the ACM 21(4), 643-651, DOI: 10.1145/321850.321860

Das von Fang et al. publizierte Verfahren Zweischritt-Verfahren zur Nullstellenbestimmung hat für komplexe Funktionen f : D → ℂ  mit  D ⊆ ℂ folgende Iterationsvorschrift:

Es besitzt die Konvergenzordnung q = 4 bei einem Effizienzindex CE = 1.414.

Quellenverweise

[1]   L. Fang, L. Ni, R. Chen (2013), Three Modified Efficient Iterative Methods for Non-linear Equations,
       Mathematical Computation, March 2013, Volume 2, Issue 1, (6-12)
       http://www.ivypub.org/MC/paperinfo/3415.shtml

In [1] entwickeln die Autoren ein Zwei-Schritt-Verfahren zur Nullstellenbestimmung ("Algorithmus 2"), das für komplexe Funktionen f : D → ℂ  mit  D ⊆ ℂ folgende Iterationsvorschrift besitzt: 

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

Quellenverweise

[1]    A. Rafiq, M. Rafiullah (2009), Some multistep iterative methods for solving nonlinear equations,
        Computers and Mathematics with Applications, 58(2009),1589–1

        https://www.sciencedirect.com/science/article/pii/S0898122109004672     

Die Verfasser konstruieren in [1] neue 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. Die dabei erforderliche zweite Ableitung f ''  approximieren sie durch den Differenzenquotienten (s. Differential/Ableitung) und erhalten schliesslich die folgende Iterationsvorschrift für komplexe Funktionen f : D → ℂ  mit  D ⊆ ℂ :

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

Das hier aufgeführte Verfahren beruht auf dem Chun-Kim I -Verfahren, indem die zweite Ableitung f ''  durch den Differenzenquotienten (s. Differential/Ableitung) approximiert wird. Es ergibt sich somit die folgende Iterationsvorschrift für komplexe Funktionen f : D → ℂ  mit  D ⊆ ℂ :

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

In [1] (Gleichung 16) präsentieren R. Sharma und A. Bahl ein 2-Schritt-Verfahren mit folgender Iterationsvorschrift für komplexe Funktionen f : D → ℂ  mit  D ⊆ ℂ 

Der Zwischenschritt (predictor) beruht hier auf einem mit dem Faktor 2/3 modifizierten Newton-Schritt.

Es handelt sich um ein optimales Verfahren mit der Konvergenzordnung q = 4 und einem Effizienzindex CE = 1.587.

Quellenverweise

[1]    R. Sharma, A. Bahl (2015),
        An Optimal Fourth Order Iterative Method for Solving Nonlinear Equations and Its Dynamics,
       Journal of Complex Analysis, Vol. 2015, Article ID 259167, http://dx.doi.org/10.1155/2015/259167

C. Chun, M.Y. Lee und B. Neta leiteten ein Verfahren für die Nullstellenbestimmung her [1] (Gleichung 24), das angewandt auf komplexe Funktionen f : D → ℂ  mit  D ⊆ ℂ auf folgender Iterationsvorschrift beruht:

Der Zwischenschritt (predictor) beruht hier - wie auch beim Verfahren von Sharma-Bahl auf einem mit dem Faktor 2/3 modifizierten Newton-Schritt. Das Verfahren hat die Konvergenzordnung q = 4 bei einem Effizienzindex CE = 1.587 und ist somit ein optimales Verfahren.

Quellenverweise

[1]    C. Chun, M. Y. Lee, B. Neta (2012),
        On optimal fourth-order iterative methods free from second derivative and their dynamics,
        Applied Mathematics and Computation 218 (2012) 6427–6438