Iterative Verfahren zur Nullstellenbestimmung

Um für eine (stückweise) stetige Funktion f deren Nullstelle(n) zu bestimmen - also die Gleichung f (x) = 0 zu lösen - bietet sich, falls alle anderen Methoden (s. Nullstellen Grundlagen) "versagen", eine numerische Lösung mit iterativen Verfahren an.

 

Bei solch einem Verfahren / Algorithmus wird - ausgehend von einem oder mehreren Startpunkten (in der Nähe der vermuteten Nullstelle) - eine Iteration durchgeführt, die im günstigen Fall (nach einigen wenigen Schritten) gegen die Nullstelle konvergiert, d.h. dass das Abbruchkriterium  | xi – xi-1 | < ε  für eine gewünschte Genauigkeit ε erfüllt ist.    

 

Im Allgemeinen kann nicht garantiert werden, dass ein Algorithmus zur Nullstellenbestimmung alle Nullstellen einer Funktion findet. Falls dieser also keine Nullstelle findet, bedeutet dies nicht, dass keine Nullstelle existiert.

Wünschenswert wäre natürlich ein Algorithmus, der für jeden Startwert x0 (oder für eine Kombination mehrerer Startwerte wie z.B. beim Tiruneh-Verfahren), stets und mit möglichst wenigen Iterationsschritten zur Nullstelle ξ konvergiert, d.h. dass für jede Folge {xi} gilt:

Leider existiert solch ein "Super-Algorithmus"  nicht. Neben konstruktionsbedingten Einschränkungen (z.B. versagt das Newton-Verfahren, falls die Ableitung für einen Wert xi der Iterationsfolge 0 wird) kann die Effizienz eines Algorithmus dramatisch von den Eigenschaften der gegebenen Funktion und von der Wahl der Startwerte abhängen.

 

Konvergenzordnung

Ein wichtiges Maß zur Beurteilung der Leistungsfähigkeit eines Algorithmus ist die Konvergenzordnung (auch Konvergenzgeschwindigkeit).

 

Ein Verfahren konvergiert linear, falls

Je kleiner die Konvergenzrate c ist, desto schneller konvergiert die Folge {xi} gegen die Nullstelle ξ.

 

Ist c = 0, spricht man von superlinearer Konvergenz. Um superlineare Konvergenzraten zu unterscheiden, führt man folgende Definition ein:

 

Falls für die Folge {xi} gilt:

dann konvergiert sie mit der Ordnung q gegen ξ für q > 1.

 

Hierbei muss q keine natürliche Zahl sein (z.B. ist beim Sekantenverfahren q = φ = 1.618 …). Ist q = 2, so liegt quadratische Konvergenz vor (z.B. beim Newton-Verfahren), bei q = 3 spricht man von kubischer Konvergenzordnung (z.B. Tiruneh-Verfahren), etc.

 

Eine praktische Methode, um die Konvergenzordnung eines Verfahrens / Folge zu bestimmen, ist die Berechnung der folgenden Sequenz dreier aufeinanderfolgender Glieder, die gegen q konvergiert und die mit COC (engl. Computational Order of Convergence) bezeichnet wird:

Die Diagramme in der folgenden Galerie zeigen dies für einige Verfahren anhand der Funktion f (x) = x³ - 4x² - 5 mit der positiven Nullstelle ξ = 1, dem Startwert xi = 3 und dem Abbruchkriterium | xi+1 – xi | ≤ 10-15.  

Effizienz-Index

Ein weiteres Maß bei iterativen Verfahren ist die Effizienz CE (engl. Computational Efficiency):

wobei q die Konvergenzordnung des Verfahrens (s.o.) ist und m die Anzahl erforderlicher Berechnungen der Funktion und - abhängig vom Verfahren - ihrer Ableitungen pro Iterationsschritt.

 

So beträgt z.B. die Effizienz beim Sekantenverfahren (2 Funktionsberechnungen: m = 2) CE = √1.6185 ≈ 1.2722; beim Newtonverfahren (1 Funktionsberechnung, 1 Berechnung der Ableitung: m = 2) ist sie größer:

CE = √2 ≈ 1.4142.

 

Konstruktion Iterativer Verfahren zur Nullstellenbestimmung

Das "klassische" Sekanten- und auch Newton-Verfahren zur Nullstellenbestimmung führen in manchen Fällen zu Problemen, wie z.B. sehr langsame Konvergenz, Divergenz, Oszillation und Sprünge (aus dem Bereich der gesuchten Nullstelle heraus); das Newton-Verfahren wird "abgewürgt", falls die Ableitung im Iterationspunkt den Wert 0 annimmt. 

 

Angesichts dieser Problemfälle wurden - interessanterweise viele in den letzten Jahren - vielfältige Modifikationen und Ersatzmethoden, meist "Hybride" aus verschiedenen Methoden, entwickelt und publiziert. Dabei lag das Ziel insbesondere auf der Erhöhung der Konvergenzordnung q, zusätzlich soll aber die Effizienz CE (s.o.) möglichst hoch sein.

 

Ein weiteres Optimierungsziel bei der Konstruktion eines Algorithmus besteht im Verzicht auf die Ableitung, zumindest auf höhere Ableitungen, indem diese approximiert werden, um zum einen dadurch m zu verringern. Zum anderen kann das Aufstellen höherer Ableitungen sehr aufwendig sein.

 

Aus der großen Vielzahl von Publikationen habe ich einige wenige mit neueren Verfahren unten unter Quellen zusammengestellt. In den Publikationen finden Sie in dortigen Referenzen weitere typische Verfahren.

 

Einige Verfahren werden auf meiner Webseite auf eigenen Unterseiten näher betrachtet:

Weitere Verfahren werden kurz und mit Beispielen vorgestellt  unter Diverse Verfahren.

 

Unter Verfahrensvergleich wurden bis dato (Aug. 2019) nur das Sekanten-, Newton- und Halley-Verfahren berücksichtigt; die Seite soll demnächst neu gestaltet werden ...


Links

 

[1]   Trevor J. McDougalla, Simon J. Wotherspoonb (2013), A simple modification of Newton’s method to
       achieve convergence of order 1 + √2, Applied Mathematics Letters 29 (2014) 20–25,
       http://dx.doi.org/10.1016/j.aml.2013.10.008

[2]   Gustavo Fernández-Torres (2015), A Novel Geometric Modification to the Newton-Secant Method
       to Achieve Convergence of Order 1 + √2 and Its Dynamics
, Modelling and Simulation in Engineering
       Volume 2015, http://dx.doi.org/10.1155/2015/502854

[3]   Ababu Teklemariam Tiruneh et al. (2013), A Two-Point Newton Method Suitable for Nonconvergent
       Cases and with Super-Quadratic Convergence, Advances in Numerical Analysis, Volume 2013,
       http://dx.doi.org/10.1155/2013/687382

[4]   S. Weerakoon, T. G. I. Fernandao (1998), A Variant of Newton’s Method with Accelerated Third-Order
       Convergence, Applied Mathematics Letters 13 (2000), 87-93

[5]   Manoj Kumar, Akhilesh Kumar Singh, Akanksha Srivastava (2013), Various Newton-type iterative methods
       for solving nonlinear equations, Journal of the Egyptian Mathematical Society (2013) 21, 334–339,
       http://dx.doi.org/10.1016/j.joems.2013.03.001

[6]   Mehdi Salimia, Taher Lotby, Somayeh Sharibz, Stefan Siegmund (2014), Optimal Newton-Secant like
       methods
without memory for solving nonlinear equations,
      
https://www.researchgate.net/publication/259360127

[7]   Obadah Said Solaiman, Ishak Hashim (2018), Two new efficient sixth order iterative methods for solving
       nonlinear equations, Journal of King Saud University – Science, https://doi.org/10.1016/j.jksus.2018.03.021

[8]   Iin Purnama Edwar, M. Imran, Leli Deswita (2016), A Sixth-Order Derivative-Free Iterative Method for
       Solving Nonlinear Equations, Bulletin of Mathematics, Vol. 08, No. 01 (2016), pp. 1–8

[9]   Muhammad Ra…ullah, Muhammad Haleem (2010), Three-Step Iterative Method with Sixth Order
       Convergence for Solving Nonlinear Equations, Int. Journal of Math. Analysis, Vol. 4, 2010, no. 50,
       2459 - 2463