Newton-Verfahren < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 13:33 Do 23.12.2010 | | Autor: | dennis2 |
| Aufgabe | Konvergenz des Newton-Verfahrens
Für [mm] \alpha >0 [/mm] sei
[mm] f(x)=x^{\alpha} [/mm], wenn [mm] x\ge 0 [/mm]
[mm] f(x)=-|x|^{\alpha} [/mm], wenn [mm] x<0 [/mm].
Sei [mm] x_0>0 [/mm] Startwert des Newton-Verfahrens zur Bestimmung der Nullstelle [mm] \overline{x}=0 [/mm] von f.
a) Für welche [mm] \alpha >0 [/mm] konvergiert das Newton-Verfahren?
b) Zeigen Sie, dass das Newton-Verfahren für [mm] \alpha > \bruch{1}{2}, \alpha \not= 1 [/mm], nur linear konvergiert. |
Hallo, ich habe ein paar Fragen zu dieser Aufgabe.
Zu a)
Zunächst schreibe ich das auf, was ich mir hierbei denke.
Fall 1:
[mm] f(x)=x^{\alpha}
[/mm]
[mm] f'(x)=\alpha x^{\alpha -1}
[/mm]
[mm] x^{k+1}=x^k-\underbrace{\bruch{x_k^{\alpha}}{\alpha x_k^{\alpha -1}}}_{< x_k}
[/mm]
Und dann habe ich mir angeguckt:
[mm] \bruch{||x^{k+1}-\overline{x}||}{||x^k-\overline{x}||}=\bruch{||x^k-\bruch{x_k^{\alpha}}{\alpha x_k^{\alpha -1}}||}{||x^k||}\le [/mm] c für [mm] c\in [/mm] (0,1) [mm] \forall [/mm] k=0,1,2,...
Aber jetzt frage ich mich, wenn jetzt im Nenner stehen würde: [mm] ||x^k||^p [/mm] mit p>1, also eine höhere Konvergenzordnung als 1, und dann würde man ein [mm] x^k<1 [/mm] nehmen, dann wäre das nicht <c.
Es ist hier ja aber nur nach Konvergenz gefragt und linear scheint es doch für alle [mm] \alpha [/mm] >0 zu konvergieren.
Die Frage (b) deutet ja aber an, dass man zwischen verschiedenen Konvergenzordnungen unterscheiden soll und dass wohl für alle [mm] \alpha \le [/mm] 0,5 diese Bedingung auch für bestimmte p>1 erfüllt ist.
Analog für den 2. Fall, dass [mm] f(x)=-|x|^{\alpha}
[/mm]
Denke ich richtig?
Oder sollte man einen anderen Ansatz wählen als obige Formel?
(b) lasse ich nochmal offen, ich denke, dass ich erst (a) klären muss.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:00 Do 23.12.2010 | | Autor: | dennis2 |
Ich habe mir gerade das Skript nochmals angesehen und für den Fall, dass p>1 ist, steht da nur, dass es eine Konstante c>0 geben muss, sodass:
[mm] \bruch{||x^{k+1}-\overline{x}||}{||x^k-\overline{x}||^p}\le [/mm] c [mm] \forall [/mm] k=0,1,2...
Wenn ich das richtig verstehe, muss c hier nicht mehr aus dem offenen Intervall (0,1) stammen, jedenfalls ist das nicht genannt.
Erklärt das, warum
[mm] \bruch{||x^k-\bruch{x_k^{\alpha}}{\alpha x_k^{\alpha -1}}||}{||x^k||^p}\le [/mm] c
immer gilt?... ![[verwirrt]](/images/smileys/verwirrt.gif "[verwirrt]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:50 Do 23.12.2010 | | Autor: | abakus |
> Ich habe mir gerade das Skript nochmals angesehen und für
> den Fall, dass p>1 ist, steht da nur, dass es eine
> Konstante c>0 geben muss, sodass:
>
> [mm]\bruch{||x^{k+1}-\overline{x}||}{||x^k-\overline{x}||^p}\le[/mm]
> c [mm]\forall[/mm] k=0,1,2...
>
> Wenn ich das richtig verstehe, muss c hier nicht mehr aus
> dem offenen Intervall (0,1) stammen, jedenfalls ist das
> nicht genannt.
>
> Erklärt das, warum
> [mm]\bruch{||x^k-\bruch{x_k^{\alpha}}{\alpha x_k^{\alpha -1}}||}{||x^k||^p}\le[/mm]
> c
>
> immer gilt?...
Keine Ahnung. Ich habe es mit Geogebra mal durchgespielt.
Für [mm] 0<\alpha<0,5 [/mm] divergiert das Verfahren. Für x=0,5 springt es zwischen [mm] x_0 [/mm] und [mm] -x_0 [/mm] hin und her.
Zwischen 0,5 und 1 konvergiert es mit alternierenden Werten, ab 1 konvergiert es nichtalternierend.
Gruß Abakus
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 18:19 Do 23.12.2010 | | Autor: | dennis2 |
> Keine Ahnung. Ich habe es mit Geogebra mal durchgespielt.
> Für [mm]0<\alpha<0,5[/mm] divergiert das Verfahren. Für x=0,5
Meinst Du hier [mm] \alpha [/mm] =0,5?
> springt es zwischen [mm]x_0[/mm] und [mm]-x_0[/mm] hin und her.
> Zwischen 0,5 und 1 konvergiert es mit alternierenden
> Werten, ab 1 konvergiert es nichtalternierend.
> Gruß Abakus
>
>
Ja, ich glaube, das erhält man so:
Kürzt man in $ [mm] \bruch{||x^k-\bruch{x_k^{\alpha}}{\alpha x_k^{\alpha -1}}||}{||x^k||}\le [/mm] c $ den Doppelbruch weg, dann bleibt übrig:
[mm] ||1-\bruch{1}{\alpha}|| [/mm] und das ist ja nur < 1 wenn [mm] \alpha [/mm] nicht kleiner als 0,5 ist.
Aber das ist doch jetzt nur für p=1 der Fall, oder?
Denn für p>1 bliebe ja im Nenner [mm] ||x_{k}||^{p-1} [/mm] stehen.
Oder sehe ich das falsch?
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 20:40 Do 23.12.2010 | | Autor: | dennis2 |
| Aufgabe | Eine Verständnisfrage zur Konvergenzgeschwindigkeit von Iterationsverfahren:
Bei Wikepedia und in meinem Skript lese ich, dass für lineare Konvergenz (d.h. p=1) gelten muss:
[mm] \bruch{||x_{k+1}-\overline{x}||}{||x_k-\overline{x}||}\le [/mm] c, wobei [mm] \overline{x} [/mm] die zu findende Nullstelle ist und für c gelten soll:
0<c<1.
Darunter finde ich dann die allgemeinere Formel, die für für p>1 gelten soll:
[mm] \bruch{||x_{k+1}-\overline{x}||}{||x_k-\overline{x}||^p}\le [/mm] c.
Und was mich nun verwirrt ist, dass dort nur noch steht, dass für c gelten soll:
c>0.
Muss denn c hier nicht mehr zwischen 0 und 1 liegen?
Das macht ja eigentlich keinen Sinn, denn man muss ja nur p=1 setzen und schon ergibt sich wieder die obere Formel für lineare Konvergenz. |
Das ist bestimmt ein doofes Missverständnis.
Aber vielleicht klärt mich jemand auf?
Wäre sehr nett.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:35 Do 23.12.2010 | | Autor: | nooschi |
also vielleicht jetzt etwas eine dööfliche Antwort von mir, deshalb nur als Mitteilung, dass die anderen sich nicht darin gehindert sehen auch zu antworten :D
Ich kann mich erinnern, dass bei uns die Definitionen auch so aussahen, sie machen meiner Meinung nach auch durchaus Sinn so.
Wenn du bei der linearen Konvergenz ein c hast, das nicht kleiner $1$ ist, hast du nichts gewonnen, du weisst eigentlich nix über die konvergenzgeschwindigkeit wenn du zB $c=1$ hast, weisst du erst, dass der Fehler nie grösser wird, aber für eine vernünftige Abschätzung wäre das nicht brauchbar, nur von der Ungleichung her, siehst du nämlich nicht, dass die Folge überhaupt konvergiert)
und jetzt Konvergenz höherer Ordnung:
Wenn du jetzt $ [mm] \bruch{||x_{k+1}-\overline{x}||}{||x_k-\overline{x}||^p}\le [/mm] c$ hast (dabei ist $p>1$ !! nie $p=1$)
d.h.: $ [mm] ||x_{k+1}-\overline{x}||\le c\cdot ||x_k-\overline{x}||^p$
[/mm]
da die Folge konvergiert, existiert ein $K$, s.d. [mm] $||x_k-\overline{x}||<1$ $\forall [/mm] k>K$
und jetzt ist eben der Punkt, dass $c$ nicht so eine grosse Rolle spielt, man kann jetzt schon durch die Potenz $p$ eine gewisse Konverenzgeschwindigkeit feststellen
(also irgendwie so: $ [mm] ||x_{k+1}-\overline{x}||\le c\cdot ||x_k-\overline{x}||^p \Rightarrow ||x_{k+2}-\overline{x}||\le c\cdot ||x_{k+1}-\overline{x}||^p\le c\cdot ||x_k-\overline{x}||^{2p}$ [/mm] und induktiv hast du dann irgendwie sowas [mm] $||x_k-\overline{x}||^{n\cdot p}$ [/mm] artiges, was dir dann eben die Konvergenzgeschwindigkeit anzeigt...)
ich hoffe man versteht ungefähr was ich sagen will :D
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:20 Sa 25.12.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:20 Sa 25.12.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:43 Sa 25.12.2010 | | Autor: | dennis2 |
Zu a)
Das Newton-Verfahren konvergiert [mm] \forall \alpha [/mm] > [mm] \bruch{1}{2}. [/mm]
Zu b)
Der Quotient unter a) erweist sich als konstant, nämlich als [mm] 1-\bruch{1}{\alpha}. [/mm] Darum strebt der Quotient, wenn im Nenner [mm] ||x_k||^p, [/mm] p>1, steht und es sich um eine Nullfolge handelt, der Ausdruck über alle Grenzen, d.h. er konvergiert nicht.
Darum liegt nur lineare Konvergenz vor.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:20 Sa 25.12.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
