www.matheraum.de
Das Matheforum.
Das Matheforum des MatheRaum.

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenNichtlineare GleichungenKonvergenzordnung
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Nichtlineare Gleichungen" - Konvergenzordnung
Konvergenzordnung < Nichtlineare Gleich. < Numerik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Nichtlineare Gleichungen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Konvergenzordnung: Frage (überfällig)
Status: (Frage) überfällig Status 
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

        
Bezug
Konvergenzordnung: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

Bezug
                
Bezug
Konvergenzordnung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                        
Bezug
Konvergenzordnung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
                
Bezug
Konvergenzordnung: Antwort
Status: (Antwort) fertig Status 
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

     []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

Bezug
        
Bezug
Konvergenzordnung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
        
Bezug
Konvergenzordnung: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:20 Fr 18.07.2014
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Nichtlineare Gleichungen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheforum.net
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]