Konvergenzordnung < Nichtlineare Gleich. < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 19:51 Mo 14.07.2014 | | Autor: | Laura87 |
Hallo,
ich habe eine Verstaendnisfrage. Ich bin letztes mal in der Numerik Prüfung durchgefallen und wurde hier unter anderem zu Bisektion- und Newtonverfahren geprüft. Der Prof. Wollte am Ende wissen, welches schneller konvergiert. Ich habe gesagt, dass das Bisektionsverfahren linear und das Newtonverfahren quadratisch konvergiert. Das hat ihm natürlıch nicht ausgereicht. Da wollte er wissen, was das genau bedeutet.
Jetzt habe ich mir mal die Definition der Konvergenzordnung angeguckt:
[mm] \parallel x^{k+1}-x^*\parallel \le [/mm] c* [mm] \parallel x^{k}-x^*\parallel^p
[/mm]
für c [mm] \in \IR, [/mm] p= konvergenzordnung c und konvergenzfaktor
Soo jetzt möchte ich versuchen, anhand eines Beispiels zu erklaeren, was ich verstanden habe.
....je größer p umso schneller konvergiert das Verfahren.
Nehmen wir an [mm] x_n [/mm] sei eine von einem quadratisch konvergenten Verfahren erzeugte Folge und [mm] y_n [/mm] eine von einem linear konvergenten und beide konvegieren gegen die Nullstelle x*.
Nehmen wir an, wir haben ein [mm] x_n [/mm] und ein [mm] y_n [/mm] berechnet mit
[mm] |y_n-x*|\le [/mm] 0.1 und [mm] |x_n-x^*|\le [/mm] 0.1
Für den naechsten Schritt gilt dann,
[mm] |y_n-x*|\le [/mm] c* 0.1 und [mm] |x_n-x^*|\le [/mm] c* 0.01
d.h. bei [mm] x_n [/mm] sinkt der Fehler quadratisch oder anders formuliert: die Anzahl der gültigen Ziffern verdoppelt sich.
Bei linear konvergenten Verfahren bleibt die Anzahl der gültigen Ziffern in jedem Schritt gleich. Die Anzahl der gültigen Ziffern.....(hier kann ich das irgenwie nicht formulieren).
Kann ich das so sagen? Also habe ich das richtig verstanden 
Ich verstehe noch nicht so ganz, was das mit der Konstanten c sein soll. Bei dem Bisektionsverfahren ist es ja 1/2.
Weil das Intervall in jedem Iterationsschritt halbiert wird?
Aber was ist es beim Newtonverfahren?
Das ist jetzt alles, was ich im Bezug zu Konvergenz gefunden habe. Gibt es noch andere Hinweise?
Ich bin für jeden Tipp Dankbar.
LG Laura
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:02 Di 15.07.2014 | | Autor: | melisa1 |
Hallo,
die Frage wurde zwar noch nicht beantwortet, aber vielleicht kann Laura meine Frage beantworten.
Bedeutet die quadratische Konvergenz, dass das Newtonverfahren doppelt so schnell konvergiert, wie das Bisektionsverfahren?
Gruß Melisa
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:43 Mi 16.07.2014 | | Autor: | Laura87 |
Hallo Melisa,
also ganz sicher bin ich mir nicht, aber soweit ich es verstanden habe, bedeutet lineare konvergenz, dass sich der Fehler in jedem Schritt in etwa halbiert. Quadratische Konvergenz bedeutet, dass der Fehler eben quadratisch sinkt.
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:14 Mi 16.07.2014 | | Autor: | Marcel |
Hallo Laura,
> Hallo Melisa,
>
>
> also ganz sicher bin ich mir nicht, aber soweit ich es
> verstanden habe, bedeutet lineare konvergenz, dass sich der
> Fehler in jedem Schritt in etwa halbiert.
ne, man könnte sagen: Im "Worst-Case" wird der Fehler immer linear sinken.
Wenn $c=7/8$ ist, dann [mm] $7/8\,$elt [/mm] sich der "Fehler" immer (anstatt "Fehler"
kann man auch ein anderes Wort benutzen. Ein "Fehler" ist in dem Sinne gemeint,
dass man anstatt des korrekten Wertes [mm] $x\,$ [/mm] halt [mm] $x^k$ [/mm] benutzt!) Wobei
das immer "in Bezug auf den vorangegangenen Fehler" gemeint ist.
> Quadratische
> Konvergenz bedeutet, dass der Fehler eben quadratisch
> sinkt.
Eben. Und von der Bedeutung her analog zu oben. Ich finde eigentlich,
dass gerade diese Ungleichung
[mm] $\|x^{k+1}-x\|$ $\le$ $c*\|x^{k}-x\|^p$
[/mm]
eigentlich das wichtigste beinhaltet. Wobei wir ein [mm] $k\,$ [/mm] mit
[mm] $\|x^k-x\| \le \sqrt[p-1]{1/c}$
[/mm]
gefunden haben sollten - den Grund findest Du in meiner anderen Antwort.
In
[mm] $\|x^{k+1}-x\|$ $\le$ $c*\|x^{k}-x\|^p$
[/mm]
kannst Du auch was anderes sehen (sofern nicht schon [mm] $\|x^k-x\|\not=0$)
[/mm]
[mm] $\frac{\|x^{k+1}-x\|}{\|x^{k}-x\|}$ $\le$ $c*\|x^{k}-x\|^{p-1}$
[/mm]
Links steht das Verhältnis des "neuen Fehlers zum alten Fehler". Wenn
dieses $< [mm] 1\,$ [/mm] ist, werden wir "besser". Auch so kann man sich die Sinnhaftigkeit
der Forderung
[mm] $c*\|x^{k}-x\|^{p-1}$ $<\,$ $1\,$
[/mm]
klarmachen!
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:48 Mi 16.07.2014 | | Autor: | Marcel |
Hallo,
> Hallo,
>
> die Frage wurde zwar noch nicht beantwortet, aber
> vielleicht kann Laura meine Frage beantworten.
>
> Bedeutet die quadratische Konvergenz, dass das
> Newtonverfahren doppelt so schnell konvergiert, wie das
> Bisektionsverfahren?
wie kommst Du darauf? Da steht doch sowas (ich zitiere):
> $ [mm] \parallel x^{k+1}-x^\cdot{}\parallel \le [/mm] $ c* $ [mm] \parallel x^{k}-x^\cdot{}\parallel^p [/mm] $
> für c $ [mm] \in \IR, [/mm] $ p= konvergenzordnung c und konvergenzfaktor
(wobei man o.E. auch $c > [mm] 0\,$ [/mm] annehmen kann).
Warum ist dann eine höhere Konvergenzordnung besser? Naja, für $0 < x < 1$ ist
[mm] $x^p \le x^q$
[/mm]
für $p,q [mm] \in \IN$ [/mm] mit $p [mm] \ge q\,.$ [/mm] Die "Konvergenzgüte" ist also größer - das [mm] $c\,$
[/mm]
ist bei dieser "Klassifizierung" eigentlich relativ unwichtig - wenngleich auch
nicht ganz unwichtig. Es sollte halt [mm] $c*\|x^k-x\|^p [/mm] < 1$ irgendwann sein. Und es
gibt eine weitere Forderung, wie ich Dir gleich zeigen werde:
[mm] $c*\|x^k-x\|^{p-1} [/mm] < [mm] 1\,.$
[/mm]
Warum?
Nehmen wir mal [mm] $c=0.5\,$ [/mm] und [mm] $p=1\,$ [/mm] (bei [mm] $p=1\,$ [/mm] ist es wohl sinnvoll, auch
$c < [mm] 1\,$ [/mm] zu fordern - klar, oder?).
Die Abschätzung ist zwar nur grob, aber prinzipiell wüßtest Du hier:
Der Abstand von [mm] $x^k$ [/mm] zum Grenzwert [mm] $x\,$ [/mm] wird sich - im schlechtesten
Fall - im Wesentlichen "schrittweise" halbieren. D.h.
Wenn [mm] $x^5$ [/mm] zu [mm] $x\,$ [/mm] den Abstand $0.8$ hat:
Dann hat [mm] $x^6$ [/mm] zu [mm] $x\,$ [/mm] einen Abstand [mm] $\le [/mm] 0.4$.
Wenn [mm] $x^6$ [/mm] jetzt zu [mm] $x\,$ [/mm] den Abstand $0.4$ hat:
Dann hat [mm] $x^7$ [/mm] zu [mm] $x\,$ [/mm] einen Abstand [mm] $\le [/mm] 0.2$.
Wenn [mm] $x^7$ [/mm] jetzt zu [mm] $x\,$ [/mm] den Abstand $0.2$ hat:
Dann hat [mm] $x^7$ [/mm] zu [mm] $x\,$ [/mm] einen Abstand [mm] $\le [/mm] 0.1$.
etc. pp.
Nehmen wir jetzt mal an, es wäre [mm] $c=10\,$ [/mm] und [mm] $p=4\,:$
[/mm]
Wenn [mm] $x^5$ [/mm] zu [mm] $x\,$ [/mm] den Abstand $0.8$ hat:
Dann hat [mm] $x^6$ [/mm] zu [mm] $x\,$ [/mm] einen Abstand [mm] $\le 10*0.8^4=4.096$. [/mm]
Das wäre jetzt nicht gut für weitere Überlegungen, denn $4,... [mm] \ge [/mm] 1.$
Nehmen wir aber mal an, es wäre [mm] $c=1.5\,$ [/mm] und [mm] $p=4\,:$
[/mm]
Wenn [mm] $x^5$ [/mm] zu [mm] $x\,$ [/mm] den Abstand $0.8$ hat:
Dann hat [mm] $x^6$ [/mm] zu [mm] $x\,$ [/mm] einen Abstand [mm] $\le 1.5*0.8^4=0.6144$. [/mm]
Das sieht schlechter aus wie bei [mm] $c=1/2\,$ [/mm] und [mm] $p=1\,.$ [/mm] Aber machen wir mal
weiter:
Wenn [mm] $x^6$ [/mm] zu [mm] $x\,$ [/mm] den Abstand $0.6144$ hat:
Dann hat [mm] $x^7$ [/mm] zu [mm] $x\,$ [/mm] einen Abstand [mm] $\le 1.5*0.6144^4=0.2137...$
[/mm]
Im nächsten Schritt würden wir konstatieren, dass
[mm] $x^8$ [/mm] zu [mm] $x\,$ [/mm] einen Abstand [mm] $\le [/mm] 0.00313...$
hat, während wir bei [mm] $c=1/2\,$ [/mm] und $p=1$ nur
[mm] $x^8$ [/mm] zu [mm] $x\,$ [/mm] hat Abstand [mm] $\le [/mm] 0.05$
wüßten.
Du siehst hier also: "Ab einem gewissen Punkt" werden bei höherer
Konvergenzordnung die [mm] $x^k$ [/mm] quasi "stärker" an den Grenzwert [mm] $x\,$ [/mm] gedrückt.
Das [mm] $c\,$ [/mm] hat dabei einen gewissen Einfluß, "wann" diese "Anziehung"
stattfinden kann:
Wegen
[mm] $\|x^{k+1}-x\| \le c*\|x^k-x\|^p$
[/mm]
wäre es doch, um
[mm] $\|x^{k+1}-x^k\| [/mm] < [mm] \|x^{k}-x\|$
[/mm]
zu erreichen, schön, wenn schon
[mm] $c*\|x^k-x\|^p$ $\le$ $\|x^k-x\|$
[/mm]
wäre. (Klar, oder? Wenn $a [mm] \le [/mm] b$ ist und man $a < c$ haben will, dann ist es
gut, wenn man $b < [mm] c\,$ [/mm] erzwingen kann. Denn dann hat man wegen
$a [mm] \le [/mm] b < c$
auch $a < [mm] c\,$ [/mm] erreicht!)
Ist
[mm] $d_k:=\|x^k-x\|$
[/mm]
bekannt, so sollte
[mm] $c*\|x^k-x\|^p [/mm] < [mm] d_k\,,$
[/mm]
also
[mm] $c*{d_k}^{p-1} [/mm] < 1$
bzw.
$c < [mm] {d_k}^{1-p}$
[/mm]
sein. Für [mm] $p=4\,$ [/mm] und [mm] $d_k=0.8$ [/mm] wäre es also gut, wenn wir [mm] $c\,$ [/mm] mit
($0 <$) $c < [mm] (0.8)^{-3}=1.95...$
[/mm]
sein, um das "schnellere Annähern der [mm] $x^k$ [/mm] an [mm] $x\,$ [/mm] ersichten zu können."
Umgekehrt:
Ist $c > [mm] 0\,$ [/mm] bekannt, dann
[mm] ${d_k}^{p-1} [/mm] < 1/c$
[mm] $\iff$
[/mm]
[mm] $d_k$ [/mm] $<$ [mm] $\sqrt[p-1]{1/c}\,.$
[/mm]
Damit die Abschätzung also (insbesondere im Worst-Case) "gewinnbringend"
für das "Annäherungsverhalten" der [mm] $x^k$ [/mm] an den Grenzwert [mm] $x\,$ [/mm] wird:
Im Falle $p=4$ und $c=1.5$ sollte irgendwann
[mm] $d_k$ $\le$ $\sqrt[3]{5/4}=1.077...$
[/mm]
sein. Kein Wunder, dass wir für [mm] $d_5=0.8$ [/mm] hier schon etwas sehen konnten.
Für [mm] $p=4\,$ [/mm] und [mm] $c=10\,$:
[/mm]
[mm] $d_k$ $\le$ $\sqrt[3]{1/10}=0.464...$
[/mm]
Kein Wunder, dass wir mit [mm] $d_5=0.8 [/mm] > [mm] \sqrt[3]{1/10}$ [/mm] hier nichts sehen konnten.
P.S. Ansonsten siehe auch
![[]](/images/popup.gif) http://de.wikipedia.org/wiki/Konvergenzgeschwindigkeit
P.P.S. Grobgesagt:
Schau' Dir mal die Graphen von
$x [mm] \mapsto x^p$ [/mm] ($p=1,2,3,...$) für $x [mm] \in [/mm] [0,1)$
an. Was für ein Verhalten beobachtet man "nahe bei $x=0$", wenn man den
Graphen einer Funktion
$x [mm] \mapsto x^{p_1}$
[/mm]
mit dem einer Funktion
$x [mm] \maspto x^{p_2}$
[/mm]
vergleicht, wenn [mm] $p_1 [/mm] < [mm] p_2$?
[/mm]
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:40 Mi 16.07.2014 | | Autor: | Laura87 |
Hallo,
entschuldigt bitte, dass ich nochmal schreibe, aber ich bin immer noch an einer Antwort interessiert und weiß nicht, wie man die Zeit verlängert.
Bitte um Verständnis
LG
Laura
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:20 Fr 18.07.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
