reduzible Matrix < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Def.: Die Matrix A [mm] \in \IR^{nxn} [/mm] heißt reduzibel, falls disjunkte, nichtleere Indexmengen I, J [mm] \subset [/mm] {1,...,n} existieren, sodass I [mm] \cup [/mm] J = {1,...,n} und [mm] a_{ij}=0 [/mm] für alle Paare (i,j) [mm] \in [/mm] I x J. Andernfalls heißt A irreduzibel.
Beispiel: Die Matrix A = [mm] \pmat{ 1 & 0 & 2 \\ 3 & 4 & 5 \\ 6 & 0 & 7 } [/mm] ist reduzibel mit I = {1,3}, J= {2}.
Bemerkung: Für reduzible Matrizen lässt sich das Lösen des linearen Gleichungssystems Ax=b zerlegen. Ist für X, Y [mm] \subset [/mm] {1,...,n} die Teilmatrix [mm] A_{XY} [/mm] definiert durch [mm] A_{XY}=(a_{ij})_{i \in X, j \in Y} [/mm] und der Teilvektor [mm] x_Y [/mm] durch [mm] x_Y [/mm] = [mm] (x_k)_{k \in Y}, [/mm] so gilt: [mm] A_{II}x_I=b_I [/mm] und [mm] A_{JJ}x_J=b_J-A_{JI}x_I. [/mm] |
Hallo!
Ich habe versucht mir die Bemerkung an dem Beispiel klar zu machen, das vorher für die Definition von reduzibel stand. Daran bin ich bisher gescheitert:
Wir können X durch I und Y durch J ersetzen, oder? Müssten dann nicht bei den letzten beiden Gleichungen auch X, Y stehen statt I, J?
Außerdem verstehe ich die Teilmatrix [mm] A_{XY} [/mm] nicht: hier stehen nur die Einträge an den Stellen (i,j) mit i [mm] \in [/mm] I und j [mm] \in [/mm] J drin? Aber das ist doch nach der Def von reduziblen Matrizen = 0, oder?
Und was ist ein "Teilvektor"? Nur die Einträge an den Stellen j [mm] \in [/mm] J? Aber wäre das nicht auch wieder nur 0?
Irgendwas gravierendes scheine ich zu übersehen. Kann mir dabei jemand helfen?
Liebe Grüße, Lily
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:59 Mi 06.07.2016 | | Autor: | meili |
Hallo Lily,
> Def.: Die Matrix A [mm]\in \IR^{nxn}[/mm] heißt reduzibel, falls
> disjunkte, nichtleere Indexmengen I, J [mm]\subset[/mm] {1,...,n}
> existieren, sodass I [mm]\cup[/mm] J = {1,...,n} und [mm]a_{ij}=0[/mm] für
> alle Paare (i,j) [mm]\in[/mm] I x J. Andernfalls heißt A
> irreduzibel.
>
> Beispiel: Die Matrix A = [mm]\pmat{ 1 & 0 & 2 \\ 3 & 4 & 5 \\ 6 & 0 & 7 }[/mm]
> ist reduzibel mit I = {1,3}, J= {2}.
>
> Bemerkung: Für reduzible Matrizen lässt sich das Lösen
> des linearen Gleichungssystems Ax=b zerlegen. Ist für X, Y
> [mm]\subset[/mm] {1,...,n} die Teilmatrix [mm]A_{XY}[/mm] definiert durch
> [mm]A_{XY}=(a_{ij})_{i \in X, j \in Y}[/mm] und der Teilvektor [mm]x_Y[/mm]
> durch [mm]x_Y[/mm] = [mm](x_k)_{k \in Y},[/mm] so gilt: [mm]A_{II}x_I=b_I[/mm] und
> [mm]A_{JJ}x_J=b_J-A_{JI}x_I.[/mm]
> Hallo!
>
> Ich habe versucht mir die Bemerkung an dem Beispiel klar zu
> machen, das vorher für die Definition von reduzibel stand.
> Daran bin ich bisher gescheitert:
>
> Wir können X durch I und Y durch J ersetzen, oder?
> Müssten dann nicht bei den letzten beiden Gleichungen auch
> X, Y stehen statt I, J?
X und Y werden verwendet um Teilmatrix und Teilvektor zu definieren.
In der Aussage der Bemerkung kommen dann mehrere verschiedene
Teilmatrizen [mm] ($A_{II}$, $A_{JJ}$ [/mm] und [mm] $A_{JI}$) [/mm] und Teilvektoren
[mm] ($x_I$, $x_J$, $b_I$ [/mm] und [mm] $b_J$) [/mm] vor.
>
> Außerdem verstehe ich die Teilmatrix [mm]A_{XY}[/mm] nicht: hier
> stehen nur die Einträge an den Stellen (i,j) mit i [mm]\in[/mm] I
> und j [mm]\in[/mm] J drin? Aber das ist doch nach der Def von
> reduziblen Matrizen = 0, oder?
Bei dem gegebenen Beispiel ist:
[mm] $A_{II} [/mm] = [mm] \pmat{ a_{11} & a_{13} \\ a_{31} & a_{33} } [/mm] = [mm] \pmat{ 1 & 2 \\ 6 & 7 }$
[/mm]
[mm] $A_{JJ} [/mm] = [mm] \pmat{ a_{22} } [/mm] = [mm] \pmat{ 4 }$
[/mm]
[mm] $A_{JI} [/mm] = [mm] \pmat{ a_{21} & a_{23} } [/mm] = [mm] \pmat{ 3 & 5 }$
[/mm]
[mm] $x_I [/mm] = [mm] \vektor{x_1 \\ x_3 }$
[/mm]
[mm] $x_J [/mm] = [mm] \vektor{x_2}$
[/mm]
Zusammengesetzt:
[mm] $\pmat{ 1 & 2 \\ 6 & 7 }\vektor{x_1 \\ x_3 } [/mm] = [mm] \vektor{b_1 \\ b_3 }$ [/mm] und
[mm] $\left(4 \right) \left( x_2 \right) [/mm] = [mm] \left( b_2 \right) [/mm] - [mm] \pmat{ 3 & 5 }\vektor{x_1 \\ x_3}$
[/mm]
>
> Und was ist ein "Teilvektor"? Nur die Einträge an den
> Stellen j [mm]\in[/mm] J? Aber wäre das nicht auch wieder nur 0?
>
> Irgendwas gravierendes scheine ich zu übersehen. Kann mir
> dabei jemand helfen?
>
> Liebe Grüße, Lily
Gruß
meili
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:59 Do 07.07.2016 | | Autor: | Mathe-Lily |
Ah, jetzt verstehe ich das, vielen Dank! 
|
|
|
| |
|
Hallo!
Jetzt habe ich doch noch eine Frage dazu:
Ist A reduzibel, wenn man mindestens eine solche Zerlegung in I und J findet, und nur dann irreduzibel, wenn man keine findet?
Auf diese Frage bin ich so gekommen:
Satz: Ist A irreduzibel und diagonaldominant, so sind Jacobi- und Gauß-Seidelverfahren durchführbar und konvergent.
In einer Bemerkung auf der Seite danach steht: Beide Voraussetzungen des Satzes werden benötigt, um eine Kontraktionseigenschaft der Iterationsmatrizen zu garantieren, wie das Beispiel A = [mm] \pmat{ \bruch{1}{2} & \bruch{1}{2} \\ 0 & 1 }, M^J= -D^{-1}(A-D) [/mm] = [mm] \pmat{ 0 & -1 \\ 0 & 0 } [/mm] zeigt. [mm] (M^J [/mm] ist die Iterationsmatrix des Jacobi-Verfahrens)
Ich versuche mir zur erklären, was das bedeutet:
A ist diagonaldominant und (wenn die Reduzibilitätsdefinition ist, wie ich sie oben beschrieben habe) reduzibel, dh. [mm] M^J [/mm] ist nicht kontraktiv, was gebraucht wird um die Existenz eines Fixpunktes und damit eine Konvergenz des Verfahrens zu gewährleisten.
Stimmt das? ^^
Liebe Grüße, Lily
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:51 Do 07.07.2016 | | Autor: | fred97 |
> Hallo!
>
> Jetzt habe ich doch noch eine Frage dazu:
> Ist A reduzibel, wenn man mindestens eine solche Zerlegung
> in I und J findet, und nur dann irreduzibel, wenn man keine
> findet?
So ist es.
>
> Auf diese Frage bin ich so gekommen:
> Satz: Ist A irreduzibel und diagonaldominant, so sind
> Jacobi- und Gauß-Seidelverfahren durchführbar und
> konvergent.
>
> In einer Bemerkung auf der Seite danach steht: Beide
> Voraussetzungen des Satzes werden benötigt, um eine
> Kontraktionseigenschaft der Iterationsmatrizen zu
> garantieren, wie das Beispiel A = [mm]\pmat{ \bruch{1}{2} & \bruch{1}{2} \\ 0 & 1 }, M^J= -D^{-1}(A-D)[/mm]
> = [mm]\pmat{ 0 & -1 \\ 0 & 0 }[/mm] zeigt. [mm](M^J[/mm] ist die
> Iterationsmatrix des Jacobi-Verfahrens)
>
> Ich versuche mir zur erklären, was das bedeutet:
> A ist diagonaldominant und (wenn die
> Reduzibilitätsdefinition ist, wie ich sie oben beschrieben
> habe) reduzibel, dh. [mm]M^J[/mm] ist nicht kontraktiv, was
> gebraucht wird um die Existenz eines Fixpunktes und damit
> eine Konvergenz des Verfahrens zu gewährleisten.
>
> Stimmt das? ^^
Ja
FRED
>
> Liebe Grüße, Lily
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:32 Fr 08.07.2016 | | Autor: | Mathe-Lily |
Toll, danke!
|
|
|
|
