[WS] Eindimensionale Nullstellenprobleme 1 - versch. Verfahren

Neue Frage »

tigerbine Auf diesen Beitrag antworten »
[WS] Eindimensionale Nullstellenprobleme 1 - versch. Verfahren
Gliederung

  1. Eindimensionale Nullstellenprobleme

  2. Bisektionsverfahren
    2a. Beschreibung des Verfahren
    2b. Bewertung

  3. Newton-Verfahren
    3a. Beschreibung des Verfahrens
    3b. Bewertung


  4. Sekanten-Verfahren
    4a. Newton-Verfahren mit finiten Differenzen
    4b. Drei-Term-Rekursion
    4c. Probleme

  5. Regula falsi

  6. Methode der inversen quadratischen Interpolation
tigerbine Auf diesen Beitrag antworten »
1. Skalare Gleichungen
Gesucht ist die Nullstelle x* der Funktion




Skalar, da hier der Fall betrachtet wird. Im folgenden sollen einige Lösungsverfahren vorgestellt werden.
tigerbine Auf diesen Beitrag antworten »
2. Bisektionsverfahren
Hierbei soll die Nullstelle von f mit Hilfe des Zwischenwertsatzes bestimmt werden. Somit muss f auf dem zu untersuchenden Intervall [a,b] stetig sein. Finden wir also ein Teilintervall mit [a',b'] mit o.B.d.A f(a') < 0 und f(b') > 0, so hat f auf diesem Intervall eine Nullstelle ungerader Vielfachheit.
tigerbine Auf diesen Beitrag antworten »
2a. Beschreibung des Verfahren
Gilt , dann hat f in[a,b] mindestens eine Nullstelle. Um sie zu bestimmen, halbieren wir das Intervall.



Nun werden die Teilintervalle auf Vorzeichenwechsel untersucht. Und die Prozedur in dem Intervall mit Vorzeichenwechsel fortgesetzt.



Bei wikipedia finden wir folgende anschauliche Darstellung:

http://upload.wikimedia.org/wikipedia/de/f/f0/Bisektion_Ani.gif
tigerbine Auf diesen Beitrag antworten »
2b. Bewertung
Laufzeit



Wir haben somit eine logarithmische Laufzeit in Abhängigkeit vom Verhältnis der Intervalllänge zur gewünschten Genauigkeit.


Vor- und Nachteile des Verfahrens:

Die Bisektion eignet sich für folgende Fälle:

  • Ein Vorzeichenwechsel liegt im gegebenen Intervall vor und die Funktion ist stetig

  • Die Startwerte der klassischen Verfahren (Newton-Verfahren, Regula Falsi) liegen nicht hinreichend nah genug an der Nullstelle, so dass dort keine lokale Konvergenz eintritt

  • Mehrfache Nullstellen mindern die Konvergenzgeschwindigkeit der klassischen Verfahren


Nachteile der Bisektion:
  • Bei einfachen Fällen (streng monotone Funktion) ist sie langsamer als ein quadratisch konvergentes Verfahren

  • Ohne Vorzeichenwechsel im gegebenen Intervall sind Zusatzprüfungen notwendig, um ein lokales Minimum von einer Nullstelle zu unterscheiden
tigerbine Auf diesen Beitrag antworten »
3. Newton-Verfahren
Die Nullstelle wird durch lineare Approximation der Funktion f bestimmt. Dazu wird das Taylorpolynom 1ten Grades um den Punkt bestimmt (entwickelt). Dessen Nullstelle ist dann eine Approximation von .

Voraussetzung ist hier natürlich das f stetig differenzierbar auf dem zu untersuchenden Intervall [a,b] ist.
 
 
tigerbine Auf diesen Beitrag antworten »
3a. Beschreibung des Verfahrens
Es folgt somit die Rekursionsvorschrift:





mit geeignetem Startwert .



Bei wikipedia finden wir die folgende Veranschaulichung:

http://upload.wikimedia.org/wikipedia/commons/e/e0/NewtonIteration_Ani.gif
tigerbine Auf diesen Beitrag antworten »
3b. Bewertung
Vorteile

  • i.A. schnelle Konvergenz


Nachteile

  • nur lokale Konvergenz (Wahl des richtigen Startwertes)

  • Funktion muss differenzierbar sein

  • Ableitung muss berechnet werden




Beispiel:

Betrachtet werden soll die Umkehrfunktion des Tangens.










Wählt man nun der Startwert zu weit von 0 entfernt, wird die Tangente zu flach und man entfernt sich immer weiter von der Nullstelle.
tigerbine Auf diesen Beitrag antworten »
4. Sekanten Verfahren
Anstatt wie beim Newton-Verfahren mit den Ableitungen zu rechnen, kann man als deren Näherungen Sekanten verwenden.

http://upload.wikimedia.org/wikipedia/commons/a/ad/Sekantenverfahren_Ani2.gif


Es ist nach Definition:




Wählt man nun klein genug, so gilt

tigerbine Auf diesen Beitrag antworten »
4a. Newton-Verfahren mit finiten Differenzen


  • geeigneter Startwert

  • 2 Auswertungen von f pro Iteration (anstelle der Ableitung)

  • finite Differenzen: endliche Differenz
tigerbine Auf diesen Beitrag antworten »
4b. Sekantenverfahren (Drei-Term-Rekursion)
Mit der Wahl von kann man sogar mit einer Funktionsauswertung pro Iteration auskommen.




Die benötigten beiden Startwerte können mit (4a) bestimmt werden.
tigerbine Auf diesen Beitrag antworten »
4c. Probleme
Die numerische Gefahr ist hier offensichtlich. Auslöschung im Nenner. Soll für das Verfahren doch gelten




So folgt aufgrund der Stetigkeit von f, dass sich auch die Funktionswerte immer weiter annähern. dies führt hier zur Gefahr der Division durch 0.
tigerbine Auf diesen Beitrag antworten »
5. Regula falsi
Sei f eine stetige Funktion. Dann ist die Regula falsi eine Kombination aus dem Bisektion-und dem Sekantenverfahren:

  • Bisektion
    Bestimme Intervall mit

    Neue Intervalle

    Prüfe und


  • Sekantenverfahren
    Bestimmung von als Nullstelle der Sekanten








http://upload.wikimedia.org/wikipedia/commons/thumb/9/99/Regula_falsi.gif/400px-Regula_falsi.gif
tigerbine Auf diesen Beitrag antworten »
6. Methode der inversen quadratischen Interpolation
Wie man durch 3 Punkte ein quadr.Polynom eindeutig legt, kann man im [WS] Polynominterpolation - Theorie sehen. Hier haben wir eine Funktion f gegeben und suchen x* mit f(x*)=0. Dieses x* ist der Funktionswert der Umkehrfunktion an der Stelle y=0.

Tauscht man also den Datensatz (f(x_1),x_1), (f(x_2),x_2), (f(x_3),x_3) so interpoliert man die Umkehrfunktion und p(0) ist eine Näherung für das gesuchte x*. (Link)


Auch diese Idee kann man mit der Bisektion kombinieren. (Link). und sollte es auch tun. Im Gegensatz zum Sekanten-Verfahren kann es durchaus vorkommen, dass p(0) außerhalb von [a,b] liegt. Selbst wenn liegt es innerhalb von [a,b], so sind die Teilintervalle wieder auf Vorzeichenwechsel zu untersuchen. Es empfiehlt sich auch zu vergleichen, ob dann das Bisektionsintervall nicht sogar kleiner ist.

Man kann sogar noch mehr Verfahren mit einander Verbinden: Brent-Verfahren
tigerbine Auf diesen Beitrag antworten »
Ausblick
Nach dieser Kurzvorstellung der Verfahren wird sich im nächsten Workshop genauer mit dem Newton-Verfahren auseinandergesetzt. Generell bleibt zu sagen, dass der Preis der gesicherten Konvergenz eines Verfahrens seine Geschwindigkeit ist. Ferner kostet einen die bessere Geschwindigkeit des Newtonverfahrens die Berechnung und Auswertung der Ableitung.
Neue Frage »
Antworten »



Verwandte Themen

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