Zusammenfassung < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:50 Di 19.09.2006 | | Autor: | Bastiane |
Hallo zusammen!
Damit ich es nicht vergesse (sollte ich den Zettel, auf dem ich es stehen habe, einmal nicht finden  ) oder damit auch andere etwas davon haben, hier ein kurzer Überblick über lineare Iterationsverfahren zur Lösung eines linearen Gleichungssystems Ax=b. Sollte jemand Fehler finden [mm] \to [/mm] bitte melden! 
Wir wollen das Gleichungssystem $Ax=b$ mit [mm] A\in \IR^{n\times n} [/mm] und [mm] b\in \IR^n [/mm] lösen. Allgemein gilt für ein lineares Iterationsverfahren:
[mm] x^{k+1}=Mx^k+Nb [/mm] wobei [mm] M,N\in\IR^{n\times n} [/mm]
Ein solches Verfahren konvergiert, falls für den Spektralradius gilt:
[mm] \rho(M):=|\lambda_{max}(M)|<1 [/mm]
Richardson-Verfahren
Für dieses Verfahren muss die Matrix A symmetrisch positiv definit sein!
Hier wählt man [mm] $M=I-\vartheta [/mm] A$.
Daraus ergibt sich: [mm] x^{k+1}=x^{k}-\vartheta(Ax^k-b).
[/mm]
Dieses Verfahren konvergiert für [mm] $0<\vartheta<\bruch{2}{\lambda_{max}(A)}$.
[/mm]
Beweis hierzu:
Allgemein konvergiert ein solches Verfahren (siehe oben) für [mm] \rho(M)<1. [/mm] Hier gilt:
Sei [mm] \lambda_i [/mm] ein Eigenwert von M so gilt: [mm] \lambda_i=1-\vartheta\lambda_A \Rightarrow \rho(M)=\rho(I-\vartheta A)=\max\{|1-\vartheta\lambda_{max}(A)|,|1-\vartheta\lambda_{min}(A)|\}.
[/mm]
wobei [mm] \lambda_A [/mm] ein Eigenwert von A ist. Damit [mm] $\rho(M)<1$ [/mm] gilt, muss also gelten:
[mm] \vartheta\lambda_{max}(A)<2 [/mm] und [mm] \vartheta\lambda_{min}(A)>0.
[/mm]
Daraus folgt dann zusammen: [mm] $0<\vartheta<\bruch{2}{\lambda_{max}(A)}$.
[/mm]
Die optimale Konvergenzrate beträgt [mm] \vartheta_{opt}=\bruch{2}{\lambda_{max}+\lambda_{min}} [/mm] woraus sich dann ergibt: [mm] \rho(M_{\vartheta_{opt}})=\bruch{\lambda_{max}-\lambda_{min}}{\lambda_{max}+\lambda_{min}}.
[/mm]
Jakobi-Verfahren
Hier teilt man A auf in eine linke untere Dreiecksmatrix L, eine Diagonalmatrix D und eine rechte obere Dreiecksmatrix R:
$A=L+D+R$.
Man wählt: [mm] $M=I-D^{-1}A=-D^{-1}(R+L)$
[/mm]
Damit ergibt sich: [mm] x^{k+1}=x^k-D^{-1}(Ax^k-b).
[/mm]
Oder für die einzelnen Komponenten von [mm] x^{k+1}:
[/mm]
[mm] x_i^{k+1}=\bruch{1}{a_{ii}}(b_i-\summe_{j\not= i}a_{ij}x_j^{k}) [/mm]
Das Jakobi-Verfahren konvergiert, falls die Matrix A strikt diagonaldominant ist, falls also gilt: [mm] $|a_{ii}|>\summe_{j\not= i}|a_{ij}| \; \forall [/mm] i$.
Gauß-Seidel-Verfahren
Die Aufteilung bleibt wie beim Jakobi-Verfahren: $A=L+D+R$.
Man wählt: [mm] $M=I-(D+L)^{-1}A=-(D+L)^{-1}R$
[/mm]
Daraus ergibt sich: [mm] x^{k+1}=x^{k}-(D+L)^{-1}(Ax^k-b)
[/mm]
Oder für die einzelnen Komponenten:
[mm] x_i^{k+1}=\bruch{1}{a_{ii}}(b_i-\summe_{j=1}^{i-1}a_{ij}x_j^{k+1}-\summe_{j={i+1}}^na_{ij}x_j^k) [/mm]
Das heißt, im Gegensatz zum Jakobi-Verfahren, nimmt man hier die bereits "neu" (also im k+1-ten Schritt) berechneten Werte der Komponenten bis [mm] x_{i-1}. [/mm] Die weiteren muss man ja erst noch berechnen, deswegen muss man dort immer noch die Werte aus dem k-ten Schritt nehmen.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
