Relaxation < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 23:16 Fr 18.03.2005 | | Autor: | Karl_Pech |
Hi Leute,
Ich habe ![[]](/images/popup.gif) folgende Frage im Usenet gestellt, habe dort aber noch keine Antwort dazu erhalten. Deshalb wollte ich fragen, ob vielleicht jemand hier eine Idee dazu hat!
Danke!
Viele Grüße
Karl
|
|
| |
|
Hallo Karl,
Den Usenet Artikel hab ich jetzt nur halb gelesen(wegen der Formeln  )
Aber Du willst Dir das SOR Verfahren bzw. das relaxierte Jacobiverfahren herleiten.
Dazu der Ansatz:
Jacobi:
[mm] Dx=Dx+\omega(b-Ax)=Dx+\omega(b-Lx+Dx+Rx)
[/mm]
[mm] Dx^{i+1}=Dx^i+\omega(b-Lx^i+Dx^i+Rx^i)
[/mm]
SOR:
[mm] Dx^{i+1}=Dx^i+\omega(b-Lx^{i+1}+Dx^i+Rx^i)
[/mm]
gruß
mathemaduenn
|
|
|
| |
|
Hi mathemaduenn!
Du hast mir den richtigen Denkansatz gegeben. Danke! 
Ich nehme an, daß diese Herleitung nun richtig ist, weil die resultierende Gleichung dem Skript entspricht:
Jacobi-SOR-Verfahren:
Wir wollen folgendes herleiten: [m]x^{\left( {i + 1} \right)} : = \omega b + \left( {\green{E} + \left( {L + D + R} \right)} \right)x^{\left( i \right)}[/m]. Aber mein Problem lag die ganze Zeit darin, daß ich von Folgendem ausging: [m]x^{\left( {i + 1} \right)} : = \omega b + \left( {\red{D} + \left( {L + D + R} \right)} \right)x^{\left( i \right)}[/m]. Kein Wunder, daß ich das nicht auf die ursprüngliche Form $Ax = b$ rückentwickeln konnte.
Wie kam ich auf diesen Fehler? Im Skript steht folgendes:
[m]x^{\left( {i + 1} \right)} : = \omega b + \left( {\blue{E} + \left( {L + \blue{E} + R} \right)} \right)x^{\left( i \right)}[/m] und deshalb der ganze Ärger. Das E ist ja im Skript gerade die Hauptdiagonalmatrix, die auf die Einheitsform gebracht wurde. Deshalb dachte ich, daß mit dem ersten E auch diese Matrix gemeint ist, und ich ein äquivalentes Verfahren kriege, wenn ich also für E überall D einsetze. Ein Trugschluß, weil ich nun sehe, daß dieses "außenstehende" E durch das Distributivgesetz entsteht. Hier also nun die richtige Herleitung:
[m]\begin{gathered}
Ax = b \Leftrightarrow \omega Ax = \omega b \Leftrightarrow 0 = \omega b - \omega Ax \hfill \\
\Leftrightarrow \blue{x - x} = \omega b - \omega Ax \Leftrightarrow x = \omega b + x - \omega Ax \hfill \\
= \omega b + x - \omega \left( {L + D + R} \right)x = \omega b + \left( {\blue{E} - \omega \left( {L + D + R} \right)} \right)x \hfill \\
\end{gathered}[/m]
Und das ist das Jacobi-SOR-Verfahren.
Vermutlich habe ich beim Gauss-Seidel-SOR-Verfahren denselben [m]D\not \Leftrightarrow E - {\text{Fehler}}[/m] gemacht. Da muß ich aber noch schauen.
Viele Grüße
Karl
|
|
|
| |
|
Hallo Karl,
Mir fehlt noch ein wenig das [mm] D^{-1} [/mm] bei deinem Jacobiverfahren. Hab ich jetzt Tomaten auf den Augen und das was Du schreibst ist dasselbe?
gruß
mathemaduenn
|
|
|
| |
|
> Mir fehlt noch ein wenig das [mm]D^{-1}[/mm] bei deinem
> Jacobiverfahren. Hab ich jetzt Tomaten auf den Augen und
> das was Du schreibst ist dasselbe?
Aber die Umformungen, die ich gemacht habe, waren doch allesamt Äquivalenzumformungen, oder nicht? Es kann natürlich auch sein, daß ich nichts Sinnvolles hergeleitet habe . Am besten ich kopiere nochmal die Originalform aus dem Arndt-Skript:
[mm]x^{(i+1)} = \omega b + [E-\omega(L+E+R)]\cdot{}x^{(i)}[/mm]
[mm]C_G(\omega):=(1-\omega)E-\omega(L+R)[/mm] und [mm]C_G(1)=C_G[/mm]
[mm]C_G(\omega)[/mm] ist die Iterationsmatrix des relaxierten Gesamtschrittverfahrens. Mit [mm]y=\omega b[/mm] ergibt sich dann [mm]x^{(i+1)}=F\left(x^{(i)}\right)=C_G(\omega)x^{(i)}+y[/mm]. Man wähle [mm]\omega[/mm] so, daß der Spektralradius [mm]\rho\left(C_G(\omega)\right)[/mm] möglichst klein ist.
Die Matrix [mm]C_G = -(L+R)[/mm] habe die reellen Eigenwerte [mm]\lambda_1 \le \lambda_2 \le \dotsm \le\lambda_n[/mm] mit den Eigenvektoren [mm]y^1, y^2,\dotsc,y^n[/mm]. Es sei [mm]\rho\left(C_G\right)<1[/mm]. Dann hat [mm]C_G(\omega)[/mm] die Eigenvektoren [mm]y^1,y^2,\dotsc,y^n[/mm] zu den Eigenwerten [mm]1-\omega+\omega\cdot{}\lambda_i[/mm], [mm]i=1,\dotsc,n[/mm]. Der Spektralradius [mm]\rho\left(C_G(\omega)\right)[/mm] wird minimal für
[mm]\omega^{\*}=\frac{2}{2-\lambda_1-\lambda_n}.[/mm]
Der Nenner ist wegen [mm]\rho\left(C_G\right)<1[/mm] ungleich Null. Im Falle [mm]\lambda_1\ne -\lambda_n[/mm] ist die Konvergenz des Verfahrens mit [mm]C_G(\omega)[/mm] besser als mit [mm]C_G[/mm].
So sieht das bei ihm aus. Hat er da einen Tippfehler gemacht?
Viele Grüße
Karl
|
|
|
| |
|
Hallo Karl,
Bei der normalisierten Form ist ja schon mit [mm] D^{-1} [/mm] multipliziert worden. Hat ich vergessen. Also L wäre quasi das untere Dreieck von A mit das mit [mm] D^{-1} [/mm] multipliziert worden ist.
gruß
mathemaduenn
|
|
|
| |
|
Hallo mathemaduenn,
> Bei der normalisierten Form ist ja schon mit [mm]D^{-1}[/mm]
> multipliziert worden. Hat ich vergessen. Also L wäre quasi
> das untere Dreieck von A mit das mit [mm]D^{-1}[/mm] multipliziert
> worden ist.
Könntest Du mir das den nochmal herleiten? Ich versteh' leider noch nicht so ganz was du jetzt meinst. ![[sorry]](/images/smileys/sorry.gif "[sorry]")
Ich würde nur gerne sehen, daß beide Formen des SOR-Verfahren gleich sind. Sind doch gleich, oder?
Viele Grüße
Karl
|
|
|
| |
|
Hallo Karl,
Start
[mm]Dx=Dx+\omega (b-Ax)[/mm]
[mm]Dx^{(i+1)}=Dx^{(i)}+\omega (b-Ax^{(i)})[/mm]
[mm]x^{(i+1)}=x^{(i)}+\omega (D^{-1}b-D^{-1}Ax^{(i)})[/mm]
[mm]x^{(i+1)}=x^{(i)}+\omega (D^{-1}b-D^{-1}(L+D+R)x^{(i)})[/mm]
[mm]x^{(i+1)}=x^{(i)}+\omega (D^{-1}b-(D^{-1}L+E+D^{-1}R)x^{(i)})[/mm]
[mm]x^{(i+1)}=(1-\omega) x^{(i)}+\omega (D^{-1}b-(D^{-1}L+D^{-1}R)
x^{(i)})[/mm]
[mm]x^{(i+1)}=((1-\omega)E-\omega D^{-1}(L+R)) x^{(i)}+\omega D^{-1}b[/mm]
Der einzige Unterschied zu deinem Skript ist die normalisierte Darstellung. Um Schreibarbeit zu sparen sollen [mm] (L+E+R):=D^{-1}A [/mm] und b offensichtlich [mm] D^{-1}b [/mm] sein. Deine L,R wären also andere als meine L,R.
gruß
mathemaduenn
|
|
|
| |
|
Hallo mathemaduenn,
Ich denke, ich konnte beide Darstellungen jetzt gut nachvollziehen; Danke!
Der Unterschied zwischen den beiden Verfahren, liegt also genau am Anfang:
Du beginnst mit: $Dx - Dx + [mm] \omega [/mm] Ax = [mm] \omega [/mm] b$
Ich beginne mit: $x - x + [mm] \omega [/mm] Ax = [mm] \omega [/mm] b$
Es läuft also auf dasselbe hinaus, aber es ist natürlich klar, daß man von mir in der Klausur, wohl eher die 2te Variante verlangen wird!
Na ja, hier ist nochmal das Gauss-Seidel-SOR-Verfahren, der Vollständigkeit halber (im Skript werden beide Verfahren nicht aus [m]Ax = b[/m] direkt hergeleitet, deshalb ja meine ganze Fragerei hier ):
[m]\begin{gathered}
Ax = b \Leftrightarrow \omega Ax = \omega b \Leftrightarrow Dx - Dx + \omega Lx + \omega Dx + \omega Rx = \omega b \hfill \\
\Leftrightarrow Dx + \omega Lx = Dx - \omega Dx - \omega Rx + \omega b \hfill \\
\Leftrightarrow Dx + \omega Lx = \left( {D - \omega D - \omega R} \right)x + \omega b \hfill \\
\Leftrightarrow \left( {D + \omega L} \right)x = \left( {\left( {1 - \omega } \right)D - \omega R} \right)x + \omega b \hfill \\
\Rightarrow x^{\left( {i + 1} \right)} : = \left( {D + \omega L} \right)^{ - 1} \left( {\left( {1 - \omega } \right)D - \omega R} \right)x + \omega \left( {D + \omega L} \right)^{ - 1} b \hfill \\
\end{gathered}[/m]
Ok, ich nehme an, daß das so stimmt.
Viele Grüße
Karl
|
|
|
| |
|
Hallo Karl,
> Ok, ich nehme an, daß das so stimmt.
ich auch wobei es jetzt nat. wieder die Darstellung(L,R) ist die ich benutzt hatte - verwirrend.
gruß
mathemaduenn
|
|
|
|
