Jacobi / Gauß-Seidel < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:49 Mo 16.02.2009 | | Autor: | Pacapear |
Hallo zusammen.
Ich verstehe bei der Zerlegung einer gegebenen Matrix A nicht, welche x man als [mm] x_{k+1} [/mm] (das x im nächsten Schritt) wählt, und welche als [mm] x_k [/mm] (das x aus dem aktuellen Schritt).
Also ich meine folgendes:
Jacobi-Verfahren
Ich zerlege ja A in [mm]\ A=D-B [/mm]
Wenn ich diese Zerlegung jetzt in [mm]\ Ax=b [/mm] einsetze, erhalte ich nach Umformen [mm] x=D^{-1}Bx+D^{-1}b.
[/mm]
Nun folgt daraus in meinem Skript direkt [mm] x_{k+1}=D^{-1}Bx_k+D^{-1}b
[/mm]
Woher weiß ich das? Also welches [mm]\ x [/mm] das [mm] x_{k+1} [/mm] ist und welches das [mm] x_k?
[/mm]
Ist es, weil ich ja eine Fixpunktiteration erhalten will, und die immer die Form [mm] x_{k+1}=\phi(x_k) [/mm] haben?
Gauß-Seidel
Hier hab ich quasi das gleiche Problem.
Ich zerlege ja A in [mm]\ A=D-E-F [/mm]
Wenn ich diese Zerlegung jetzt in [mm]\ Ax=b [/mm] einsetze, erhalte ich nach Umformen [mm] x=D^{-1}(Ex+Fx+b).
[/mm]
Nun folgt daraus in meinem Skript direkt [mm] x_{k+1}=D^{-1}(Ex_{k+1}+Fx_k+b)
[/mm]
Woher weiß ich hier, welches [mm]\ x [/mm] das [mm] x_{k+1} [/mm] ist und welches das [mm] x_k?
[/mm]
Mit der Fixpunktiteration (falls das denn stimmt) kann ich es mir hier nicht mehr erklären.
Wieso hab ich zweimal [mm] x_{k+1} [/mm] und nur einmal [mm] x_k?
[/mm]
Und warum steht das [mm] x_k [/mm] nicht am F und umgekehrt?
LG, Nadine
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:28 Di 17.02.2009 | | Autor: | Blech |
Du hast in der Numerik drei Ziele, die Du erreichen willst:
1. Schnelle Algorithmen
2. Allgemeingültige Algorithmen
(3. Stabile Algorithmen -- Stabilität wird für alle vorausgesetzt, aber es gibt gutmütigere und empfindlichere. Einer der Vorteile des iterativen Lösens von LGS ist ja, daß sie Rundungsfehler leichter wegstecken als Gauß.)
Und man geht die Probleme aus zwei unterschiedlichen Richtungen an. Einerseits beginnt man oft bei allgemeinen Verfahren aus der reinen Mathematik und versucht die schnell zu machen. Andererseits sucht man sich ein Sammelsurium aus Methoden zusammen, die für Spezialfälle schnell sind (und bei denen man auch schnell entscheiden kann, ob der Spezialfall vorliegt).
Die Idee des Verfahrens hier ist: Wir nutzen Fixpunktiteration zum iterativen Lösen von bestimmten LGS.
Jetzt ist unser Problem in der Form Ax=b gegeben. Damit wir die Idee umsetzen können, müssen wir das ganze in Fixpunktform bringen.
Der Ansatz, der auf
[mm] $x=D^{-1}Bx [/mm] + [mm] D^{-1}b$
[/mm]
führt, hat 2 große Vorteile:
1. Wir sehen sofort ob [mm] $D^{-1}$ [/mm] existiert
2. Falls ja, können wir es genauso schnell ausrechnen.
Man könnte durchaus oben nach dem anderen x auflösen, oder A anders zerlegen, aber Inverse zu berechnen ist sehr, sehr aufwendig und das würde das Verfahren völlig nutzlos machen. Was bringt mir der schönste Algorithmus, wenn er prohibitiv teuer ist?
Also der Grund für die Iterationsvorschrift ist:
-Sie ist leicht zu berechnen
-und führt zu einem stabilen Algorithmus.
-Für die Klasse von Fällen, wo der anwendbar ist, d.h. wir eine Kontraktion kriegen und auf den Fixpunkt konvergieren, haben wir einen Fortschritt erzielt.
ciao
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:34 Di 17.02.2009 | | Autor: | Pacapear |
Hallo Stefan!
Das ich das Ganze als Fixpunktiteration schreiben will, hab ich verstanden.
Was ich aber nicht verstanden habe:
Warum steht in der Fixpunktgleichung [mm] \phi(x)=x_{k+1}=D^{-1}(Ex_{k+1}+Fx_k+b) [/mm] beim Gauß-Seidel-Verfahren an dem E auch ein [mm] x^{k+1} [/mm] und nicht nur ein [mm] x^k [/mm] ?
[mm] x^{k+1} [/mm] ist ja gleich [mm] \phi(x), [/mm] ich könnte ja dann auch schreiben [mm] \phi(x)=x_{k+1}=D^{-1}(E\phi(x)+Fx_k+b), [/mm] das wäre ja dann irgendwie rekursiv ![[nixweiss]](/images/smileys/nixweiss.gif "[nixweiss]")
LG, Nadine
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:44 Di 17.02.2009 | | Autor: | Blech |
> Hallo Stefan!
>
> Das ich das Ganze als Fixpunktiteration schreiben will, hab
> ich verstanden.
>
> Was ich aber nicht verstanden habe:
>
> Warum steht in der Fixpunktgleichung
> [mm]\phi(x)=x_{k+1}=D^{-1}(Ex_{k+1}+Fx_k+b)[/mm] beim
> Gauß-Seidel-Verfahren an dem E auch ein [mm]x^{k+1}[/mm] und nicht
> nur ein [mm]x^k[/mm] ?
Die Idee bei Gauß-Seidel ist, daß man das darüber erweitert, indem man die schon ausgerechneten Teile von [mm] $x^{k+1}$ [/mm] zur Berechnung von [mm] $x^{k+1}_i$ [/mm] heranzieht.
E ist eine strikte untere Dreiecksmatrix, also wird für die Berechnung von [mm] $x^{k+1}_i$ [/mm] nur [mm] $\left(x^{k+1}_j\right)_{j
Irgendwer saß mal vor seinem Rechner und hat gerade die update-Schleife geschrieben und sich dabei gefragt "hey, warum überschreib ich die Werte nicht in situ?"
Das Verfahren ist also schnell.
Die Fixpunktgleichung wäre hier zwar
[mm] $x=(D+E)^{-1}(Fx+b)$
[/mm]
aber man braucht [mm] $(D+E)^{-1}$ [/mm] ja nicht.
ciao
Stefan
|
|
|
|
