Iteration < Nichtlineare Gleich. < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:17 Mi 15.12.2004 | | Autor: | Bastiane |
Hallo!
Bei dieser Aufgabe hier habe ich gerade mal ein bisschen rumprobiert, ob der Ansatz wohl richtig ist?
Sei [mm] T\in\IR^{n\times n} [/mm] eine Matrix und sei [mm] x^{(0)}\in\IR^n [/mm] ein Startwert.
Die Folge [mm] (x^{(k)})_{k\in\IN} [/mm] sei durch die Iterationsvorschrift [mm] x^{(k+1)}=Tx^{(k)} [/mm] definiert. Zeige, dass [mm] (x^{(k)})_{k\in\IN} [/mm] genau dann für jeden beliebigen Startwert konvergiert, wenn für jeden Eigenwert [mm] \lambda [/mm] von T gilt:
a) [mm] |\lambda|<1
[/mm]
Ich habe nun überlegt, dass man das bestimmt wieder in ein Fixpunktproblem verwandeln muss, bzw. den Banachschen Fixpunksatz anwenden kann (den Fixpunkt selber brauchen wir ja nicht). Nun bräuchte ich für den Fixpunktsatz ja eine kontrahierende Abbildung, also eine Schranke L<1 so dass
||T(x)-T(y)||<L||x-y||
Nun gilt für Eigenwerte [mm] \lambda:
[/mm]
[mm] T(x)=\lambda [/mm] x
für [mm] |\lambda| [/mm] <1 gilt also:
||T(x)||<||x||
und
||T(y)||<||y||
Nun hatte ich versucht, mithilfe der Dreiecksungleichung auf die Form
||T(x)-T(y)||<||x-y||
zu kommen, aber das habe ich irgendwie nicht so ganz geschafft...
Würde das denn so reichen? Und welche Norm muss ich hier nehmen? Und komme ich da denn überhaupt mit der Dreiecksungleichung hin?
Viele Grüße
Bastiane
![[breakdance]](/images/smileys/breakdance.gif "[breakdance]")
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:43 Mi 15.12.2004 | | Autor: | Stefan |
Liebe Christiane!
Nein, so kann man es leider nicht machen, da dein Beweis nur für Eigenvektoren zutrifft und nicht jeder Vektor ein Eigenvektor ist.
Man muss das Ganze über die Jordansche Normalform beweisen.
Hast du den "Hämmerlin-Hoffmann"? Wenn ja, dort steht der Beweis in Kapitel 8 (Iteration), Paragraph 3. Wenn nicht, werde ich ihn wohl abtippen (und etwas ausführen) müssen.
Kannst mir ja kurz Bescheid sagen...
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:07 Mi 15.12.2004 | | Autor: | Bastiane |
Hallo Stefan!
> Hast du den "Hämmerlin-Hoffmann"? Wenn ja, dort steht der
> Beweis in Kapitel 8 (Iteration), Paragraph 3. Wenn nicht,
> werde ich ihn wohl abtippen (und etwas ausführen) müssen.
Nein, den habe ich leider nicht - wie sieht das Buch denn aus, dann gucke ich für die Zukunft mal in der Bibliothek.
Hast du nicht zufällig einen Scanner? Dann könnte ich schon mal selbst versuchen, es zu verstehen...
Viele Grüße
Christiane
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:06 Mi 15.12.2004 | | Autor: | Stefan |
Liebe Christiane!
Na, dann wollen wir mal! 
Es sei [mm] $\xi$ [/mm] eine Lösung der Fixpunktgleichung $Tx=x$.
Für alle $k [mm] \in \IN$ [/mm] gilt:
[mm] $x^{(k+1)} [/mm] - [mm] \xi [/mm] = [mm] T(x^{(k)}) [/mm] - [mm] T(\xi) [/mm] = [mm] T(x^{(k)} [/mm] - [mm] \xi) [/mm] = [mm] T^{k+1}(x^{(0)} [/mm] - [mm] \xi)$.
[/mm]
Daraus ist ersichtlich, dass die Iterationsfolge [mm] $(x^{(k)})_{k \in \IN_0}$, $x^{(k+1)} [/mm] = [mm] T(x^{(k)})$, [/mm] für [mm] $x^{(0)} \ne \xi$ [/mm] genau dann gegen den Fixpunkt [mm] $\xi$ [/mm] konvergiert, wenn [mm] $\lim\limits_{k \to \infty}T^k=0$ [/mm] elementweise gilt.
Wir möchten nun zeigen, dass jedenfalls dann, wenn der Betrag des betragsmäßig größten Eigenwertes von $T$ kleiner als Eins ist, der Fall ist.
Wegen
[mm] $(CTC^{-1})^k [/mm] = [mm] CT^kC^{-1}$
[/mm]
für jede invertierbare Matrix $C$, genügt es die Behauptung für einen speziellen Vertreter der Ähnlichkeitsklasse von $T$ zu zeigen. Wir zeigen die Behauptung daher für die Jordansche Normalform $J$ von $T$ (wir gehen davon aus, dass wir uns über dem Körper [mm] $\IC$ [/mm] befinden, betrachten also auch komplexe Eigenwerte).
Genauer zeigen wir also:
Es gilt [mm] $\lim\limits_{k \to \infty}J^k=0$, [/mm] wenn alle (eventuell mehrfach gezählten) Eigenwerte [mm] $\lambda_1,\ldots,\lambda_n$ [/mm] von $T$ dem Betrage nach kleiner als Eins sind.
Dazu sei für alle [mm] $\mu \in \{1,2,\ldots,m\}$ [/mm] mit einem $1 [mm] \le [/mm] m [mm] \le [/mm] n$
[mm] $J_{\mu} [/mm] = [mm] \begin{pmatrix} \lambda_{\mu} & 1 & & \\ & \ddots & \ddots & 0 \\ 0 & & \ddots & 1 \\ & & & \lambda_{\mu} \end{pmatrix}$
[/mm]
ein Jordankästchen zum Eigenwert [mm] $\lambda_{\mu}$ [/mm] der Jordanschen Normalform $J$ von $T$.
Da offenbar
[mm] $J^k [/mm] = [mm] \begin{pmatrix} J_1^k & & & 0 \\ & J_2^k & & \\ & & \ddots & \\ 0 & & & J_m^k \end{pmatrix}$
[/mm]
gilt, genügt es das Konvergenzverhalten eines Jordankästchens zu untersuchen.
Wir schreibe [mm] $J_{\mu}$ [/mm] in der Form
[mm] $J_{\mu} [/mm] = [mm] \lambda_{\mu} E_n [/mm] + N$ mit
$N:= [mm] \begin{pmatrix} 0 & 1 & & & \\ & \ddots & \ddots & 0 & \\ & & \ddots & \ddots & \\ 0 & & & \ddots & 1 \\ & & & & 0 \end{pmatrix}$
[/mm]
und bilden [mm] $J_{\mu}^k [/mm] = [mm] (\lambda_{\mu}E_n [/mm] + [mm] N)^k$ [/mm] mit dem Binomischen Lehrsatz. Wegen [mm] $N^n=0$ [/mm] erhält man:
[mm] $J_{\mu}^k [/mm] = [mm] \sum\limits_{i=1}^{n-1} [/mm] {k [mm] \choose [/mm] i} [mm] \lambda_{\mu}^{k-i}N^i$.
[/mm]
Für jedes feste $i [mm] \in \{0,1,\ldots,n-1\}$ [/mm] hat man die Abschätzung
[mm] $\left\vert {k \choose i} \lambda_{\mu}^{k-i} \right\vert \le \left\vert \lambda_{\mu}^{k-i} \cdot k^i \right\vert$
[/mm]
und wegen [mm] $|\lambda_{\mu} [/mm] | < 1$ die Konvergenz
[mm] $\lim\limits_{k \to \infty} \left\vert {k \choose i} \lambda_{\mu}^{k-i} \right\vert [/mm] =0$,
woraus die Behauptung folgt.
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:11 Mi 15.12.2004 | | Autor: | Bastiane |
Hallo Stefan!
Vielen Dank für die Antwort. Ich war mir gar nicht sicher, ob du das heute noch schaffen würdest, vor allem weil ich auch gar keine Frage mit einer Fälligkeit mehr geschrieben hatte.
Ich hoffe, ich kann mich jetzt kurz fassen, auch wenn ich den genauen Überblick über die ganze Aufgabe noch nicht habe. Aber ich gucke es mir gleich nochmal genauer an.
> Wir möchten nun zeigen, dass jedenfalls dann, wenn der
> Betrag des betragsmäßig größten Eigenwertes von [mm]T[/mm] kleiner
> als Eins ist, der Fall ist.
Sind das denn jetzt beide Richtungen, oder ist das nur [mm] \Leftarrow [/mm] ?
> Wegen
>
> [mm](CTC^{-1})^k = CT^kC^{-1}[/mm]
>
> für jede invertierbare Matrix [mm]C[/mm], genügt es die Behauptung
Gilt das echt für beliebige invertierbare Matrizen? Hätte ich gar nicht gedacht! Du brauchst es mir jetzt nicht zu beweisen, aber macht man das über Induktion? Oder kann man das einfach so "ausrechnen"? (aber das werde ich in der Aufgabe nicht mehr hinschreiben)
> wir uns über dem Körper [mm]\IC[/mm] befinden, betrachten also auch
> komplexe Eigenwerte).
Ist das in der Aufgabe denn gefordert? Und benutzen wir das eigentlich irgendwo? (aber ich glaube, das ist auch nicht ganz sooo wichtig)
>
> Genauer zeigen wir also:
>
> Es gilt [mm]\lim\limits_{k \to \infty}J^k[/mm], wenn alle (eventuell
> mehrfach gezählten) Eigenwerte [mm]\lambda_1,\ldots,\lambda_n[/mm]
> von [mm]T[/mm] dem Betrage nach kleiner als Eins sind.
Da fehlt doch was, oder? Ein =0?
> Für jedes feste [mm]i \in \{0,1,\ldots,n-1\}[/mm] hat man die
> Abschätzung
>
> [mm]\left\vert {k \choose i} \lambda_{\mu}^{k-i} \right\vert \le \left\vert \lambda_{\mu}^{k-i} \cdot k^i \right\vert[/mm]
Das sehe ich noch nicht so ganz - wie kommt man dadrauf?
Vielen vielen Dank für deine Hilfe bzw. die Lösung. ![[peinlich]](/images/smileys/peinlich.gif "[peinlich]")
viele Grüße
Christiane
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:25 Mi 15.12.2004 | | Autor: | Stefan |
Liebe Christiane!
> Sind das denn jetzt beide Richtungen, oder ist das nur
> [mm]\Leftarrow[/mm] ?
Die andere Richtung ist naehzu trivial, solltest du aber auch noch hinschreiben:
Gibt es einen Egenwert [mm] $\lambda$ [/mm] mit [mm] $|\lambda| \ge [/mm] 1$, dann gilt für einen zugehörigen Eigenvektor $v$:
$T^kx = [mm] \lambda^k [/mm] x$,
und wegen [mm] $\lim\limits_{k \to \infty} \lambda^k \ne [/mm] 0$ kann [mm] $(T^k)_{k \in \IN}$ [/mm] keine Nullfolge sein und daher die Iterationsfolge nicht konvergieren.
> Gilt das echt für beliebige invertierbare Matrizen? Hätte
> ich gar nicht gedacht! Du brauchst es mir jetzt nicht zu
> beweisen, aber macht man das über Induktion? Oder kann man
> das einfach so "ausrechnen"? (aber das werde ich in der
> Aufgabe nicht mehr hinschreiben)
Rechne es doch mal aus. Die $C$'s und [mm] $C^{-1}$'s [/mm] heben sich immer gegenseitig weg.
> Ist das in der Aufgabe denn gefordert? Und benutzen wir
> das eigentlich irgendwo? (aber ich glaube, das ist auch
> nicht ganz sooo wichtig)
Wenn wir das Ganze nicht über [mm] $\IC$ [/mm] betrachte, zerfallen die charakteristische Polynome nicht notwendig und es gibt nicht notwendig eine Jordansche Normalform, die wir ja benutzen.
> > Für jedes feste [mm]i \in \{0,1,\ldots,n-1\}[/mm] hat man die
> > Abschätzung
> >
> > [mm]\left\vert {k \choose i} \lambda_{\mu}^{k-i} \right\vert \le \left\vert \lambda_{\mu}^{k-i} \cdot k^i \right\vert[/mm]
>
> Das sehe ich noch nicht so ganz - wie kommt man dadrauf?
${k [mm] \choose [/mm] i} = [mm] \frac{k \cdot (k-1) \cdot \ldots \cdot (k-i+1)}{i!}$ [/mm] besteht aus $i$ Faktoren, die alle kleiner oder gleich $k$ sind.
Liebe Grüße.
Stefan
|
|
|
|
