Weiß man zusätzlich, dass die Funktion 2x stetig differierbar ist, benötigt man für die Bestimmung der Extremalpunkte einer Funktion die Nullstellen der 1. Ableitung und man setzt dazu und wendet auf das Nullstellenverfahren an. Mit der 2. Ableitung entscheidet man, ob ein Minimum oder Maximum vorliegt.
Ein Fixpunkt einer Funktion ist ein Punkt mit der Eigenschaft , also dem Schnittpunkt des Graphen von mit der Winkelhalbierenden. Auch diese Problem kann man in ein Problem der Nullstellensuche überführen, indem man über definiert. Ein Fixpunkt von ist damit eine Nullstelle von .
Ist eine Funktion gehen, so ist es im allgemeinen nicht notwendigerweise der Fall, dass gilt und damit eine Vorzeichenwechsel bei den Intervallrenzen vorliegt. In einem solchen Fall kann ggf. auf ein Teilintervall in übergehen, für das .
Um eine möglichst gute Startnäherung für jede solche Nullstelle zu erhalten, sucht man dann Teilintervalle in , in dem ein Vorzeichenwechsel vorliegt und möglichst nur eine Nullstelle liegt.
Dazu berechnet man im Allgemeinen Funktionswerte mit
für ein gegebenes, genügend großes . Dadurch zerlegt man das Ausgangsintervall in Teilintervalle und identifiziert die Teilintervalle in denen ein Vorzeichenwechsel vorliegt.
Die Menge aller bezeichnet man auch als ein Gitter in , die selbst als Gitterpunkte und den Prozess der Auswahl von endlich vielen Punkten aus als Diskretisierung des Intervalls.
Es werden im Folgenden eine Reihe von Verfahren behandelt, die, ausgehend von einem solchen Intervall mit Vorzeichenwechsel, unter geeigneten Bedingungen eine genäherte Nullstelle von liefern. Dabei geht man davon aus, dass eine Funktion zumindest stetig ist, denn liefert dem Zwischenwertsatz die Existenz einer Nullstelle mit . Für das Newtonverfahren benötigt man noch die zusätzliche Eigenschaft der Differenzierbarkeit, weil die Ableitung für die Interation von zu benötigt wird.
Das erste Verfahren, das wir vorstellen wollen, ist das Intervallschachtelungs- oder auch Bisektionsverfahren. Bei diesem wird, beginnend mit dem Intervall , eine Folge von Intervallen erzeugt, so dass und damit gilt. Dieses Verfahren verwendet in jeder Iteration als einzige Information nur die Vorzeichen der Funktionswerte an den Randpunkten des aktuellen Intervalls, so dass keine schnelle Konvergenzgeschwindigkeit zu erwarten ist.
Da und stetig ist, ist daher das Abbruchkriterium in Schritt (2) von Algorithmus nach endlich vielen Schritten erfüllt. Statt dieses Abbruchkriteriums, das beispielsweise im Fall
ungünstig ist, könnte man alternativ oder zusätzlich auch die Abfrage mit einer kleinen Konstante als
Abbruchkriterium verwenden.
Das Bisektionsverfahren ist ein sicheres und numerisch stabiles Verfahren, aber mit langsamer Konvergenz. Es konvergiert i. a. nicht einmal linear. Für die Fehler zweier aufeinander folgender Iterierter und kann sogar gelten:
Beispiel für Fehlervergrößerung in einem Iterationsschritt
Für die Funktion kann man die Nullstelle in direkt angeben. Im Beispiel wird diese mit Bisektionsverfahren berechnet. Ferner ist stetig und erfüllt und die Voraussetzung für die Anwendung des Bisektionsverfahrens:
Bei der Regula Falsi verwendet man im -ten Schritt die Sekante, welche die Punkte und verbindet. Diese Gerade kann durch Graph einer Funktion dargestellt werden
Man startet mit einer stetigen Funktion , die auf dem Intervall einen Vorzeichenwechsel bei den Funktionswerten besitzt (d.h. ). Dann berechnet in jedem Iterationsschritt jeweils den Schnittpunkt der Sekante durch die Punkte und . Die Schnittpunkt teilt das Intervall in zwei Teilintervalle. Wenn gilt, hat man eine Nullstelle gefunden. Falls das , betrachtet man das Teilintervall in dem dann ein Vorzeichnenwechsel vorliegt.
Die Abbruchbedingung (2) schließt wieder den Fall mit ein, dass gilt, also die Sekante durch die Punkte die x-Achse bereits in der gesuchten Nullstelle schneidet.
Für die Regula Falsi ist keine aussagekräftige Fehlerabschätzung erhältlich. Aber sie konvergiert unter gewissen Voraussetzungen mindestens linear (siehe z. B. Stoer). Man beachte, dass wegen keine Auslöschung bei der Berechnung von eintritt, so dass das Verfahren überdies numerisch stabil ist. Die erzeugten Näherungen liegen alle im Ausgangsintervall und können alle auf einer Seite der gesuchten Nullstelle liegen.
Beim Sekantenverfahren wählt man, ähnlich wie bei der Regula Falsi, die Nullstelle einer Sekante als neue Iterierte, wobei jeweils die Sekante von den beiden letzten Iterationspunkten und des Graphen von verbunden werden. Der nächste Stelle der Iteration wieder der Schnittpunkt der Sekante mit der -Achse, wenn dieser existiert.
Bei Regula Falsi wird die Sekante in einem Teilintervall zwischen den Punkten und gebildet, in dem ein Vorzeichenwechsel . Damit liegt die nachfolgende Iterationstelle in dem Teilintervall .
Beim Sekantenverfahren kann es möglich sein, dass die Sekantensteigung zwischen den beiden letzten Iterationspunkten und so gering ist, dass der Schnittpunkt mit der -Achse außerhalb des Definitionsbereiches liegt.
Im ungünstigen Fall, dass gilt, hat die Sekante sogar überhaupt keinen Schnittpunkt mit der -Achse und das Verfahren bricht ab.
Im Allgemeinen kann man zwei Startstellen wählen, die die Eigenschaft haben sollten, dass die zugehörige Sekante eine Schnittpunkt mit der -Achse in besitzt. Dabei muss nicht notwendig gelten. Wenn allerdings die Voraussetzung erfüllt ist, so kann man analog zu Regula Falsi und wählen. In weiteren Iterationsschritten werden sich dann aber die Sekanten von Regula Falsi und dem Sekantenverfahren unterscheiden.
Man beachte hier beim Sekantenverfahren in Schritt (1), dass man die Iterierte im -ten Schritt eines Verfahrens meist als Korrektur der Iterierten im -ten Schritt schreibt, also in der Form mit einem mit:
Bei Konvergenz des Verfahrens gegen muss man zumindest für größere voraussetzen, dass also die Iterationsstellen genügend nahe bei der gesuchten Nullstelle liegen.
Während bei dem Bisektionsverfahren und der Regula Falsi die Konvergenz durch den Vorzeichenwechsel in dem jeweils betrachtet nächsten Teilintervall mit und den sich immer weiter halbierende Intervallen sofort einleuchtet, ist das beim Sekantenverfahren nicht klar.
Bei Regula Falsi wird die Sekante bzgl. der Intervallgrenzen von gebildet, was zu einer monoton steigenden Folge und einer monoton fallenden Folge führt, die beide gegen die Nullstelle konvergieren . Beim Sekantenverfahren weist die Folge der Iterationsstellen in der Regel kein Monotonieverhalten auf (weder steigend noch fallend)
muss im Allgemeinen beim Sekantenverfahren nicht gelten, so dass das Verfahren im Allgemeinen nur lokal konvergiert. Genauer kann man den folgenden Satz beweisen (vgl. Isaacson and Keller[1]):
Unterschied zwischen Sekantenverfahren und Regula Falsi
Bei der Anwendung des Sekantenverfahrens wird die Sekanten immer bzgl. der beiden vorhergehenden Iterationsstellen und gebildet und damit die nächste Iterationsstelle berechnet, während bei der Regula Falsi die Sekante bzgl. der linken und rechten Intervallgrenze bzw. gebildet wird, in dem ein Vorzeichenwechsel der stetigen Funktion zu finden ist.
Konsequenz der Unterschiede zwischen Sekantenverfahren und Regula Falsi
Sei , und es existiere ein mit und . Sind die Anfangsnäherungen und hinreichend nahe bei gewählt, so konvergiert nach Streichung des Abbruchkriterium in Schritt (2) durch das Sekantenverfahren erzeugte Folge superlinear gegen von der Ordnung .
Das Sekantenverfahren konvergiert also im Allgemeinen schneller als das Bisektionsverfahren und die Regula Falsi. Anders als diese, neigt es aber zu instabilem Verhalten, da der Fall und damit Auslöschung bei der Berechnung von eintreten kann.
Die schnelle Konvergenz des Sekantenverfahrens soll an einem Beispiel demonstriert werden.
Beispiel - Berechnung Wurzel 2 mit Sekantenverfahren
Es soll berechnet werden. Dies kann man tun, indem man die positive Nullstelle der Funktion . Mit dem Startintervall sucht man die Nullstelle und z.B. mit dem Startintervall bestimmt man näherungsweise die Nullstelle . In dem folgenden Beispiel setzen wir .
Hätte man mit der ursprünglichen Formel gearbeitet, wie man das meist in der Praxis zu tun hat, so hätte man 2 Funktionsauswertungen von zur Berechnung von und jeweils eine für die von bis , d. h. insgesamt 5 Funktionsauswertungen zur Berechnung von benötigt.
Funktionsauswertungen sind in vielen Situationen ein gutes praktisches Vergleichskriterium für unterschiedliche Algorithmen zur Lösung eines Problems, da diese häufig die numerisch teuersten Teilaufgaben bei der Problemlösung darstellen.
Es sei nun und die Existenz eines mit vorausgesetzt. Beim Newton-Verfahren benötigt man nur eine Startnäherung für . Ist die Näherung für zu Beginn der -ten Iteration, so wählt man bei diesem Verfahren die Nullstelle der Tangente im Punkt an den Graphen von als nächste Näherung.
Wenn wir beispielsweise voraussetzen ( ist dann eine einfache Nullstelle), können wir dabei zumindest für solche , die nahe bei liegen, annehmen. Wenn die Ableitung stetig ist, gibt es eine Umgebung , in der nur positiv (streng monoton steigend) oder nur negativ ist (streng monoton fallend).
Abgebraische und geometrische Konsequenzen von f'(x)=0
(Algebra) Wenn man sich die Iterationsvorschrift vom Newtonverfahren ansieht, führt im Nenner zu einem undefinierten Iterationsschritt für die Definition von .
(Geometrie) Im Fall und hätte die Tangente als Parallele zur -Achse auch keine Nullstelle, wobei das Newton-Verfahren keine nächste Iterationsstelle liefert.
Bei direkter Verwendung von der allgemeinen Iterationsvorschrift
muss man für jeden Iterationsschritt neben Division und Subtraktion einmal und einmal auswerten.
Das wären für die Berechnung von jeweils 3 Funktionsauswertungen von und , also insgesamt 6 Funktionsauswertungen erforderlich gewesen. Das Newtonverfahren ist also in diesem Fall ein sehr schnelles Verfahren.
Wir wollen uns nun mit der Konvergenz des Newton-Verfahrens beschäftigen. Dazu holen wir etwas weiter aus. Für eine gegebene Funktion nennen wir einen Punkt mit
einen Fixpunkt von . Weiter sprechen wir bei der Iterationsvorschrift
von der Fixpunktiteration mit der Verfahrensfunktion. Ist stetig und konvergiert die Iteriertenfolge, so muss ihr Grenzwert offenbar notwendig ein Fixpunkt von sein. Man beachte in diesem Zusammenhang, dass genau dann Fixpunkt von ist, wenn Nullstelle z. B. der Funktion ist, dass also die Probleme der Bestimmung einer Nullstelle und der eines Fixpunktes einer Funktion äquivalent sind.
Sei gegeben und Fixpunkt von . Weiter sei in -mal differenzierbar mit einem , und es gelte entweder
für oder
für
Dann existiert ein , so dass die durch erzeugte Iteriertenfolge für jeden Startpunkt gegen konvergiert und zwar mindestens von der Ordnung . Im Fall ist die Konvergenzordnung genau .
Taylorentwicklung von um liefert für beide Fälle in (5.10)
für
Somit hat man
(5.11)
so dass zu einem gegebenen ein existiert und
(5.12)
mit und gilt. Im Fall sei dabei so klein gewählt, dass
ist, was aufgrund der Voraussetzung möglich ist. Für ist es offenbar möglich, so klein zu wählen, dass für alle folgt.
Die Ungleichung (5.12) impliziert nun für auch und damit im Fall auch für alle , so dass man
hat und daraus wegen die Konvergenz von mindestens der Ordnung schließen kann. Ist die Zusatzbedingung erfüllt und wird oben so gewählt, dass gilt, so gilt wegen (5.11)
(5.13)
Daraus folgt die genaue Konvergenzordnung in diesem Fall, denn wäre diese mindestens , so folgte mit (5.13) für ein und ein
und damit im Widerspruch zu Konvergenz von gegen
q.e.d.
In dem folgenden Satz wird nun unter verschiedenen Voraussetzungen eine jeweilige Konvergenzordnung des Newton-Verfahrens angegeben.
Es sei gegeben und es existiere mit . Mit einem sei weiter für Aussage (i) und für Aussage (ii) . Dann gilt nach Streichung von Schritt (2) für die durch das Newton-Verfahren (Algorithmus 8) erzeugte Folge :
(i) Ist , dann existiert ein , so dass für jeden Startpunkt gegen konvergiert und zwar mindestens quadratisch. Im Fall konvergiert sogar von einer Ordnung .
(ii) Ist andererseits eine -fache Nullstelle von mit einem , d. h., ist
und ist weiter in zweimal differenzierbar, so ist die Iterationsfunktion
(5.14)
des Newton-Verfahrens differenzierbar in mit
(5.15)
und existiert ein , so dass für jeden Startpunkt (genau) linear gegen konvergiert.
Die Behauptung folgt mit Satz 5.9, wenn man diesen auf in (5.14) anwendet sowie mit den folgenden Darstellungen. Im Fall (i) zeigt man zunächst die Stetigkeit von und in . Man ermittelt dann
so dass also
gilt. Damit folgt die Behauptung.
Im Fall (ii) erhält man
und somit
(5.16)
Wegen folgt damit und ist demzufolge aus (5.14) stetig in . Weiter hat man mit (5.16) wegen
Also ist und damit insbesondere auch .
q.e.d.
Man beachte, dass das Newton-Verfahren pro Iteration zwei Funktionsauswertungen benötigt, während das Sekanten-Verfahren nur eine verlangt. Im Fall, dass der Grenzwert eine einfache Nullstelle ist, konvergiert letzteres Verfahren unter geeigneten Voraussetzungen aber nur superlinear, während das Newton-Verfahren dann mindestens quadratisch konvergiert. Es stellt sich also die Frage, welches der Verfahren in der Praxis effizienter ist. Bemerkenswert ist es daher, dass man zeigen kann, dass das Sekantenverfahren, wenn man zwei Iterationen zu einer zusammenfasst und es damit etwa gleichen Aufwand pro Iteration wie das Newton-Verfahren bekommt, eine Konvergenzrate von mindestens hat, und es folglich lokal schneller als das Newton-Verfahren konvergiert. Allerdings neigt das Sekanten-Verfahren, anders als das Newton-Verfahren, aufgrund von Auslöschungen zu instabilem Verhalten.