konvergiert Iterationsverf.? < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:39 Mi 18.10.2006 | | Autor: | Riley |
| Aufgabe | | Es seien die nxn Matrizen A, C gegeben und es gelte [mm] \rho(I_n-AC)<1, [/mm] wobei [mm] I_n [/mm] die Einheitsmatrix bezeichnet. Zeigen Sie, dass das Iterationsverfahren [mm] X_{k+1} [/mm] = [mm] X_k (I_n-AC)+C [/mm] für beliebige Startmatrizen [mm] X_0 [/mm] gegen [mm] A^{-1} [/mm] konvergiert. |
Hallo!
Hab einige Fragen zu dieser Aufgabe!
und zwar haben wir das mit der Picard-iteration in der VL gemacht:
[mm] x^{k+1} [/mm] = (I- [mm] \omegaA)x^k [/mm] + [mm] \omega [/mm] b , dieses Verfahren konvergiert gegen eine Lösung, wenn [mm] \rho(I-\omega [/mm] A) < 1 ist.
aber jetzt ist das in dieser Aufgabe ja mit Matrizen? ich hab mal [mm] A^{-1} [/mm] für [mm] X_k [/mm] eingesetzt:
[mm] X_{k+1} [/mm] = [mm] A^{-1} (I_N-AC)+C= A^{-1} [/mm] - C + C = [mm] A^{-1} [/mm] ... aber damit hab ich ja nichts gezeigt...
habt ihr eine hilfe für mich, wie ich da am besten rangehen sollte...??
viele grüße
riley
|
|
| |
|
Hallo Riley,
> aber jetzt ist das in dieser Aufgabe ja mit Matrizen? ich
> hab mal [mm]A^{-1}[/mm] für [mm]X_k[/mm] eingesetzt:
> [mm]X_{k+1}[/mm] = [mm]A^{-1} (I_N-AC)+C= A^{-1}[/mm] - C + C = [mm]A^{-1}[/mm] ...
> aber damit hab ich ja nichts gezeigt...
Doch wenn es einen Fixpunkt gibt dann ist das [mm] A^{-1} [/mm] Ansonsten wäre interessant wie ihr das für die "Vektoren" gezeigt habt. Vllt. ist die Aussage "Es existiert genau ein Fixpunkt" ja übertragbar.
viele Grüße
matheamduenn
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:14 Mi 18.10.2006 | | Autor: | Riley |
Hi Mathemaduenn!
ohja, das ist cool !! ich hab das nun versucht analog zu machen:
H:= [mm] I_n [/mm] - AC.
Iterationsverfahren: [mm] X_{k+1} [/mm] = [mm] X_k (I_n-AC) [/mm] + C = [mm] X_k [/mm] H + C, dann gilt [mm] X_k= X_{k-1} (I_n-AC) [/mm] + C = [mm] X_{k-1} [/mm] H +C.
und wenn es einen Fixpunkt gibt, dann muss es ja wie du geschrieben hast [mm] A^{-1} [/mm] sein, also [mm] A^{-1} [/mm] = H [mm] A^{-1} [/mm] + C. -
ok, als vss ist gegeben, dass [mm] \rho(H) [/mm] < 1.dann ex. nach einem satz aus unserem skript eine induzierte Norm (operatornorm) mit [mm] \|H\|< [/mm] 1, da spektralradius ja inf aller induz normen ist.
betrachte nun:
[mm] \| X_k [/mm] - [mm] A^{-1} \| [/mm] = [mm] \| X_{k-1} [/mm] H + C - ( H [mm] A^{-1} [/mm] + [mm] C)\|
[/mm]
= [mm] \| X_{k-1} [/mm] H + C - [mm] A^{-1} [/mm] H - [mm] C\| [/mm] = [mm] \| X_{k-1} [/mm] H - [mm] A^{-1} [/mm] H [mm] \|
[/mm]
= [mm] \| [/mm] ( [mm] X_{k-1} [/mm] - [mm] A^{-1} [/mm] H [mm] \|
[/mm]
[mm] \leq \|X_{k-1} [/mm] - [mm] A^{-1}) \| \|H\|(Submultiplikativität)
[/mm]
= [mm] \|X_{k-2} [/mm] H + C - [mm] A^{-1} [/mm] H - C [mm] \| \|H\|
[/mm]
= [mm] \| (X_{k-2} [/mm] - [mm] A^{-1}) [/mm] H [mm] \| \|H\|
[/mm]
[mm] \leq \| X_{k-2} [/mm] - [mm] A^{-1} \| \|H\|^2 [/mm] (Submulti.)
.... jetzt kann man das ja immer so weitermachen bis k-k=0:
[mm] \leq \|X_0 [/mm] - [mm] A^{-1} \| \|H\|^k
[/mm]
und da [mm] \|H\| [/mm] < 1, gilt [mm] \|H\| [/mm] -> 0 für k -> [mm] \infty.
[/mm]
damit folgt:
[mm] \limes_{k\rightarrow\infty} \|X_k [/mm] - [mm] A^{-1}\| \leq [/mm] 0.
wegen einer der Normeigenschaften gilt aber [mm] \|X_k [/mm] - [mm] A^{-1}\| \ge [/mm] 0
[mm] \Rightarrow \|X_k [/mm] - [mm] A^{-1} \| [/mm] = 0
[mm] \Rightarrow X_k [/mm] - > [mm] A^{-1} [/mm] für k -> [mm] \infty.
[/mm]
hmm... was sagst du dazu ? hab ich damit die behauptung gezeigt?
viele grüße
riley
|
|
|
| |
|
Hallo Riley,
> ohja, das ist cool !! ich hab das nun versucht analog zu
> machen:
> H:= [mm]I_n[/mm] - AC.
> Iterationsverfahren: [mm]X_{k+1}[/mm] = [mm]X_k (I_n-AC)[/mm] + C = [mm]X_k[/mm] H +
> C, dann gilt [mm]X_k= X_{k-1} (I_n-AC)[/mm] + C = [mm]X_{k-1}[/mm] H +C.
>
> und wenn es einen Fixpunkt gibt, dann muss es ja wie du
> geschrieben hast [mm]A^{-1}[/mm] sein, also [mm]A^{-1}[/mm] = H [mm]A^{-1}[/mm] + C. -
Leider war ich hier etwas ungenau.
Wenn es einen eindeutigen (oder nur einen) Fixpunkt gibt ist das [mm] A^{-1}.
[/mm]
> ok, als vss ist gegeben, dass [mm]\rho(H)[/mm] < 1.dann ex. nach
> einem satz aus unserem skript eine induzierte Norm
> (operatornorm) mit [mm]\|H\|<[/mm] 1, da spektralradius ja inf aller
> induz normen ist.
> betrachte nun:
> [mm]\| X_k[/mm] - [mm]A^{-1} \|[/mm] = [mm]\| X_{k-1}[/mm] H + C - ( H [mm]A^{-1}[/mm] +
> [mm]C)\|[/mm]
>
> = [mm]\| X_{k-1}[/mm] H + C - [mm]A^{-1}[/mm] H - [mm]C\|[/mm] = [mm]\| X_{k-1}[/mm] H -
> [mm]A^{-1}[/mm] H [mm]\|[/mm]
>
> = [mm]\|[/mm] ( [mm]X_{k-1}[/mm] - [mm]A^{-1}[/mm] H [mm]\|[/mm]
>
> [mm]\leq \|X_{k-1}[/mm] - [mm]A^{-1}) \| \|H\|(Submultiplikativität)[/mm]
>
> = [mm]\|X_{k-2}[/mm] H + C - [mm]A^{-1}[/mm] H - C [mm]\| \|H\|[/mm]
>
> = [mm]\| (X_{k-2}[/mm] - [mm]A^{-1})[/mm] H [mm]\| \|H\|[/mm]
>
> [mm]\leq \| X_{k-2}[/mm] - [mm]A^{-1} \| \|H\|^2[/mm] (Submulti.)
>
> .... jetzt kann man das ja immer so weitermachen bis
> k-k=0:
>
> [mm]\leq \|X_0[/mm] - [mm]A^{-1} \| \|H\|^k[/mm]
>
> und da [mm]\|H\|[/mm] < 1, gilt [mm]\|H\|[/mm] -> 0 für k -> [mm]\infty.[/mm]
>
> damit folgt:
>
> [mm]\limes_{k\rightarrow\infty} \|X_k[/mm] - [mm]A^{-1}\| \leq[/mm] 0.
>
> wegen einer der Normeigenschaften gilt aber [mm]\|X_k[/mm] -
> [mm]A^{-1}\| \ge[/mm] 0
>
> [mm]\Rightarrow \|X_k[/mm] - [mm]A^{-1} \|[/mm] = 0
>
> [mm]\Rightarrow X_k[/mm] - > [mm]A^{-1}[/mm] für k -> [mm]\infty.[/mm]
>
> hmm... was sagst du dazu ? hab ich damit die behauptung
> gezeigt?
Sieht gut aus und außerdem sehr nach Banachschem Fixpunktsatz  Kannst Du nat. alternativ auch zitieren. So bliebe noch die Eindeutigkeit zu zeigen.
viele Grüße
mathemaduenn
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:32 Do 19.10.2006 | | Autor: | Riley |
Hi Mathemaduenn!
hmm, okay, allerdings haben wir den banachschen fixpunktsatz in dieser und auch in sonst noch keiner VL durchgenommen. hab ihn aber grad mal nachgeschlagen, ... ;) nur, gibt es eine möglichkeit die eindeutigkeit auch ohne diesen satz zu zeigen? ... weil in den büchern ist das über diese kontraktionseigenschaft gezeigt, die wir ja auch noch nicht eingeführt haben und dann kann ich schlecht zu einem widerspruch kommen...?
viele grüße
riley
|
|
|
| |
|
Hallo Riley,
![[sorry]](/images/smileys/sorry.gif "[sorry]") das ich dich verwirrt habe. Es war doch schon völlig richtig und ausreichend![[daumenhoch]](/images/smileys/daumenhoch.gif "[daumenhoch]") (bis auf ein paar vergessene Klammern).
Über den Banachschen FPS geht nat. auch muß aber nicht sein da Du ja den GW. schon kennst.
viele Grüße
mathemaduenn
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:43 Fr 20.10.2006 | | Autor: | Riley |
Hi Mathemaduenn!
okay, alles klar :) vielen dank für deine hilfe!
viele grüße
riley =))
|
|
|
|
