numerische Verfahren < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
Hallo Leute,
Ich würde gerne wissen, ob ich richtig gerechnet habe und ob mir nicht jemand ein Beispiel zum Rechnen geben könnte, wo das Einzelschrittverfahren funktioniert.
Und muß man das eigentlich unbedingt mit dem Sassenfeld-Kriterium machen. Was ist z.B. mit diesem ominösen Spektralradius? Ich weiß nicht, wie ich mir das Sassenfeld-Kriterium für die Klausur merken soll. :-(
Ok, hier geht's los:
Das Verfahren:
Wir gehen wieder von [m]A \in M\left( {n \times n,\IK} \right);\;x, b \in \IK^n[/m] aus, machen diesmal aber etwas andere Umformungen:
[m]\begin{gathered}
Ax = b \Leftrightarrow \left( {L + D + R} \right)x = b \Leftrightarrow Lx + Dx + Rx = b \Leftrightarrow \left( {L + D} \right)x + Rx = b \hfill \\
\Leftrightarrow x + \left( {L + D} \right)^{ - 1} Rx = \left( {L + D} \right)^{ - 1} b \Leftrightarrow x = - \left( {L + D} \right)^{ - 1} Rx + \left( {L + D} \right)^{ - 1} b \hfill \\
\end{gathered}[/m]
Damit lautet unser neues Verfahren: [m]x^{\left( {i + 1} \right)} : = - \left( {L + D} \right)^{ - 1} Rx^{\left( i \right)} + \left( {L + D} \right)^{ - 1} b[/m].
Konvergenzkriterien für unser Verfahren:
Sei $A = [mm] \left( a_{ij} \right)$.
[/mm]
Sassenfeld-Kriterium: Ist folgende Ungleichung erfüllt: [m]\left\| { - \left( {L + D} \right)^{ - 1} R} \right\|_{\infty ,\infty } \leqslant \mathop {\max }\limits_{1 \leqslant i \leqslant n} s_i \leqslant \mathop {\max }\limits_{1 \leqslant i \leqslant n} \sum\limits_{\begin{subarray}{l}
j = 1 \\
j \ne i
\end{subarray}} ^{n} {\left| {a_{ij} } \right|} < 1[/m] mit [m]s_i : = \sum\limits_{j = 1}^{i - 1} {\left| {a_{ij} } \right|*s_j } + \sum\limits_{j = i + 1}^n {\left| {a_{ij} } \right|} ,\,i = 1, \ldots ,n[/m], so konvergiert sowohl das Einzelschritt- als auch das Gesamtschrittverfahren.
Ein Beispiel:
Seien [m]A: = \left( {\begin{array}{*{20}c}
{ - 6} & 3 & { - 2} \\
4 & 9 & 4 \\
2 & 5 & 8 \\
\end{array} } \right);\;b: = \left( {\begin{array}{*{20}c}
5 \\
3 \\
2 \\
\end{array} } \right)[/m]. Wir überprüfen zuerst die Konvergenz des Verfahrens mit dem oberen Kriterium bevor wir unser Verfahren benutzen:
[m] - \left( {L + D} \right)^{ - 1} = \left( {\begin{array}{*{20}c}
{\tfrac{1}
{6}} & 0 & 0 \\
{ - \tfrac{2}
{{27}}} & { - \tfrac{1}
{9}} & 0 \\
{\tfrac{1}
{{216}}} & {\tfrac{5}
{{72}}} & { - \tfrac{1}
{8}} \\
\end{array} } \right)[/m]
und
[m] - \left( {L + D} \right)^{ - 1} R = - \left( {L + D} \right)^{ - 1} \left( {\begin{array}{*{20}c}
0 & 3 & { - 2} \\
0 & 0 & 4 \\
0 & 0 & 0 \\
\end{array} } \right) = \left( {\begin{array}{*{20}c}
0 & {\tfrac{1}
{2}} & { - \tfrac{1}
{3}} \\
0 & { - \tfrac{2}
{9}} & { - \tfrac{8}
{{27}}} \\
0 & {\tfrac{1}
{{72}}} & {\tfrac{{29}}
{{108}}} \\
\end{array} } \right)[/m].
Nun berechnen wir hiervon die Zeilensummennorm:
[m]\max \left\{ {0 + \frac{1}
{2} + \frac{1}
{3},\;0 + \frac{2}
{9} + \frac{8}
{{27}},\;0 + \frac{1}
{{72}} + \frac{{29}}
{{108}}} \right\} = \max \left\{ {\frac{5}
{6},\;\frac{{14}}
{{27}},\;\frac{{61}}
{{216}}} \right\} = \frac{5}
{6}[/m].
Nun berechnen wir s:
[m]\begin{gathered}
s_1 : = \underbrace {\sum\limits_{j = 1}^0 \cdots }_0 + \sum\limits_{j = 2}^3 {\left| {a_{1j} } \right|} = \left| {a_{12} } \right| + \left| {a_{13} } \right| = 3 + 2 = 5 \hfill \\
s_2 : = \sum\limits_{j = 1}^1 {\left| {a_{2j} } \right|*s_j } + \sum\limits_{j = 3}^3 {\left| {a_{2j} } \right|} = \left| {a_{21} } \right|*s_1 + \left| {a_{23} } \right| = 4*5 + 4 = 24 \hfill \\
s_3 : = \sum\limits_{j = 1}^2 {\left| {a_{3j} } \right|*s_j } + \underbrace {\sum\limits_{j = 4}^3 \cdots }_0 = \left| {a_{31} } \right|*s_1 + \left| {a_{32} } \right|*s_2 = 2*5 + 5*24 = 5\left( {2 + 24} \right) = 130 \hfill \\
\max \left\{ {5,\;24,\;130} \right\} = 130 \hfill \\
\end{gathered}[/m]
Also: [mm] $\bruch{5}{6} [/mm] < 130$, womit die linke Seite der Ungleichung zwar erfüllt ist, aber offensichtlich nicht die rechte Seite. Damit sollte die Benutzung des Einzelschrittverfahrens zu keinem brauchbaren Ergebnis führen, oder?
Grüße
Karl
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:45 Fr 04.02.2005 | | Autor: | DaMenge |
Hi,
dein Problem hat eine einfache Lösung:
du musst das Sassenfeld-Kriterium nicht auf A überprüfen, sondern auf deine Iterationsmatrix , also auf: $ - [mm] \left( {L + D} \right)^{ - 1} [/mm] R $
übrigens: um mal deine Verfahren in der Praxis zu erläutern:
du hast Konvergenz gegeben GENAU DANN WENN der Spektralradius kleiner als 1 ist, ABER das kann man in realen Fällen (1000x1000 Matrizen) wohl kaum überprüfen (siehe Eigenwert Berechnungen von Mises & CO...),
deshalb ist das starke Zeilensumenkriterium HINREICHEND dafür, dass der Spektralradius kleiner als 1 ist, also wenn man das zeigen kann, ist man glücklich...
Weiterhin, speziell beim Einzelschrittverfahren: es gilt, wie du richtig schreibst: $ [mm] \left\| { - \left( {L + D} \right)^{ - 1} R} \right\|_{\infty ,\infty } \leqslant \mathop {\max }\limits_{1 \leqslant i \leqslant n} s_i \leqslant \mathop {\max }\limits_{1 \leqslant i \leqslant n} \sum\limits_{\begin{subarray}{l} j = 1 \\ j \ne i \end{subarray}} [/mm] ^{n} [mm] {\left| {a_{ij} } \right|} [/mm] < 1 $
Aber das besagt doch gerade: (Man geht von einer Matrix A=L+E+R aus) wenn A strikt diagonaldominant (=starke ZeilensummenKriterium) , dann ist auch das maximale s des Sassenfeld-Kriterium noch kleiner, also insbesondere auch kleiner als 1.
[Außerdem steht da noch, dass die Operatornorm kleiner als das maximale s sein muss, d.h. wenn das Kleiner als 1 ist, dann besteht Konvergenz]
D.H : man überprüft zuerst auf Diagonaldominanz (hier konvergiert sowohl Gesamt- als auch EinzelSchrittverfahren), sollte das nicht hinhauen, dann überprüfe auf Sassenfeld...
Sollte dies alles nicht funzen - tja dann muss man noch Sätze kennen wie:
wenn die Iterationsmatrix (also nicht A) unzerlegbar ist (z.B wenn beide nebendiagonalen voll besetzt sind wie bei der diskretiesierung von Direchlet-Randwert-problemen) und sie das schwache Zeilensummenkriterium erfüllt, dann konvergiert sowohl Gesamt- als auch Einzelschrittverfahren.
Hoffe, dass ich mich jetzt nicht vertan hab - ist alles ausm Gedächtnis...
(also bitte überprüfen)
viele Grüße
DaMenge
|
|
|
| |
|
Hallo DaMenge,
Ich kenne das Sassenfeldkriterium nicht. Aber lerne natürlich immer gern dazu
> du musst das Sassenfeld-Kriterium nicht auf A überprüfen,
> sondern auf deine Iterationsmatrix , also auf: [mm]- \left( {L + D} \right)^{ - 1} R[/mm]
> Weiterhin, speziell beim Einzelschrittverfahren: es gilt,
> wie du richtig schreibst: [mm]\left\| { - \left( {L + D} \right)^{ - 1} R} \right\|_{\infty ,\infty } \leqslant \mathop {\max }\limits_{1 \leqslant i \leqslant n} s_i \leqslant \mathop {\max }\limits_{1 \leqslant i \leqslant n} \sum\limits_{\begin{subarray}{l} j = 1 \\ j \ne i \end{subarray}} ^{n} {\left| {a_{ij} } \right|} < 1[/mm]
Das verstehe ich nicht wenn links die Zeilensummennorm steht und rechts die Zeilensummennorm ohne das Diagonalelement(wenn ich jetzt alles auf die Matrix [mm] -(L+D)^{-1}R [/mm] beziehe) das verstehe ich nicht. Oder meintest du das sich nur die [mm] s_i [/mm] auf die Iterationsmatrix beziehen. Vielleicht kannst du das ja noch etwas genauer ausführen.
gruß
mathemaduenn
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:34 Sa 05.02.2005 | | Autor: | DaMenge |
Hi,
anscheinend ist dieses Kriterium wirklich nicht besonders bekannt, deswegen sage ich noch ein bischen dazu.
(Beweise findet man in dem PraMa-Skript auf ![[]](/images/popup.gif) dieser Seite [ca. S.124] )
Also, es geht um das Einzelschrittverfahren - man geht davon aus, dass man die Diagonalelemente nach geeigneter Transformation schon normiert hat, also A=L+E+R
(dies scheint im orginal-post nicht gemacht worden zu sein !!)
Dann ist folgendes definiert: $ [mm] s_{i} [/mm] := [mm] \summe_{j=1}^{i-1}(|a_{ij}|\cdot{}s_{j})+ \summe_{j=i+1}^{n}(|a_{ij}|) [/mm] $
und das Sassenfeld-Kriterium ist erfüllt, wenn : $ [mm] 1>s_{m} [/mm] := max [mm] \{ s_{i} \} [/mm] $
jetzt kann man schnell zeigen, dass die Zeilensummennorm der Iterationsmatrix kleiner als dieses $ [mm] s_{m} [/mm] $ ist , also : $ [mm] \left\| { C_E } \right\|_{\infty ,\infty } \leqslant \mathop {\max }\limits_{1 \leqslant i \leqslant n} s_i =s_m [/mm] <1 $
und somit das einzelschrittverfahren konvergiert
außerdem zeigt man schnell, dass wenn Diagonaldominanz vorliegt (=starken Zeilensummenkriterium für diese Matrix A=L+E+R), dann gilt:
$ [mm] s_m \le \mathop {\max }\limits_{1 \leqslant i \leqslant n} \sum\limits_{\begin{subarray}{l} j = 1 \\ j \ne i \end{subarray}} [/mm] ^{n} [mm] {\left| {a_{ij} } \right|} [/mm] = [mm] \left\| { C_G } \right\|_{\infty ,\infty } [/mm] < 1 $
also ist das Sassenfeld-Kriterium erfüllt, wenn Diagonaldominanz vorliegt (und die Matrix auf die Form A=L+E+R gebracht wurde), d.h. bei Diagonaldominanz konvergieren sowohl Einzel- als auch Gesamtschrittverfahren und beim Sassenfeld-Kriterium konvergiert das Einzelschrittverfahren.
Ich weiß jetzt erhlich gesagt gar nicht, ob ich alle Fragen damit (vor allem: richtig) beantwortet habe, deshalb empfehle ich dringend obiges Skript - da findet man alles richtig und vollständig.
viele Grüße
DaMenge
|
|
|
| |
|
Hallo DaMenge, Hallo mathemaduenn,
> Hi,
> anscheinend ist dieses Kriterium wirklich nicht besonders
> bekannt, deswegen sage ich noch ein bischen dazu.
> (Beweise findet man in dem PraMa-Skript auf
> dieser Seite
> [ca. S.124] )
Unglaublich, dieses Skript scheinen hier doch einige naturwiss. Studenten zu benutzen. Bastiane, DaMenge, (...?) und ich. 
> Also, es geht um das Einzelschrittverfahren - man geht
> davon aus, dass man die Diagonalelemente nach geeigneter
> Transformation schon normiert hat, also A=L+E+R
> (dies scheint im orginal-post nicht gemacht worden zu sein
> !!)
Ich nehme an, du meinst man solle A zuerst so umformen, daß auf der Hauptdiagonale von A nur Einsen stehen, oder? Und da wir ja offenbar das Gleiche Skript benutzen. Warum steht dort [mm] $C_G$? [/mm] Im Beweis scheint doch [mm] $C_G [/mm] = A$ zu sein, oder nicht? Wär' Klasse, wenn Du mir den Beweis Schritt für Schritt nochmal erklären könntest.
Und irgendwie komme ich jetzt ein wenig mit den Kriterien für dieses Verfahren durcheinander. Also ich hab' dich jetzt so verstanden, daß man dieses Sassenfeld-Kriterium gar nicht braucht, sondern nur die Sache mit dem starken Zeilensummenkriterium? Den letzteres scheint sowieso ein allgemeineres "Heilmittel" zu sein, was die Konvergenz dieser Schrittverfahren angeht und Sassenfeld-V. ist viel komplizierter und nur auf Einzelschritt-V. beschränkt?
Vielen Dank!
Schöne Grüße
Karl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:28 Sa 05.02.2005 | | Autor: | DaMenge |
Hi Karl,
ich hatte gerade diesen Freitag meine letzte Vordiplomsprüfung beim Herrn Arndt gemacht und deshalb kenne ich aktuell dieses Skript ganz gut.
> Ich nehme an, du meinst man solle A zuerst so umformen, daß
> auf der Hauptdiagonale von A nur Einsen stehen, oder?
genau ! das musst du zuerst machen !
> Warum steht
> dort [mm]C_G[/mm]? Im Beweis scheint doch [mm]C_G = A[/mm] zu
> sein, oder
> nicht? Wär' Klasse, wenn Du mir den Beweis Schritt für
> Schritt nochmal erklären könntest.
Hier weiß ich nicht genau, welchen genauen Beweis du nochmal erklärt haben willst (nenne ruhig die Nummer)
Wenn 4.1.4 sein sollte: hier sind zwei Aussagen enthalten:
1) Wenn Sassenfeld erfüllt, dann konvergiert das Einzelschrittverfahren
2) wenn diagonaldominant, dann ist sassenfeld erfüllt.
Aber wegen dem $ [mm] C_G [/mm] $ : Also dies ist die Iterationsmatrix des Gesamtschrittverfahren, also normaler weise : $ [mm] D^{-1}(L+R) [/mm] $
wobei A=L+D+R wäre - wir wollten jetzt aber schon von dieser Gestalt ausgehen: A=L+E+R
dann ist $ [mm] C_G [/mm] = L+R $ also nicht (ganz) A !!!
> Und irgendwie komme ich jetzt ein wenig mit den Kriterien
> für dieses Verfahren durcheinander. Also ich hab' dich
> jetzt so verstanden, daß man dieses Sassenfeld-Kriterium
> gar nicht braucht, sondern nur die Sache mit dem starken
> Zeilensummenkriterium? Den letzteres scheint sowieso ein
> allgemeineres "Heilmittel" zu sein, was die Konvergenz
> dieser Schrittverfahren angeht und Sassenfeld-V. ist viel
> komplizierter und nur auf Einzelschritt-V. beschränkt?
Hier ist viel richtig, aber ich sage es vielleicht nochmal eindeutig:
wenn A=L+D+R diagonaldominant ist (=starke Zeilensummenkriterium) dann gilt natürlich nach der Umfrmung zu A=L+E+R , dass $ [mm] \mathop {\max }\limits_{1 \leqslant i \leqslant n} \sum\limits_{\begin{subarray}{l} j = 1 \\ j \ne i \end{subarray}} [/mm] ^{n} [mm] {\left| {a_{ij} } \right|} [/mm] < 1 $
also (das sagt auch dieser Satz 4.1.4) wenn A diagonaldominant ist, dann konvergiert das Gesamtschrittverfahren und das Einzelschrittverfahren.
Wenn dies NICHT gegeben ist, dann kann man noch das Sassenfeld-Kriterium überprüfen - wenn dies erfüllt wird, dann konvergiert zumindest das Einzelschrittverfahren !
Sollte beides nicht erfüllt sein, dann muss man evtl. noch prüfen, ob A unzerlegbar ist ("beide Nebendiagonalen sind voll besetzt" ist hinreichend dafür) und das schwache Zeilensummenkriterium erfüllt ist - Dann konvergioeren auch wieder beide Verfahren.
wenn dies alles nicht erfüllt sein sollte, muss man wohl oder übel den Spektralradius überprüfen - denn dies ist eine äquivalente Bedingung zur Konvergenz !
hoffe, ich kann es halbwegs richtig erklären - gestern saß es noch sattelfester^^
viele Grüße
DaMenge
|
|
|
| |
|
Hallo Karl,
Danke für die Info bezgl. Sassenfeld. Ich hab nochmal nachgedacht für deine Aufgabe ist ja ein ganz basales Konvergenzkriterium erfüllt. Die Tatsache das die Norm der Iterationsmatrix kleiner 1 ist sichert die Anwendbarkeit des Banachschen Fixpunktsatzes. Das Sassenfeldkrit. liefert demzufolge wahrscheinlich nur weitere Abschätzungen der Zeilensummennorm. Das letztere ist aber nur eine Vermutung.
viele Grüße
mathemaduenn
|
|
|
| |
|
wenn du Karl_Pech nochmal das Einzelschrittverfahren so detaliert beschreibst wie bei dem Gesamtschrittverfahren.
Wäre echt super von dir, das Gesamtschrittverfahren hast du so super erklärt, das mir fast ein Stein vom Hernzen gefallen ist :)
Wäre sehr dankbar
|
|
|
| |
|
Hallo Thomas,
Zunächst einmal gehen wir wieder von folgendem Grundproblem aus: $Ax = b$. Dabei ist $A [mm] \in M\left( {n \times n,\IK} \right)$ [/mm] eine quadratische Matrix und $b, x [mm] \in \IK^n$ [/mm] sind Vektoren mit jeweils [mm] $n\!$ [/mm] Zeilen. [mm] $b\!$ [/mm] ist der Ergebnisvektor und wir wollen wissen für welchen Vektor [mm] $x\!$ [/mm] das Gleichungssystem das Ergebnis [mm] $b\!$ [/mm] liefert.
Das Verfahren:
Angenommen [mm] $n\!$ [/mm] ist so groß, daß wir es in vernünftiger Zeit nicht exakt berechnen können. Dann benutzen wir ein Näherungsverfahren. Z.B. das Einzelschrittverfahren. Dafür zerlegen wir [mm] $A\!$ [/mm] in die 3 Matrizen $L, [mm] D\!$ [/mm] und [mm] $R\!$. $L\!$ [/mm] ist eine Matrix, welche auf ihrer Hauptdiagonale und oberhalb Dieser nur Nullen enthält. [mm] $R\!$ [/mm] ist eine Matrix, welche auf ihrer Hauptdiagonale und unterhalb dieser nur Nullen enthält. [mm] $D\!$ [/mm] ist eine Matrix, welche überall - außer auf ihrer Hauptdiagonale - zwingend Nullen enthält.
Wegen der Matrizenaddition ist es klar, daß $A = L + D + [mm] R\!$ [/mm] gilt. Beispiel:
[m]\left( {\begin{array}{*{20}c}
a & b & c \\
d & e & f \\
g & h & i \\
\end{array} } \right) = \left( {\begin{array}{*{20}c}
0 & 0 & 0 \\
d & 0 & 0 \\
g & h & 0 \\
\end{array} } \right) + \left( {\begin{array}{*{20}c}
a & 0 & 0 \\
0 & e & 0 \\
0 & 0 & i \\
\end{array} } \right) + \left( {\begin{array}{*{20}c}
0 & b & c \\
0 & 0 & f \\
0 & 0 & 0 \\
\end{array} } \right)[/m]
Das können wir aber in unsere Gleichung $Ax = [mm] b\!$ [/mm] einsetzen:
[m]\begin{gathered}
Ax = b \Leftrightarrow \left( {L + D + R} \right)x = b \Leftrightarrow \left( {\left( {L + D} \right) + R} \right)x = b \Leftrightarrow \left. {\left( {L + D} \right)x + Rx = b} \;\right|*\left( {L + D} \right)^{ - 1} \hfill \\
\Leftrightarrow x + \left( {L + D} \right)^{ - 1} Rx = \left( {L + D} \right)^{ - 1} b \Leftrightarrow x = \left( {L + D} \right)^{ - 1} b - \left( {L + D} \right)^{ - 1} Rx = - \left( {L + D} \right)^{ - 1} Rx + \left( {L + D} \right)^{ - 1} b \hfill \\
\end{gathered}[/m]
Damit lautet unser Verfahren:
[m] \Rightarrow x^{\left( {i + 1} \right)} : = - \left( {L + D} \right)^{ - 1} Rx^{\left( i \right)} + \left( {L + D} \right)^{ - 1} b[/m]
Es funktioniert also (wie auch beim Gesamtschrittverfahren) so, daß du in diese Gleichung rechts einen Startvektor einsetzt (könnte z.B. eine, deiner Meinung nach, gute Schätzung für den Lösungsvektor am Schluß sein.) Dann rechnest du das Ganze aus und erhälst einen neuen Startvektor. Diesen setzt Du wieder rechts in deine Gleichung ein. u.s.w. bis dir die Näherungslösung, die Du bisher erzielt hast, gefällt.
Bevor wir uns ein Beispiel dafür ansehen, müssen wir, wie auch beim anderen Verfahren, Bedingungen betrachten, unter denen unser Verfahren (gut) funktioniert:
Konvergenzkriterien für das Einzelschrittverfahren:
Hier sind die Kriterien, die wir auf [mm] $A\!$ [/mm] oder seine Iterationsmatrix anwenden können:
starkes Zeilensummenkriterium (Diagonaldominanz):
[m]\sum\limits_{\begin{subarray}{l}
j = 1 \\
j \ne i
\end{subarray}} ^{n} {\frac{{\left| {a_{ij} } \right|}}
{{\left| {a_{ii} } \right|}}} < 1,\;i = 1,2, \ldots ,n[/m]
Ist dieses Kriterium erfüllt, so konvergiert unser Verfahren (und das Gesamtschrittverfahren).
Sassenfeld-Kriterium:
(siehe dazu auch die Diskussionen mit mathemaduenn! )
Wir wollen alle Einträge der Matrix [mm] $A\!$ [/mm] zunächst mit Indizes versehen, um das Verfahren für jeden einzelnen Eintrag überhaupt beschreiben zu können: $A = [mm] \left(a_{ij}\right)$.
[/mm]
Bevor wir dieses Kriterium benutzen können, müssen wir dafür sorgen, daß die Matrix [mm] $D\!$ [/mm] in der Zerlegung $A = [mm] L+D+R\!$ [/mm] nur Einsen auf ihrer Hauptdiagonale enthält ("normieren"). Damit entspricht $D$ der Einheitsmatrix und wir schreiben
$A = [mm] L+E+R\!$ [/mm] und unsere Iterationsmatrix lautet dann [m] - \left( {L + E} \right)^{ - 1} R[/m]. Jetzt zum Kriterium:
Wir definieren rekursiv:
[m]s_i : = \sum\limits_{j = 1}^{i - 1} {\left| {a_{ij} } \right|s_j } + \sum\limits_{j = i + 1}^n {\left| {a_{ij} } \right|} ,\;i = 1,2, \ldots ,n[/m]
Wir berechnen also dieses [mm] $s_i$ [/mm] für jede einzelne Zeile von [mm] $A\!$ [/mm] beginnend bei [mm] $s_1$. [/mm] Danach schauen wir, welches dieser [mm] $s\texttt{-Werte}$ [/mm] das Größte ist, wofür dann folgende Bedingung gilt:
[m]\left\| { - \left( {L + E} \right)^{ - 1} R} \right\|_{\infty ,\infty } \leqslant \mathop {\max }\limits_{1 \leqslant i \leqslant n} s_i \leqslant \left\| {C_G } \right\|_{\infty ,\infty } < 1,[/m]
wobei [mm] $C_G$ [/mm] die Iterationsmatrix des Gesamtschrittverfahrens ist. Gilt diese Bedingung, so konvergiert unser Verfahren (und auch ein Gesamtschrittverfahren).
schwaches Zeilensummenkriterium und vollbesetzte Nebendiagonalen:
"Sollte beides nicht erfüllt sein, dann muss man evtl. noch prüfen, ob A unzerlegbar ist ("beide Nebendiagonalen sind voll besetzt" ist hinreichend dafür) und das schwache Zeilensummenkriterium erfüllt ist - Dann konvergieren auch wieder beide Verfahren." (DaMenge)
Also z.B.
[m]\left( {\begin{array}{*{20}c}
\star & {n_{1_1 } } & \star \\
{n_{2_1 } } & \star & {n_{1_2 } } \\
\star & {n_{2_2 } } & \star \\
\end{array} } \right),[/m]
wobei alle [mm] $n\texttt{-Einträge}$ [/mm] hier [mm] $\ne [/mm] 0$ sein müssen und außerdem noch folgendes gelten muß:
[m]\left( {\sum\limits_{\begin{subarray}{l}
j = 1 \\
j \ne i
\end{subarray}} ^{n} {\frac{{\left| {a_{ij} } \right|}}
{{\left| {a_{ii} } \right|}}} \leqslant 1,\;i = 1,2, \ldots ,n} \right) \wedge \left( {{\text{Es gibt min}}{\text{. }}1{\text{ }}i_0 {\text{, so da{\ss} }}\sum\limits_{\begin{subarray}{l}
j = 1 \\
j \ne i_0
\end{subarray}} ^{n} {\frac{{\left| {a_{i_0 j} } \right|}}
{{\left| {a_{i_0 i_0 } } \right|}}} < 1} \right)[/m]
Beachte das [mm] $\le$ [/mm] in der ersten Formel. Das ist (neben der zweiten Formel) ein weiterer Unterschied zum starken Zeilensummenkriterium. Im Grunde genommen ist das wohl so etwas wie ein "abgeschwächtes" starkes Zeilensummenkriterium, wo das starke Zeilensummenkriterium halt nur für ein bestimmtes [mm] $i_0$ [/mm] gilt.
Spektralradius (Das Allzweck-Kriterium(?)):
"wenn dies alles nicht erfüllt sein sollte, muss man wohl oder übel den Spektralradius überprüfen - denn dies ist eine äquivalente Bedingung zur Konvergenz!" (DaMenge)
1.) Ermittle die Eigenwerte der Iterationsmatrix des Näherungsverfahrens (z.B. mit der Determinante; geht das eigentlich noch irgendwie schneller?).
2.) Suche nach dem betragsmäßig größten Eigenwert aus der Lösungsmenge der gefundenen Eigenwerte (siehe Antwort von Stefan)
3.) Ist dieser Eigenwert < 1, so konvergiert unser Näherungsverfahren, obwohl alle anderen Kriterien versagt haben.
Beispiel für unser Verfahren:
[m]A: = \left( {\begin{array}{*{20}c}
{\frac{1}
{6}} & {\frac{1}
{6}} & {\frac{3}
{{22}}} \\
{\frac{1}
{{12}}} & {\frac{1}
{{22}}} & {\frac{9}
{{22}}} \\
{\frac{1}
{3}} & {\frac{7}
{{22}}} & {\frac{1}
{4}} \\
\end{array} } \right)[/m]
Wir prüfen zuerst das starke Zeilensummenkriterium:
Seien $i = [mm] 1\!$ [/mm] und [m]\textstyle j = 2, 3: \frac{{\frac{1}
{6}}}
{{\frac{1}
{6}}} + \frac{{\frac{3}
{{22}}}}
{{\frac{1}
{6}}} = 1 + \frac{9}
{{11}} = \frac{{20}}
{{11}}\not < 1[/m]. Wie es scheint, könnten wir gleich hier aufhören, weil das Kriterium gleich in der ersten Spalte nicht erfüllt ist. Die Nebendiagonalen sind zwar voll besetzt, aber man sieht, daß [m]\tfrac{20}{11} \ne 1[/m], womit auch das schwache Zeilensummenkriterium nicht erfüllt ist. Wir führen das Verfahren aber trotzdem zu Ende:
Seien $i = [mm] 2\!$ [/mm] und [m]\textstyle j = 1; 3: \frac{{\frac{1}
{{12}}}}
{{\frac{1}
{{22}}}} + \frac{{\frac{9}
{{22}}}}
{{\frac{1}
{{22}}}} = \frac{{11}}
{6} + 9 = \frac{{65}}
{6}\not \leqslant 1[/m]. Seien $i = [mm] 3\!$ [/mm] und [m]\textstyle j = 1, 2: \frac{{\frac{1}
{3}}}
{{\frac{1}
{4}}} + \frac{{\frac{7}
{{22}}}}
{{\frac{1}
{4}}} = \frac{1}
{{12}} + \frac{7}
{{88}} = \frac{{43}}
{{264}} < 1[/m]. Hättest Du bei der letzten Zeile der Matrix angefangen und dann wegen diesem positiven Ergebnis sofort aufgehört, so hätte es Probleme gegeben. (Ich merke gerade, daß ich mich nicht ganz an die Reihenfolge gehalten habe, weil ich das mit dem schwachen Zsk vorweg genommen habe.) Als nächstes kommt also das Sassenfeld-Kriterium:
Zuerst normieren wir die Matrix:
[Dateianhang nicht öffentlich]
Jetzt benutzen wir Sassenfeld:
[m]\left( {\begin{array}{*{20}c}
1 & 1 & {\frac{9}
{{11}}} \\
{\frac{{11}}
{6}} & 1 & 9 \\
{\frac{4}
{3}} & {\frac{{14}}
{{11}}} & 1 \\
\end{array} } \right) = \left( {\begin{array}{*{20}c}
0 & 0 & 0 \\
{\frac{{11}}
{6}} & 0 & 0 \\
{\frac{4}
{3}} & {\frac{{14}}
{{11}}} & 0 \\
\end{array} } \right) + \left( {\begin{array}{*{20}c}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1 \\
\end{array} } \right) + \left( {\begin{array}{*{20}c}
0 & 1 & {\frac{9}
{{11}}} \\
0 & 0 & 9 \\
0 & 0 & 0 \\
\end{array} } \right)[/m]
Damit gilt:
[m] - \left( {L + E} \right)^{ - 1} R = \left( {\begin{array}{*{20}c}
{ - 1} & 0 & 0 \\
{\frac{{11}}
{6}} & { - 1} & 0 \\
{ - 1} & {\frac{{14}}
{{11}}} & { - 1} \\
\end{array} } \right)\left( {\begin{array}{*{20}c}
0 & 1 & {\frac{9}
{{11}}} \\
0 & 0 & 9 \\
0 & 0 & 0 \\
\end{array} } \right) = \left( {\begin{array}{*{20}c}
0 & { - 1} & { - \frac{9}
{{11}}} \\
0 & {\frac{{11}}
{6}} & { - \frac{{15}}
{2}} \\
0 & { - 1} & {\frac{{117}}
{{11}}} \\
\end{array} } \right)[/m]
Und:
i = 1: [mm] $1+\bruch{9}{11}\operatorname{\textcolor{red}{\not<}}1$
[/mm]
i = 2: [m]21\left( {1 + \frac{9}
{{11}}} \right) + 9 \not< 1[/m]
i = 3: [m]\frac{4}
{3}\left( {1 + \frac{9}
{{11}}} \right) + \frac{{14}}
{{11}}\left( {21\left( {1 + \frac{9}
{{11}}} \right) + 9} \right)\not < 1[/m]
Versuchen wir es noch mit dem Spektralradius:
Wir gehen jetzt also wieder von der nicht normierten Form von [mm] $A\!$ [/mm] aus und zerlegen wie gehabt, dann erhalten wir:
[m] - \left( {L + D} \right)^{ - 1} R = \left( {\begin{array}{*{20}c}
0 & 1 & {\frac{9}
{{11}}} \\
0 & { - \frac{{11}}
{6}} & {\frac{{15}}
{2}} \\
0 & 1 & { - \frac{{117}}
{{11}}} \\
\end{array} } \right)[/m].
Wir bestimmen die Eigenwerte:
[m]\begin{gathered}
\det \left| {\begin{array}{*{20}c}
{ - \lambda } & 1 & {\frac{9}
{{11}}} \\
0 & { - \frac{{11}}
{6} - \lambda } & {\frac{{15}}
{2}} \\
0 & 1 & { - \frac{{117}}
{{11}} - \lambda } \\
\end{array} } \right| = - \lambda ^3 - \frac{{823}}
{{66}}\lambda ^2 - 12\lambda \hfill \\
\Rightarrow \lambda \approx - 1.050898675 \vee \lambda \approx 11.41879829 \vee \lambda = 0 \hfill \\
\end{gathered}[/m]
und sehen, daß selbst der Spektralradius nicht kleiner 1 ist. Na ja, obwohl ich ein schlechtes Beispiel genommen habe, versuchen wir jetzt trotzdem das Verfahren für
[m]b: = \left( {\begin{array}{*{20}c}
1 \\
1 \\
2 \\
\end{array} } \right)[/m]
anzuwenden. Es gilt:
[m] - \left( {L + D} \right)^{ - 1} Rx^{\left( i \right)} + \left( {L + D} \right)^{ - 1} b = \left( {\begin{array}{*{20}c}
{x_{i_2 } + \frac{{9x_{i_3 } }}
{{11}} + 6} \\
{ - \frac{{11x_{i_2 } }}
{6} + \frac{{15}}
{2}x_{i_3 } + 11} \\
{x_{i_2 } - \frac{{117x_{i_3 } }}
{{11}} - 14} \\
\end{array} } \right)[/m]
Und wenn wir wie oben besprochen wiederholt Werte in diese Matrix einsetzen, müßten die Werte im Iterationsvektor betragsmäßig immer größer werden. So erhalte ich z.B. schon nach 3 Iterationen beginnend beim Nullvektor als Startwert:
[m]x_3 = \left( {\begin{array}{*{20}c}
{11.21349862} \\
{1314.623737} \\
{-1680.108815} \\
\end{array} } \right)[/m].
Viele Grüße
Karl
Dateianhänge:
Anhang Nr. 1 (Typ: gif) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:31 Mi 09.02.2005 | | Autor: | DaMenge |
Hi Karl,
ich möchte noch ein paar Informationen ergänzen, obwohl ich deinen Beitrag insgesamt sehr gut finde !!
Also, ich zitiere mal immer son bischen, worauf ich Bezug nehme:
> Damit lautet unser Verfahren:
>
> [m]\Rightarrow x^{\left( {i + 1} \right)} : = - \left( {L + D} \right)^{ - 1} Rx^{\left( i \right)} + \left( {L + D} \right)^{ - 1} b[/m]
es wäre hier mal interessant zu erfahren, worin jetzt genau der Unterschied zwischen Gesamt- und Einzelschrittverfahren besteht.
So, wie du es dort aufschreibst ist es ein Gesamtschrittverfahren, denn man verwendet zur Berechnung des $ [mm] x^{(i+1)} [/mm] $ nur die Werte von $ [mm] x^i [/mm] $ .
Wichtig ist jedoch, dass man in der Praxis natürlich "niemals" ($ [mm] \approx [/mm] $ sehr selten) eine Inverse tatsächlich berechnet, es sei denn, man "sieht" sie sofort ohne große Rechnungen (wie bei Diagonalmatrizen).
Deswegen forme ich mal deinen Ausdruck noch um zu :
$ [mm] (L+D)*x^{(i+1)}=-R*x^{(i)}+b \quad\gdw\quad L*x^{(i+1)}+D*x^{(i+1)}=-R*x^{(i)}+b\quad\gdw\quad D*x^{(i+1)}=b-L*x^{(i+1)}-R*x^{(i)} [/mm] $
das ergibt unser neues Verfahren für die Praxis:
$ [mm] x^{(i+1)}=D^{-1}*(b-L*x^{(i+1)}-R*x^{(i)}) [/mm] $
Das ergibt für die j-te Komponente:
$ [mm] x^{(i+1)}_j =\bruch{1}{a_{jj}}*\left( b_j - \summe_{k=1}^{j-1}a_{j,k}*x^{(i+1)}_k -\summe_{k=j+1}^{n}a_{j,k}x^{(i)}_k \right) [/mm] $
wohlgemerkt: L ist eine echte untere Dreiecksmatrix
was passiert also?
zuerst berechnen wir $ [mm] x^{(i+1)}_1 [/mm] $ - dabei fällt die Komponente in L weg, also wird nur $ [mm] x^{(i)}_2 [/mm] $ bis $ [mm] x^{(i)}_n [/mm] $ benutzt.
Danach berechnen wir $ [mm] x^{(i+1)}_2 [/mm] $ - hierbei benutzen wir laut der Formel aber schon $ [mm] x^{(i+1)}_1 [/mm] $ und danach noch $ [mm] x^{(i)}_3 [/mm] $ bis $ [mm] x^{(i)}_n [/mm] $.
Man sieht also, dass in der j-ten Komponente schon alle vorher berechneten Komponenten derselben Iteration mit eingehen !!
(Im Gegensatz zum Gesamtschrittverfahren, wo immer nur Komponenten der Iteration vorher benutzt werden.)
> starkes Zeilensummenkriterium (Diagonaldominanz):
>
[m]\sum\limits_{\begin{subarray}{l}
j = 1 \\
j \ne i
\end{subarray}} ^{n} {\frac{{\left| {a_{ij} } \right|}}
{{\left| {a_{ii} } \right|}}} < 1\quad ,\;i = 1,2, \ldots ,n[/m]
Ist euch eigentlich schon aufgefallen, dass man hier die Matrix A schon in Form A=L+E+R gebracht hat (so, wie später beim Sassenfeld-Kriterium gebraucht)?
Man könnte das Kriterium der Diagonaldominanz natürlich auch einfach so beschreiben:
[m]\sum\limits_{\begin{subarray}{l}
j = 1 \\
j \ne i
\end{subarray}} ^{n} {\left| {a_{ij} } \right|} < \left| {a_{ii} } \right| \quad ,\;i = 1,2, \ldots ,n[/m]
Hieran sieht man, warum es "diagonaldominant" heißt.
So, deine Rechnungen habe ich dann aber nicht mehr nachvollzogen, aber, du schreibst, doch : unzerlegbar und schwaches Zeilenkriterium !
Ich denke alle anderen Verfahren vorher funzen nicht - erst dieses und Spektralradius natürlich (denn dies funzt genau dann wenn Konvergenz vorliegt)
Wie wäre es also mit eine Matrix, die bei der eindimensionalen Diskretisierung von Randwertproblemen für gewöhnliche Differentialgleichungen öfter auftritt:
$ [mm] M:=\pmat{-2&1&0&0\\1&-2&1&0\\0&1&-2&1\\0&0&1&-2}$
[/mm]
Hat laut Derive die Eigenwerte 0 und 1/2 (für die entspr. Iterationsmatrix !!!) und ist offensichtlich unzerlegbar und erfüllt (nur) das schwache Zeilenkriterium...
Hoffe, dies ist nicht völlig nutzlos..
viele Grüße
DaMenge
|
|
|
|
