Konvergenz von Iterationsverf. < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 16:34 Do 03.08.2006 | | Autor: | rungekutta4 |
hallo!
ich hab' mich letzthin etwas mit numerischen verfahren yur lösung von linearen gleichungssystemen herumgeschlagen, namentlich sind das ja gauss-seidel-, jacobi- und sor-verfahren. als ich dann mal zur tat schritt und ein programm auf meinem taschenrechner schrieb, das die iterationsverfahren anwendet, musste ich ernüchtert feststellen, dass ich entweder etwas falsch programmiert hab, etwas falsch in meiner zusammenfassung steht oder ich etwas grundlegendes falsch verstehe. ich hab daraufhin natürlich mal die ersten zwei punkte überprüft, doch verlief die suche ergebnislos, deshalb suche ich jetzt hier rat.
nundenn folgende probleme:
1. das konvergenzkriterium ist kaum zu erfüllen (?)
2. der berechnete lösungsvektor ist falsch
ein beispiel:
nehmen wir mal das gauss-seidel-verfahren (einzelschrittverfahren) mit den einfachen zahlen:
[mm] \underbrace{\pmat{ 2 & 2 \\ 3 & 4 }}_A x=\underbrace{\vektor{1 \\ 2}}_b
[/mm]
unschwer lässt sich die richtige lösung errechnen: [mm] x=\vektor{0 \\ \frac 1 2 }
[/mm]
nun zum beschwerlichen, iterativen weg mit der iterationsvorschrift:
[mm] x^{m+1}=M^{-1}(Nx^m+b)\hspace{40pt}\ddagger
[/mm]
M = [mm] \pmat{ 2 & 0 \\ 3 & 4 }
[/mm]
N = M - A = [mm] \pmat{ 0 & -2 \\ 0 & 0 }
[/mm]
wir wählen willkürlich mal: [mm] x^0=\vektor{ 0\\0 }
[/mm]
nun zu den problemen:
1. das allgemeine konvergenzkriterium für [mm] \ddagger [/mm] lautet:
[mm] ||M^{-1}N||=\alpha<1
[/mm]
die spektralnorm ist laut TR [mm] \frac{5}{4} [/mm] also >1 und somit ist das kriterium nicht erfüllt und das tut es auch nicht für die M und N des jacobi- oder sor-verfahren. aber da fragte ich mich doch, was denn da überhaupt erfüllend sein könnte und ignorierte diese tatsache vorerst mal, da ich keine matrix fand, welche eben dieses kriterium erfüllte. nichtsdestotrotz, kann mir jemand erklären, was ich da falsch mache oder wie hier konvergenz erreicht werden kann? es kann ja nicht sein, dass sogut wie alle 'normalen' matrizen mit den iterationsalgorithmen nicht funktionieren.
2. ich erhalte nach 500 sowie 5000 iterationsschritten (es konvergiert also dahin) folgende (falsche) lösung:
[mm] x\approx\vektor{0.281\\0.289}
[/mm]
wähle ich ein anderes [mm] x^0 [/mm] kommt ein anderer senf raus. und irgendwie stimmte das beim gauss- und sor-verfahren generell nie recht. - beim jacobi-verfahren klappte es in einigen fällen zwar, wenn auch mit sehr langsamer konvergenz.
nundenn.. kann das sein oder .. ist mein code falsch? oder .. ich weiss einfach nicht mehr, was ich noch überprüfen sollte. >____<
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:10 Do 03.08.2006 | | Autor: | RAT |
Hallo, dass die Verfahren selbst bei "einfachen" Matrizen nicht konvergieren kann durchaus sein, es sind keine "Black-Box" Verfahren, man kann nicht einfach was reinstecken und es kommt immer was tolles dabei raus. In der Regel werden die Verfahren für Riesengroße Matrizen mit bestimmter Besetztheitsstrucktur verwendet(wie sie zb bei der Numerik partieller DGLn auftreten). Dafür gibts dann auch ein paar Sätze, die sagen, dass es für die Matrizen funktioniert.
So...den Text hab ich geschrieben bevor ich deine Rechnung überprüft hab...ich muss dir leider sagen, dass du was falsch gemacht hast, die Spektralnorm von M^-1*N ist 3/4, außerdem hab ich das kurz getestet und es konvergiert gegen die Lösung.
Irgendwo hat sich also ein Fehler eingeschlichen...
Gruß
|
|
|
| |
|
hmm. das ist aber merkwürdig, bzw. das sollte nicht sein.
wie ich herausgefunden habe ist ein weiteres stabilitätskriterium, dass die matrix A strikt diagonaldominat und regulär sein muss (siehe wikipedia:"gauss-seidel-verfahren").
ersteres ist hier offensichtlich nicht gegeben, deshalb finde ich meine nicht-konvergenz eigentlich immer noch ganz plausibel. wie dem auch sei, mit diesem wissen war ich jetzt vor allem im stande, eindeutig konvergente matritzen zu bilden und damit meine algorithmen zu testen. herausgestellt hat sich, dass der fehler darin lag, dass ich den parameter "anzahl iterationen" in einer for-schleife zum bilden von L, D und R als zählvariable verwendet hab und dadurch lustigerweise natürlich immer gleich viele iterationen gemacht wurden (im normalfall 2 oder 3) .. und ich meinte, das konvergiere einfach unglaublich krass. ;)
nichtsdestotrotz, danke für die information über den delikaten charakter der verfahren. hat sich mittlerweile bei den aufgaben, die ich doch noch gefunden hab, auch abgezeichnet.
insofern befinde ich mal: diese verfahren sind für meine wenigkeit reichlich überflüssige hirnfüllung. ;)
|
|
|
|
