[WS] Eindimensionale Nullstellenprobleme 3 - Vergleich

Neue Frage »

tigerbine Auf diesen Beitrag antworten »
[WS] Eindimensionale Nullstellenprobleme 3 - Vergleich
Gliederung

  1. Fibonacci - Zahlen

  2. Sekanten - Methode

  3. Regula Falsi
tigerbine Auf diesen Beitrag antworten »
1. Fibonacci-Zahlen
Die Fibonacci-Folge ist wie folgt rekursiv definiert:






Für den Quotient aufeinander folgernder Folgenglieder gilt:

(Goldener Schnitt)


Ansatz:




Sofern die Folge also gegen einen Grenzwert c konvergiert, gilt dann:

und somit gilt



Direkte Berechnungsvorschrift (Binet)



mit



berechnen. Die Ganzzahligkeit der Folgenglieder ist dadurch gewährleistet, dass sich ungerade Potenzen von stets aufheben.
 
 
tigerbine Auf diesen Beitrag antworten »
2. Sekanten - Verfahren
In der Einführung [Workshop - Eindimensionale Nullstellenprobleme 1] wurde die Methode ja bereits vorgestellt. Nun soll sich mit der Frage beschäftigt werden:


"Ist die Sekante die bessere Tangente?"


Die Iterationsvorschrift lautet hier nun also, mit dem Differenzenquotient:




Wie schon erwähnt, ist dies eine Drei-Term-Rekursion. Zum Start benötigt man also 2 Werte . Nun soll in Analogie zum Newton-Verfahren die Konvergenz und das Konvergenzverhalten untersucht werden.
tigerbine Auf diesen Beitrag antworten »
2a. Sekanten - Verfahren für C²-Funktion
Sei f auf [a,b] zweimal stetig differenzierbar mit einfacher Nullstelle in x*. Gilt dann auf dem Intervall , so konvergiert das Sekantenverfahren mit der Ordnung


Beweis:

Schritt 1:
Aufgrund der Kompaktheit des Intervalls und der Stetigkeit der Funktionen f', f'' existieren:







Betrachte man nun den Differenzenquotienten




So folgt aus dem Mittelwertsatz der Differentialrechung die Abschätzung:




Schritt 2:

Nun benötigen man Wissen aus dem [Workshop - Polynominterpolation]. Man bestimmt ein Interpolationspolynom und den zugehörigen Interpolationsfehler.


Interpoliert wird in den Punkten . Dann lautet die Newton-Form des IPs (beachte die Gestalt der dividierten Differenzen):



Für den Interpolationsfehler gilt:




Somit erhält man:






Mit der Iterationsvorschrift des Sekantenverfahrens




ergibt sich dann:




Schritt 3:

Nun stellt man das Ergebnis von 2 um




Betragsmäßig also




Mit den Abschätzungen aus Schritt 1 folgt nun also

(#)


Diese Art der Abschätzung kennt man schon aus [Workshop - Eindimensionale Nullstellenprobleme 2] Daraus folgt, dass die Sekantenmethode konvergieren wird, wenn man die Startwerte nur nahe genug bei x* wählt. Was nun noch fehlt die Bestimmung des Exponenten q (Bezeichnung siehe Linkverweis). Nun setzt man



und damit erhält man auch




Eingesetzt in (#) ergibt sich dann:




Nun kommen wir zur Grenzwertbetrachtung. Da die Folge für geeignete Startwerte konvergiert, nähern sich die beiden Seiten also beliebig nahe an. Aus dem wird also beim Übergang ein






Somit gilt also die behauptete asymptotische Konvergenzordnung für geeignete Startwerte.
tigerbine Auf diesen Beitrag antworten »
2b. Sekante oder Tangente?
Kommen wir nun zur dieser Frage zurück. Was ist besser Sekantenverfahren oder Newton-Verfahren?

Beim Sekantenverfahren ist je Schritt nur eine neue Funktionsauswertung nötig, wogegen beim Newton-verfahren die Funktion und die Ableitung ausgewertet werden müssen. Faßt man nun 2 Schritte des Sekantenverfahrens zusammen, so erhält man ein Verfahren mit der asymtotischen Ordnung von



Lokal ist das Sekantenverfahren also schneller als das Newton-verfahren.

Jedoch kann es diesen Vorteil auch sofort wieder verlieren, da es in der Nähe der gesuchten x* bei (nicht alternierenden Vorzeichen ) im Nenner zur Auslöschung kommen kann.


Und nun? Die Lösung liegt in einem Mittelweg. Der Regula Falsi.
tigerbine Auf diesen Beitrag antworten »
3. Regula Falsi
Die Probleme beim Sekantenverfahren sollen nun dadurch beseitigt werden, dass sichergestellt wird, dass gilt:




Damit dies möglich ist, muss es sich bei x* um eine Nullstelle mit Vorzeichenwechsel handeln (ungerade Vielfachheit). Das Verfahren konvergiert sicher gegen die Nullstelle, die Konvergenzordnung ist i.A. jedoch nur linear. Es kann in Extremfällen sogar langsamer konvergieren als das einfache Intervallschachtelungsverfahren.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »