www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Numerik linearer Gleichungssysteme" - Relaxation
Relaxation < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Numerik linearer Gleichungssysteme"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Relaxation: SOR-Verfahren
Status: (Frage) reagiert/warte auf Reaktion Status 
Datum: 23:16 Fr 18.03.2005
Autor: Karl_Pech

Hi Leute,

Ich habe []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



        
Bezug
Relaxation: Ansatz
Status: (Antwort) fertig Status 
Datum: 00:02 Sa 19.03.2005
Autor: mathemaduenn

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


Bezug
                
Bezug
Relaxation: Danke :)
Status: (Frage) beantwortet Status 
Datum: 09:33 Sa 19.03.2005
Autor: Karl_Pech

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



Bezug
                        
Bezug
Relaxation: Inverse von D
Status: (Antwort) fertig Status 
Datum: 09:53 Sa 19.03.2005
Autor: mathemaduenn

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

Bezug
                                
Bezug
Relaxation: Hmm...
Status: (Frage) beantwortet Status 
Datum: 10:06 Sa 19.03.2005
Autor: Karl_Pech


>  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



Bezug
                                        
Bezug
Relaxation: Hab's
Status: (Antwort) fertig Status 
Datum: 10:17 Sa 19.03.2005
Autor: mathemaduenn

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

Bezug
                                                
Bezug
Relaxation: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 10:45 Sa 19.03.2005
Autor: Karl_Pech

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]

Ich würde nur gerne sehen, daß beide Formen des SOR-Verfahren gleich sind. Sind doch gleich, oder?

Viele Grüße
Karl



Bezug
                                                        
Bezug
Relaxation: Schreibweise
Status: (Antwort) fertig Status 
Datum: 11:22 Sa 19.03.2005
Autor: mathemaduenn

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





Bezug
                                                                
Bezug
Relaxation: klar
Status: (Frage) beantwortet Status 
Datum: 11:55 Sa 19.03.2005
Autor: Karl_Pech

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



Bezug
                                                                        
Bezug
Relaxation: Antwort
Status: (Antwort) fertig Status 
Datum: 08:57 So 20.03.2005
Autor: mathemaduenn

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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Numerik linearer Gleichungssysteme"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]