Konvergenzbedingungen < Numerik < Hochschule < Mathe < Vorhilfe
|
Hi Leute,
Ich wollte eigentlich nur sichergehen, daß ich richtig gerechnet habe. 
Aufgabe:
Prüfe die Konvergenz des Gesamt- und Einzelschrittverfahrens für die Matrizen:
[m]\left( {\begin{array}{*{20}c}
1 & { - 2} & 2 \\
{ - 1} & 1 & { - 1} \\
{ - 2} & { - 2} & 1 \\
\end{array} } \right)[/m] und [m]\bruch{1}{2}\left( {\begin{array}{*{20}c}
2 & 1 & 1 \\
{ - 2} & 2 & { - 2} \\
{ - 1} & 1 & 2 \\
\end{array} } \right)[/m].
Es reicht also, wenn das starke Zeilensummenkriterium gilt:
zu a)
[m]\begin{gathered}
\left| { - 2} \right| + 2 = 4 > 1 \hfill \\
\left| { - 1} \right| + \left| { - 1} \right| = 2 > 1 \hfill \\
\left| { - 2} \right| + \left| { - 2} \right| = 4 > 1 \hfill \\
\end{gathered}[/m]
Damit konvergieren beide Verfahren.
zu b)
[m]\begin{gathered}
0.5 + 0.5 = 1 \geqslant 1 \hfill \\
\left| { - 1} \right| + \left| { - 1} \right| = 2\;\red{>}\;1 \hfill \\
\left| { - 0.5} \right| + 0.5 = 1 \geqslant 1 \hfill \\
\end{gathered}[/m]
Das heißt also, daß diese Matrix das schwache Zeilensummenkriterium erfüllt, richtig? Es bleibt noch die Unzerlegbarkeit zu zeigen, weshalb ich an dieser Stelle mal die Definition aus dem PraMa-Skript abschreibe:
Seien $n [mm] \in \IN$ [/mm] und [m]A \in \left(n \times n, \IK\right),\,A = \left(a_{i,j}\right)[/m]. A heißt zerlegbar, wenn es nichtleere Teilmengen [mm] $N_1$ [/mm] und [mm] $N_2$ [/mm] von $N := [mm] \left\{1,\ldots,n\right\}$ [/mm] gibt mit:
[m]\begin{gathered}
1.\quad N_1 \cap N_2 = \emptyset \hfill \\
2.\quad N_1 \cup N_2 = N \hfill \\
3.\quad \forall i \in N_1 \forall j \in N_2 :a_{i,j} = 0 \hfill \\
\end{gathered}[/m].
A heißt ansonsten unzerlegbar.
(Hmm, DaMenge wenn Du das hier liest, so wollte ich dich fragen, ob's tatsächlich ausreicht, daß die Nebendiagonalen einer Matrix vollbesetzt sein müssen, damit Unzerlegbarkeit gilt? Habe ich das irgendwie im Skript überlesen?)
Für unseren konkreten Fall gibt es 6 Möglichkeiten für eine solche Zerlegung (oder gibt's noch mehr?):
[m]\begin{array}{*{20}c}
{N_1 } &\vline & {N_2 } \\
\hline
{\left\{ 1 \right\}} &\vline & {\left\{ {2,3} \right\}} \\
{\left\{ {2,3} \right\}} &\vline & {\left\{ 1 \right\}} \\
{\left\{ {1,2} \right\}} &\vline & {\left\{ 3 \right\}} \\
{\left\{ 3 \right\}} &\vline & {\left\{ {2,1} \right\}} \\
{\left\{ {1,3} \right\}} &\vline & {\left\{ 2 \right\}} \\
{\left\{ 2 \right\}} &\vline & {\left\{ {1,3} \right\}} \\
\end{array}[/m]
Das heißt alle Einträge der Matrix mit Ausnahme der Einträge auf der Hauptdiagonalen müssen Null sein, oder wie? Ok, das würde natürlich erklären, warum es ausreicht nur die Nebendiagonalen zu betrachten. Aber müßte A dann nicht sogar dann schon unzerlegbar sein, wenn es irgendwo in der Matrix einen Eintrag > 0 gibt, der nicht auf der Hauptdiagonale liegt?
Oder habe ich die obige Definition mißverstanden? Wenn ja, was besagt diese dann wirklich?
Ok, in jedem Fall würde ich sagen, daß A unzerlegbar ist, womit also wieder beide Verfahren konvergieren.
Vielen Dank!
Grüße
Karl
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:05 So 06.03.2005 | | Autor: | DaMenge |
Hi Karl,
also zuerst zu den Zeilensummenkriterium: das starke gilt, wenn : $ [mm] \sum\limits_{\begin{subarray}{l} j = 1 \\ j \ne i \end{subarray}} [/mm] ^{n} [mm] {\frac{{\left| {a_{ij} } \right|}} {{\left| {a_{ii} } \right|}}} [/mm] < [mm] 1,\;i [/mm] = 1,2, [mm] \ldots [/mm] ,n $
wohlgemerkt : KLEINER ALS 1 - nicht wie bei dir größer.
Man sagt dazu auch "diagonaldominant", denn es ist das gleiche wie:
$ [mm] \sum\limits_{\begin{subarray}{l} j = 1 \\ j \ne i \end{subarray}} [/mm] ^{n} [mm] {\left| {a_{ij} } \right| } [/mm] < [mm] \left| {a_{ii} } \right|,\;i [/mm] = 1,2, [mm] \ldots [/mm] ,n $
das bedeutet in Worten : Das Diagonalelement ist (betragsmäßig) größer als aller anderen in der Zeile zusammen, also dominant.
Deshalb musst du da nochmal nachschauen.
Zu der Unzerlegbarkeit : in dem Skript auf : www.iam.uni-bonn.de/~arndt/
ist auf Seite 132f. ein Beispiel (4.3.4), weshalb beide vollen Nebendiagonalen hinreichen für Unzerlegbarkeit.
Zusammenfassend : (durch Widerspruch:) sonst müsste es ein i aus [mm] N_1 [/mm] und (i+1) aus [mm] N_2 [/mm] (oder andersrum) geben, so dass $ [mm] a_{i,i+1} [/mm] $ bzw. $ [mm] a_{i+1,i} [/mm] $ gleich 0 ist, dies sind aber gerade die Nebendiagonalelemente, die alle nach Vorraussetzung ungleich 0 sind...
[es reich nicht aus, wenn nur irgendwo eine Eintrag ungleich 0 ist, siehe dazu die Permutierte Matrix nach Beispiel 4.3.2]
Damit die Verfahren konvergieren muss aber neben der Unzerlegbarkeit noch das schwache Zeilensummenkriterium erfüllt sein, also musst du dort mal schauen.
ich hoffe, ich habe alle fragen erwischt..
viele Grüße
DaMenge
|
|
|
|
