Kurs:Numerik I/Nullstellenverfahren

Nullstellenbestimmung reeller Funktionen einer Veränderlichen

Bearbeiten

Häufig sucht man in Anwendungen für eine gegebene stetige Funktion   eine Nullstelle (auch Wurzel genannt), d. h. einen Punkt   mit  .

Diffentialrechnung - Extremalpunkte

Bearbeiten

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.

Wurzeln mit Nullstellenverfahren bestimmen

Bearbeiten

Wenn die Wurzel   für   näherungsweise bestimmen möchte, sucht man z.B. für nach der Nullstelle der Funktion  

  • in dem Intervall   für   und
  • in dem Intervall   für  .

Fixpunkte

Bearbeiten

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  .

Aufgaben

Bearbeiten
  • Analysieren die folgenden Nullstellenverfahren und berechnen Sie die Wurzel von 5 näherungsweise mit Tabellenkalkulation (LibreOffice).
  • Definieren Sie eine Funktion   mit der man die 3. Wurzel aus   bestimmen kann.
  • Geben Sie eine Funktion   mit dem Intervall   an, wobei man mit Nullstellenverfahren die Stellen   näherungsweise bestimme kann, für die   gilt.

Startintervall für Nullstellenverfahren

Bearbeiten

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  .

Teilintervall mit Vorzeichenwechsel

Bearbeiten

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.

Zerlegung des Intervalls in Teilintervalle

Bearbeiten

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.

Funktionswerte an Gitterpunkten

Bearbeiten

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.

Zwischenwertsatz - Analysis

Bearbeiten

Sind   und   (anderenfalls hätte man eine Nullstelle von   gefunden) und ist

 

so muss   nach dem Zwischenwertsatz im Intervall   eine (einfache) Nullstelle besitzen und können wir   und   setzen.

Anwendung unterschiedlicher Nullstellenverfahren

Bearbeiten

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.

Bemerkung

Bearbeiten

Im Folgenden wird vorausgesetzt, dass   für   erfüllt ist.


Das Bisektionsverfahren

Bearbeiten

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.

Animation - Bisektionsverfahren

Bearbeiten

 


Algorithmus - Bisektionsverfahren

Bearbeiten
(0) Gib   mit   und  . Setze  .
(1) Berechne   und  .
(2) Falls  , stop!
(3) Falls  , setze  .
Falls  , setze  .
(4) Setze   und gehe nach (1).

Intervallbreite im Bisektionsverfahren

Bearbeiten

Offenbar gilt für die Länge der bei der Bisektionsmethode erzeugten Intervalle  

 

Wenn Algorithmus in Schritt (2) nicht abgebrochen wird, folgt damit

 

Einschachtelung der Nullstelle

Bearbeiten

Wegen   sowie   oder   hat man weiter mit der Abschätzung der Intervallbreite

 

und demnach

 

Bemerkung - Abbruchkriterium Bisektionsverfahren

Bearbeiten

Die Abbruchbedingung (2)   schließt u.a. den Fall mit ein, dass   gilt, also bei der Intervallmitte bereits die gesuchte Nullstelle gefunden wurde.

Abbruchkriterium

Bearbeiten

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.


Beispiel - Genauigkeit Bisektionsverfahren

Bearbeiten

Ist  , so folgt aus (5.6)

 
 
 

Bemerkung - Konvergenzgeschwindigkeit und Stabilität

Bearbeiten

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

Bearbeiten

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:

 
 

und demzufolge wird der Fehler von   zu   größer:

 

Die Regula falsi

Bearbeiten

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

 

Schnittpunkt mit der x-Achse

Bearbeiten

Der Graph der  -ten Sekante   schneidet die  -Achse in dem folgenden Punkt:

 

Der Punkt   wird nun als neue Näherung für   genommen. Ansonsten verfährt man wie bei der Bisektion.

Zeigen Sie, dass der Punkt   ein Nullstelle der Funktion   ist.

Animation - Regular Falsi

Bearbeiten

 

Algorithmus (Regula Falsi)

Bearbeiten

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.

Algorithmus - Regula Falsi

Bearbeiten
(0) Gib   mit   und  . Setze  .
(1) Berechne   sowie  .
(2) Falls  , stop!
(3) Falls  , setze  .
Falls  , setze  .
(4) Setze   und gehe nach (1).

Bemerkung - Abbruchkriterium Regula Falsi

Bearbeiten

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.

Fehlerabschätzung - Regula Falsi

Bearbeiten

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.

Sekantenverfahren

Bearbeiten

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.

Unterschiede - Regula Falsi und Sekantenverfahren

Bearbeiten
  • Bei Regula Falsi wird die Sekante zwischen den Punkten   und   gebildet.
  • Beim Sekantenverfahren wird die Sekante zwischen den beiden letzten Iterationspunkten   und   des Graphen von   gebildet.

Konsequenzen der Unterschiede - Regula Falsi und Sekantenverfahren

Bearbeiten
  • 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.

Wahl der Startwerte - Sekantenverfahren

Bearbeiten

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.

Berechnung der Nullstelle der Sekanten

Bearbeiten

Die Nullstelle der Sekante beim Sekantenverfahren ist offenbar durch

 

gegeben.

Animation (Sekantenverfahren)

Bearbeiten

 

Algorithmus - Sekantenverfahren

Bearbeiten
(0) Gib   und  . Berechne   sowie   und setze  .
(1) Berechne
 
sowie  .
(2) Falls  , stop!
(3) Setze   und gehe nach (1).

Bemerkung - Korrektur der Iterierten

Bearbeiten

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.

Konvergenz vom Sekantenverfahren

Bearbeiten

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.

Monotonie

Bearbeiten

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)

Intervalle aus Interationstellen

Bearbeiten

Auch der Fall

  •   bei   bzw.
  •   bei  

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

Bearbeiten

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

Bearbeiten

Als Konsequenz der der Unterschiede zwischen Sekantenverfahren und Regula Falsi ergibt sich daher,

  • dass bei der Regula Falsi der nächste Iterationspunkt   immer im Intervall   liegen muss,
  • dass bei dem Sekantenverfahren der Schnittpunkt der Sekante mit der  -Achse nicht notwendigerweise zwischen   und   liegen muss.

Ferner ergeben sich auch Unterschiede in der Konvergenzgeschwindigkeit.

Satz - Konvergenz Sekantenverfahren

Bearbeiten

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  .

Bemerkung - Konvergenz Sekantenverfahren

Bearbeiten

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

Bearbeiten

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  .

Näherungsweise Angabe der Nullstelle

Bearbeiten

Der gesuchte Wert lautet auf 12 Stellen hinter dem Dezimalpunkt genau

 

Vereinfachung der Interationsvorschrift

Bearbeiten

Die Iterationsvorschrift des Sekantenverfahrens lässt sich hier durch Anwendung der 3. Binomischen Formel im Quotienten wie folgt vereinfachen:

 

Startstellen des Sekantenverfahrens

Bearbeiten

Die Startstellen sollte nahe bei der gesuchten Nullstelle liegen und verwendet daher als Startstellen   und  

Interationsschritt 1

Bearbeiten

Man errechnet mit   und   für  

 

mit   und   für  

Interationsschritt 2

Bearbeiten
 

usw.

Iteriertenfolge

Bearbeiten

Insgesamt erhält man die Iteriertenfolge

  •  
  •  
  •  
  •  

wobei die richtigen Ziffern jeweils unterstrichen sind.

Bemerkung - Berechnungsaufwand

Bearbeiten

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.

Newton-Verfahren für Nullstellen

Bearbeiten

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.

Gleichung der Tangente

Bearbeiten

Die Funktion  , dessen Graph die Tangente in   beschreibt, wird wie folgt definiert:

 

gegeben, so dass man   für folgendes   erfüllt ist:

 

erhält.

Aufgaben

Bearbeiten
  • Erläutern Sie an einem Schaubild/Zeichnung die Herleitung des Funktionsterms von  !
  • Erläutern Sie an einem eigenzeichnet Steigungsdreieck in einer Skizze die geometrische Herleitung des Terms  !

Bemerkung - Eigenschaft der Ableitung an der gesuchten Nullstelle

Bearbeiten

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

Bearbeiten
  • (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.

Animation der Iteration

Bearbeiten

 

Algorithmus - Newton-Verfahren

Bearbeiten
(0) Wähle ein   und  , berechne   und setze  .
(1) Berechne  ,
(5.9)  
und  .
(2) Falls  , stop!
(3) Setze   und gehe nach (1).

Beispiel - Newton-Verfahren zur Berechnung der Wurzel 2

Bearbeiten

Man betrachtet nun eine Funktion   mit dem Funktionsterm   und damit ist  . Gesucht ist die positive Nullstelle   von  .

Berechnung der Iterationsvorschrift

Bearbeiten

Die Iterationsvorschrift des Newton-Verfahrens lässt sich hier schreiben als

 

Startwert der Iteration

Bearbeiten

Beginnend mit   und   berechnet man die Iterierten

  •  
  •  
  •  

Bemerkung - Notation

Bearbeiten

Die unterstrichen Ziffern nach dem Iterationsschritt bezeichnen, wie viele Stelle bereits mit der gesuchten Nullstelle von   übereinstimmen

Berechnungsaufwand

Bearbeiten

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.

Vergleich mit Sekantenverfahren im Beispiel

Bearbeiten

Bei diesem Beispiel   und der Wahl von Startwerten (!) erreicht das Sekantenverfahren aber mit etwas weniger Aufwand sogar etwas höhere Genauigkeit.

Konvergenz des Newton-Verfahrens

Bearbeiten

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.

Bemerkung

Bearbeiten

Wir beweisen nun folgenden allgemeinen Satz über die lokale Konvergenz der Fixpunktiteration, wobei

 

eine offene  -Umgebung des Punktes   bezeichne.

Konvergenzsatz - Fixpunktiteration

Bearbeiten

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  .

Beweis - Konvergenzsatz - Fixpunktiteration

Bearbeiten

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.

Konvergenzsatz - Newton-Verfahren

Bearbeiten

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.

Literatur

Bearbeiten
  1. Isaarcson E., Bishop Keller, H. (1966) Analysis of Numerical Methods, Wiley Sons URL: https://vdocument.in/isaacson-keller-analysis-of-numerical-methods.html?page=1

Siehe auch

Bearbeiten

Seiteninformation

Bearbeiten

Diese Lernresource können Sie als Wiki2Reveal-Foliensatz darstellen.

Wiki2Reveal

Bearbeiten

Dieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Kurs:Numerik I' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.