Newtonverfahren < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:57 So 25.06.2006 | | Autor: | Bastiane |
| Aufgabe | Wir wollen das Newton-Verfahren zur Berechnung von [mm] x=\bruch{1}{a} [/mm] mit [mm] a\in\IR, a\not=0 [/mm] betrachten, d.h. wir suchen die Nullstelle von [mm] f(x)=\bruch{1}{x}-a.
[/mm]
Beweisen Sie durch vollständige Induktion:
[mm] \epsilon_k=-\bruch{1}{a}\rho^{2^k},\; [/mm] mit [mm] \rho=|ax_0-1|. [/mm]
Welche Bedingung für [mm] \rho [/mm] bzw. [mm] x_0 [/mm] ist hinreichend und notwendig für globale Konvergenz des Iterationsverfahrens? Wie groß ist die Konvergenzrate?
|
Hallo zusammen!
Also obiges ist Aufgabenteil c). a) und b) habe ich schon gelöst, ich hoffe, diese Ergebnisse sind für diesen Teil nicht wichtig. Den Beweis mit Induktion habe ich auch schon gemacht. Nur hänge ich an den beiden Fragen am Ende.
Was mir als erstes einfiel, was auch hier zu der "Fehlerabschätzung" passt, ist:
damit das Ganze konvergiert, muss der Fehler gegen 0 gehen. Also:
[mm] \lim_{k\to\infty}-\bruch{1}{a}|ax_0-1|^{2^k}=0
[/mm]
Damit das gilt, müsste doch [mm] |ax_0-1|<1 [/mm] sein, oder? Und wenn ich das weiter umforme, erhalte ich:
[mm] $x_0<\bruch{2}{a} \vee [/mm] (a>0 [mm] \wedge x_0>0) \vee [/mm] (a<0 [mm] \wedge x_0<0)$
[/mm]
Könnte das stimmen?
Ist es richtig, dass das dann die hinreichende Bedingung ist? Denn wenn das gilt, dann geht der Fehler ja auf jeden Fall gegen 0, und wenn das der Fall ist, dann konvergiert das Verfahren!?!
Was aber ist notwendig für die globale Konvergenz? Da fällt mir irgendwie überhaupt nichts ein. ![[kopfkratz2]](/images/smileys/kopfkratz2.gif "[kopfkratz2]") Oder ergibt meine Rechnung sogar auch noch die notwendige Bedingung?
Und was ist dann mit der Konvergenzrate? Das ist doch nach Definition die Zahl p für die gilt:
[mm] |x_{k+1}-x|
In Teil a) hatte ich gezeigt, dass gilt: [mm] x_{k+1}=x_k+x_k(1-ax_k) [/mm] für k=0,1,.... Das könnte ich hier ja erstmal schon mal einsetzen, allerdings weiß ich dann auch nicht weiter.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
| |
|
Hallo Bastiane ,
Ich weiß es nicht so genau, weil es länger her ist.
Vielleicht hilfts trotzdem.
Die Kernidee des Newton-Verfahrens sieht man, wenn man Newtons Formel wie folgt abwandelt:
[mm] $x_{n+1}=x_n-\frac{f(x_n)}{\color{blue}\left[\frac{f(x_n)-f(x_{nullstelle})}{x_n-x_{nullstelle}}\right]}$
[/mm]
[mm] $x_{n+1}=x_n-\frac{f(x_n)*\left[x_n-x_{nullstelle}\right]}{f(x_n)-0}=x_n-\frac{f(x_n)}{f(x_n)\color{magenta}-0\color{black}}*\left[x_n-x_{nullstelle}\right]=x_{nullstelle}$
[/mm]
Diese Formel liefert Newton also sofort die Nullstelle!
Und zwar in jedem Fall. Blöd bloß, dass man die Nullstelle vorher kennen muss, weil man sonst den Differenzenquotienten nicht aufstellen kann.
Allein deshalb hat Newton nach etwas gesucht, das ungefähr [mm] $\color{blue}\left[\frac{f(x_n)-f(x_{nullstelle})}{x_n-x_{nullstelle}}\right]$
[/mm]
da drängt sich
[mm] $f'(x_{nullstelle}) \color{blue}\approx \left[\frac{f(x_n)-f(x_{nullstelle})}{x_n-x_{nullstelle}}\right]$
[/mm]
auf, das wir aber auch nicht kennen, sowie
[mm] $f'(x_{n}) \approx \color{blue}\left[\frac{f(x_n)-f(x_{nullstelle})}{x_n-x_{nullstelle}}\right]$
[/mm]
das er dann genommen hat:
[mm] $x_{n+1}=x_n-\frac{f(x_n)}{\color{blue}f'(x_n)}$
[/mm]
Wenn du sicherstellst, dass [mm] $f'(x_n)$ [/mm] von dem Differenzenquotienten
nicht zu stark abweicht. Weder für den
Startwert [mm] $x_0$ [/mm] noch für irgendwelche Werte,
die beim Iterieren auftreten, müsste deine Iteration konvergieren.
Leider kann ich dir nicht dabei helfen den Begriff nicht zu stark abweicht mit Inhalt zu füllen.
Das musst du selbst tun (oder andere im Matheraum).
In der Hoffnung, nix falsches geschrieben zu haben (oder dich gelangweilt zu haben)
Gruß Karthagoras
|
|
|
| |
|
Hallo Bastiane,
> Wir wollen das Newton-Verfahren zur Berechnung von
> [mm]x=\bruch{1}{a}[/mm] mit [mm]a\in\IR, a\not=0[/mm] betrachten, d.h. wir
> suchen die Nullstelle von [mm]f(x)=\bruch{1}{x}-a.[/mm]
>
> Beweisen Sie durch vollständige Induktion:
> [mm]\epsilon_k=-\bruch{1}{a}\rho^{2^k},\;[/mm] mit [mm]\rho=|ax_0-1|.[/mm]
> Welche Bedingung für [mm]\rho[/mm] bzw. [mm]x_0[/mm] ist hinreichend und
> notwendig für globale Konvergenz des Iterationsverfahrens?
> Wie groß ist die Konvergenzrate?
>
> Hallo zusammen!
>
> Also obiges ist Aufgabenteil c). a) und b) habe ich schon
> gelöst, ich hoffe, diese Ergebnisse sind für diesen Teil
> nicht wichtig. Den Beweis mit Induktion habe ich auch schon
> gemacht. Nur hänge ich an den beiden Fragen am Ende.
> Was mir als erstes einfiel, was auch hier zu der
> "Fehlerabschätzung" passt, ist:
>
> damit das Ganze konvergiert, muss der Fehler gegen 0 gehen.
> Also:
>
> [mm]\lim_{k\to\infty}-\bruch{1}{a}|ax_0-1|^{2^k}=0[/mm]
>
> Damit das gilt, müsste doch [mm]|ax_0-1|<1[/mm] sein, oder? Und wenn
> ich das weiter umforme, erhalte ich:
>
Hier erhalte ich [mm] \frac{2}{a}> x_0\geq \frac{1}{a} [/mm] (insbes. a>0) (das ist der Fall [mm] 0\leq ax_0-1 [/mm] <1)
oder -1 < [mm] ax_0-1 \leq [/mm] 0 d.h. 0< [mm] ax_0\leq [/mm] 1
und das ergibt
- im Falle a>0 die Bedingung [mm] 0
- im Falle a<0 die Bedingung 0> [mm] x_0 [/mm] > [mm] \frac{1}{a}
[/mm]
Und es gilt fuer Konvergenz ''genau dann wenn'', denn das [mm] \epsilon_k [/mm] ist ja der genaue Fehler.
Lieben Gruss,
Mathias
> [mm]x_0<\bruch{2}{a} \vee (a>0 \wedge x_0>0) \vee (a<0 \wedge x_0<0)[/mm]
>
> Könnte das stimmen?
>
> Ist es richtig, dass das dann die hinreichende Bedingung
> ist? Denn wenn das gilt, dann geht der Fehler ja auf jeden
> Fall gegen 0, und wenn das der Fall ist, dann konvergiert
> das Verfahren!?!
> Was aber ist notwendig für die globale Konvergenz? Da
> fällt mir irgendwie überhaupt nichts ein. Oder
> ergibt meine Rechnung sogar auch noch die notwendige
> Bedingung?
>
> Und was ist dann mit der Konvergenzrate? Das ist doch nach
> Definition die Zahl p für die gilt:
>
> [mm]|x_{k+1}-x|
> konvergiert. Oder nicht?
>
> In Teil a) hatte ich gezeigt, dass gilt:
> [mm]x_{k+1}=x_k+x_k(1-ax_k)[/mm] für k=0,1,.... Das könnte ich hier
> ja erstmal schon mal einsetzen, allerdings weiß ich dann
> auch nicht weiter.
>
> Viele Grüße
> Bastiane
>
>
|
|
|
|
