[WS] Eindimensionale Nullstellenprobleme - Beispiele |
24.08.2007, 12:36 | tigerbine | Auf diesen Beitrag antworten » | |||||
[WS] Eindimensionale Nullstellenprobleme - Beispiele Beispiele zum Newton-Verfahren [Workshop - Eindimensionale Nullstellenprobleme 2]
Vergleiche von Verfahren und Sonderfälle
|
|||||||
24.08.2007, 17:38 | tigerbine | Auf diesen Beitrag antworten » | |||||
1. Newton-Verfahren zur Wurzelberechnung, a > 0 Die n-te Wurzel einer reellen Zahl a > 0 ist eine Nullstelle der Funktion Eine kleine Kurvendiskussion, zeigt, dass es für gerades n zwei Lösungen (symmetrisch zu 0) und ungerades n eine Lösungen in den reellen Zahlen gibt. Gesucht ist die nichtnegative Lösung. Das Newton-Verfahren zur Berechnung von lautet: Man sieht, dass das Verfahren nicht für definiert ist. Da eine nichtnegative Zahl gesucht ist, wählt man als Startwert ein Da es sich um eine einfache Nullstelle einer mind. einmal stetig differenzierbaren Funktion handelt, konvergiert das Verfahren, wenn man den Startwert nur nahe genug bei x* wählt. (Beweis) Hier liegt der Fall sogar noch deutlich besser: Das Verfahren konvergiert für jeden Startwert gegen x*. Beweis:
Auf Grund des Kurvenverlaufs gilt also für k=0,1,.., Somit folgt die Abschätzung: Welche man für ein Abbruchkriterium verwenden kann: Ab wann konvergiert das Verfahren quadratisch? Da es sich um eine einfache Nullstelle einer C²-Funktion handelt, gibt es sogar eine Umgebung von x* in der das Verfahren quadratisch konvergiert. Beispiel n=2 Wegen folgt dann Mit den Ausführungen zur Konvergenz folgt die Bedingung: Das nütz natürlich nicht viel, wenn man keine Ahnung über die Lage von x* hat. Dennoch wollen wir, mit der Kenntnis, einmal den Einzugsbereich explizit für ein paar a bestimmen. |
|||||||
24.08.2007, 19:12 | tigerbine | Auf diesen Beitrag antworten » | |||||
2. Nur einmal stetig diffbare Funktion Nun betrachten wir eine einmal stetig differenzierbare Funktion mit einer einfachen Nullstelle. Nullstellenfunktion f Newton- Iteration Die zur Newton-Iteration gehörige Fixpunktfunktion g lautet: Wie konvergiert die Iteration nun? Dabei liegt zwischen x* und . Aufgrund der Gestalt der Funktion f' folgt hier: Somit konvergiert die Newton-Iteration für alle Startwerte. Nun muss noch ein q bestimmt werden. Dass die Iteration nicht nur linear, sondern superlinear konvergiert wurde ja bereits allgemein im Theorie-Teil gezeigt. Die nächste Frage muss also lauten: Ist die Funktion f Lipschitzstetig? Betrachten wir die Funktion auf dem Intervall [0,5]. Sie ist dort strikt konvex. |
|||||||
26.08.2007, 12:51 | tigerbine | Auf diesen Beitrag antworten » | |||||
3. Newton-Verfahren bei doppelter Nullstelle Die Funktion hat eine doppelte Nullstelle bei . Es gilt: Nun stellt man die Iterationsvorschrift des Newton Verfahrens auf: Es liegt also für x*=0 eine hebbare Definitionslücke vor. Die Rekursion verläuft also für unproblematisch und man kann zur Untersuchung schreiben: Das liefert die folgende Konvergenzuntersuchung. Dabei benutzt man x*=0 Daher weiß man nun, dass das Verfahren mind. linear konvergiert. Dass die Konvergenz aus der Abschätzung folgt, wurde hier gezeigt. Lineare Konvergenzrate und Superlineare Konvergenz Somit liegt keine superlineare und damit auch keine höhere Konvergenordnung (z.B. quadratisch) vor. Es zeigt sich aber die für C²-getroffene Aussage, dass die lineare Konvergenzrate den Wert hat. Zugehörige Fixpunktiteration Für die stetige Fortsetzung gilt: So dass, da die Folge ja konvergiert, wir auch die hier gemachte Aussage verifizieren können. |
|||||||
26.08.2007, 15:02 | tigerbine | Auf diesen Beitrag antworten » | |||||
4. Modifiziertes Newton Verfahren Vergleiche [Workshop - Eindimensionale Nullstellenprobleme 2] Nun wollen wir uns noch einmal an der Funktion f(x) = x² versuchen. Diese besitzt bei x*= 0 eine doppelte (p=2) Nullstelle. Es gilt f'(x) = 2x, f''(x) = 2, f'''(x)=0. Rekursionsvorschrift: Und es gilt die Abschätzung Somit ist es nicht verwunderlich, dass dieses Verfahren bereits im ersten Iterationsschritt (für jeden Startwert ungleich x*) konvergiert. |
|||||||
03.09.2007, 12:30 | tigerbine | Auf diesen Beitrag antworten » | |||||
5. Newton-Verfahren mit kubischer Konvergenz Nach folgendem Satz gilt (siehe [Workshop - Eindimensionale Nullstellenprobleme 2]):
Bislang haben wir als Bestwert nur "lokale quadratische Konvergenz" erhalten. Geht auch noch mehr? Versuchen wir ein Beispiel: Nun wird es unschön. Daher ein paar Platzhalter. somit konvergiert das Verfahren mit der Konvergenzordnung 3. |
|||||||
Anzeige | |||||||
|
|||||||
03.09.2007, 19:24 | tigerbine | Auf diesen Beitrag antworten » | |||||
1. Regula-Falsi vs. Bisektion Nach den Kommentaren im [Workshop - Eindimensionale Nullstellenprobleme 3] sollen hier anhand zweier Beispiele das Konvergenzverhalten von Regula falsi und Bisektion verglichen werden. Das erste Beispiel Die Nullstelle liegt formal bei Als erste grobe Abschätzung kann man treffen, dass sich die Nullstelle im Intervall [0, 15] befindet. Es ist dann: http://www.smileygarden.de/smilie/Sport/12.gif Let's get ready to rumble |
|||||||
03.09.2007, 20:08 | tigerbine | Auf diesen Beitrag antworten » | |||||
a. Kandidat 1: Regula Falsi --------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------------------------------- Das bisherige einmal im Bild: |
|||||||
03.09.2007, 21:29 | tigerbine | Auf diesen Beitrag antworten » | |||||
b. Kandidat 2: Bisektion --------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------------------------------- |
|||||||
03.09.2007, 21:39 | tigerbine | Auf diesen Beitrag antworten » | |||||
c. Zwischenstand nach 3 Schritten Wer liegt nun nach 3 Runden vorne? Bei der Bisektion bleibt als mittel der Genauigkeitsbestimmung nur die Länge des Intervalls. Bei der Regula falsi bekommt man mit noch einen Näherungswert zur Lösung x*. Da man aber nur den Funktionswert kennt, muss zur Genauigkeitsbestimmung herangezogen werden. Regula Falsi Bisektion Somit liegt nach 3 Runden die Bisektion vorne. Nun wissen wir, dass sich beim Bisektionsverfahren die Intervallänge immer halbiert. Kann die Regula falsi noch aufholen? |
|||||||
03.09.2007, 23:52 | tigerbine | Auf diesen Beitrag antworten » | |||||
d. Richtige Stellen Nach wie vielen Iterationen erreichen die beiden Verfahren 1,2,...,10 richtige Stellen? Regula Falsi ... Bisektion Somit führt auch noch bei einer Berechnung bis auch 10 Ziffern Genauigkeit die Bisektion. Damit soll der Wettkampf beendet werdet. Dieses Mal hat also die Bisektion "gewonnen" http://www.smileygarden.de/smilie/Sport/1er.gif |
|||||||
05.09.2007, 00:56 | tigerbine | Auf diesen Beitrag antworten » | |||||
2. Bisektion vs. Sekante vs. Newton Kaum den Titel gewonnen, haben wir 2 neue Herausforderer für das Bisektionsverfahren. Wer hat bei folgender Funktion die Nase vorne: Diese Funktion hat eine einfache Nullstelle im Intervall [1,2] Sieger soll dasjenige Verfahren sein, dass nach 20-Runden die meisten richtigen Ziffern ermittelt hat. |
|||||||
05.09.2007, 02:33 | tigerbine | Auf diesen Beitrag antworten » | |||||
a. Kandidat 1: Bisektion
Macht also über'm Strich 6 Ziffern |
|||||||
05.09.2007, 04:20 | tigerbine | Auf diesen Beitrag antworten » | |||||
b. Kandidat 2: Sekanten - Verfahren
Somit nach 8 Schritten 13 übereinstimmende Ziffern. Somit sehen wie hier nach 9 Schritten das Problem des Verfahrens. Die "Näherung" ist bereits soweit Fortgeschritten, dass es im Nenner zur Auslöschung kommt. |
|||||||
05.09.2007, 14:24 | tigerbine | Auf diesen Beitrag antworten » | |||||
c. Kandidat 3: Newton - Verfahren
Somit nach 7 Schritten 13 übereinstimmende Ziffern. Das Verfahren ist stabil in der Nähe der gesuchten Lösung x*. |
|||||||
05.09.2007, 14:32 | tigerbine | Auf diesen Beitrag antworten » | |||||
d. Ergebnis Somit kommen wir bei dieser Funktion zu folgendem Ranking: http://www.smileygarden.de/smilie/Sport/1er.gif Newton-Verfahren http://www.smileygarden.de/smilie/Sport/2eme.gif Sekanten-Verfahren http://www.smileygarden.de/smilie/Sport/3eme.gif Bisektion |
|||||||
05.09.2007, 15:07 | tigerbine | Auf diesen Beitrag antworten » | |||||
3. Bisektion und Singularität (Polstelle) Es wurde im [Workshop - Eindimensionale Nullstellenprobleme 1] erwähnt, dass die Bisektion auf einem Intvall [a,b] mit f(a)f(b) < 0 für stetiges f aufgrund des Zwischenwertsatzes stetiger Funktion konvergieren muss. Was passiert nun im Falle einer unstetigen Funktion? |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|