[WS] Lineare Gleichungssysteme 3 - Iterative Verfahren

05.07.2007, 01:11

tigerbine

[WS] Lineare Gleichungssysteme 3 - Iterative Verfahren

Gliederung

7. Iterative Verfahren / Splitting Verfahren

Präkonditionieren / Splitten

Richardson-Iteration

Gesamtschrittverfahren ( oder Jacobi-Verfahren)

Einzelschrittverfahren (oder Gauß-Seidel-Verfahren)

SOR-Verfahren (David Young)

Konvergenzsatz für GSV und ESV und Fehlerabschätzung

Beweise des Konvergenzsatzes für GSV und ESV

05.07.2007, 01:24

tigerbine

Auf diesen Beitrag antworten »

7. Iterative Verfahren
Im Workshop [WS] Lineare Gleichungssysteme 2 - LR-Zerlegungen sind Verfahren vorgestellt worden, die theoretisch in endlich vielen Schritten die exakte Lösung des LGS Ax=b liefern oder zeigen, dass A singulär ist. Bei der Durchführung der Verfahren auf dem Rechner wird aber i.A. schon die Eingabe mit gewissen Ungenauigkeiten behaftet sein. Vergleiche hierzu die Konditionen eines LGS [Workshop - Lineare Gleichungssysteme 1]

Ein nächster Punkt ist, dass man alle Eliminationsschritte ausführen muss, um überhaupt eine Lösung(snäherung) zu erhalten. Deswegen soll in diesem Workshop ein anderer Weg vorgestellt werden. Zum einen werden Verfahren gesucht, die nach kürzerer Rechenzeit wieder beendet werden können und, die eine Näherungslösung als Eingabe akzeptieren und als Ausgabe eine verbesserte Näherungslösung liefern (Iterationsverfahren)

Die Konvergenzuntersuchung werden uns auf den Fixpunktsatz von Banach führen, daher ist ein Blick in den [WS] Fixpunktiterationen empfohlen.

05.07.2007, 02:37

tigerbine

Auf diesen Beitrag antworten »

7a. Präkonditionieren / Splitten
Mit der Kondition einer Matrix hatten wir ja bereits einen Verstärkungsfaktor für den Eingabefehler von b kennengelernt. Ein Ansatz wäre also zu versuchen anstatt des LGS Ax = b ein besser konditioniertes zu lösen.

Sei $\begin{eqnarray*} P \in \mathbb R^{n \times n} \end{eqnarray*}$ eine reguläre Matrix. Man nennt sie den Linkspräkonditionierer.

$\begin{eqnarray*} Ax &&= b \\P^{-1}Ax &&= P^{-1}b \\ P^{-1}Ax + x -x &&= P^{-1}b \\ x && = P^{-1}b + x - P^{-1}Ax \\ x &&= P^{-1}b + (I-P^{-1}A)x \end{eqnarray*}$

Damit kann man nun die Iterationsvorschriften aufstellen:

$\begin{eqnarray*} x^{(k+1)}= (I-P^{-1}A)x^{(k)} + P^{-1}b \end{eqnarray*}$
$\begin{eqnarray*} Px^{(k+1)}=(P-A)x^{(k)} + b \end{eqnarray*}$

Hier soll (2) verwendet werden. Zur Beurteilung der Konvergenz wird man jedoch die Darstellung (1) benötigen. Ebenso hätte man die Darstellungen auf folgende Weise erhalten können. Wegen des "Aufsplitten" der Matrix A nennt man die Verfahren daher auch Splitting Verfahren:

$\begin{eqnarray*} Ax&& = b \\ Px + Ax - Px &&= b \\ Px + (A-P)x &&= b \\ x &&=P^{-1}(P-A)x + P^{-1}b \\ x&&=(I-P^{-1}A)x + P^{-1}b \end{eqnarray*}$

Der beste Linkskonditionierer ist offensichtlich $\begin{eqnarray*} P=A \end{eqnarray*}$ . In diesem Fall erhält man unabhängig von $\begin{eqnarray*} x^{(0)} \end{eqnarray*}$ in einem Schritt die Lösung. Diese Wahl (Invertierung von A) ist i.a. Natürlich zu aufwendig. Dennoch ist es daher nahe liegend, P so zu wählen, dass $\begin{eqnarray*} P^{-1}A \end{eqnarray*}$ die Einheitsmatrix in einem gewissen Sinne approximiert. Dabei sollen folgende Regeln beachtet werden:

Das Gleichungssystem (2) muss arithmetisch einfach lösbar sein
Die Iterierten $\begin{eqnarray*} x^{(k)} \end{eqnarray*}$ müssen bei jeder Wahl von $\begin{eqnarray*} x^{(0)} \end{eqnarray*}$ (möglichst schnell) gegen die Lösung von Ax=b konvergieren, d.h. $\begin{eqnarray*} \lim_{k \to \infty} ||x^{(k)} - x||_2 = 0 \end{eqnarray*}$

Es wird die Annahme gemacht, dass A durch Zeilen. bzw. Spaltenvertauschungen so umgeordnet worden sei, daß kein Hauptdiagonalelement Null ist (ist dies nicht möglich, so ist A singulär).

Zur Beschreibung von möglichen Präkonditionieren verwendet man die folgenden regulären Matrizen:

$\begin{eqnarray*} A_L:=(l_{ij}) \text{ mit } l_{ij}:= \begin{cases} a_{ij} & i \geq j, \\0& \text{sonst} \end{cases}, \text{ Bsp. } A_L=\begin{pmatrix} a_{11} & 0 \\ a_{21} & a_{22}\end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} A_R:=(r_{ij}) \text{ mit } r_{ij}:= \begin{cases} a_{ij}& i \leq j, \\0 & \text{sonst} \end{cases}, \text{ Bsp. } A_R=\begin{pmatrix} a_{11} & a_{12} \\ 0 & a_{22} \end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} \text{diag}(A):=(d_{ij}) \text{ mit } d_{ij}:= \begin{cases} d_{ij}& i = j, \\0 & \text{sonst} \end{cases}, \text{ Bsp. } \text{diag}(A)=\begin{pmatrix} a_{11} & 0 \\ 0 & a_{22}\end{pmatrix} \end{eqnarray*}$

05.07.2007, 13:15

tigerbine

Auf diesen Beitrag antworten »

7b. Richardson-Iteration
Hier gilt:

$\begin{eqnarray*} P =I \end{eqnarray*}$
$\begin{eqnarray*} x^{(k+1)}=(I-A)x^{(k)} + b \end{eqnarray*}$

05.07.2007, 13:34

tigerbine

Auf diesen Beitrag antworten »

7c. Gesamtschrittverfahren ( oder Jacobi-Verfahren)
Hier gilt:

$\begin{eqnarray*} P =\text{diag}(A) \end{eqnarray*}$
$\begin{eqnarray*} Px^{(k+1)}=(P-A)x^{(k)} + b \end{eqnarray*}$
$\begin{eqnarray*} \begin{pmatrix}a_{11} &&0\\&\ddots&\\0&&a_{nn} \end{pmatrix} \begin{pmatrix}x_1\\\vdots\\x_n \end{pmatrix}^{(k+1)}= \begin{pmatrix} 0 &-a_{12} &\hdots & -a_{1n} \\-a_{21} &0& \ddots &\vdots \\ \vdots & \ddots & \ddots&- a_{n-1n}\\-a_{n1} & \hdots &-a_{nn-1}&0\end{pmatrix}\begin{pmatrix}x_1 \\ \vdots \\ x_n \end{pmatrix}^{(k)}+\begin{pmatrix} b_1 \\ \vdots \\ b_n\end{pmatrix} \end{eqnarray*}$

Liest man die Rekursionsvorschrift Zeilenweise aus, erhält man:

$\begin{eqnarray*} a_{ii}x_i^{(k+1)} = -\sum_{j=1}^{i-1} a_{ij}x_j^{(k)} - \sum_{j=i+1}^{n} a_{ij}x_j^{(k)} + b_i\quad \forall~i =1,...,n \end{eqnarray*}$

Man benötigt also für einen Eintrag $\begin{eqnarray*} x_i^{(k+1)} \end{eqnarray*}$ des neuen Vektors alle Einträge $\begin{eqnarray*} x_j^{(k)} \end{eqnarray*}$ das alten Vektors $\begin{eqnarray*} x^{(k)} \end{eqnarray*}$ . Deswegen nennt man das Verfahren auch Gesamtschrittverfahren, da die verbesserten Werte erst nach einem Gesamtschritt (n-Einzelschritte) zum Tragen kommen.

05.07.2007, 13:52

tigerbine

Auf diesen Beitrag antworten »

7d. Einzelschrittverfahren (oder Gauß-Seidel-Verfahren)
Hier gilt:

$\begin{eqnarray*} P=A_L \end{eqnarray*}$
$\begin{eqnarray*} \begin{pmatrix}a_{11} &&0 \\\vdots &\ddots& \\ a_{n1}&\hdots & a_{nn}\end{pmatrix} \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} ^{(k+1)}= \begin{pmatrix} 0 & -a_{12} & \hdots & -a_{1n} \\ \vdots &\ddots && \vdots \\ &&\ddots&-a_{n-1n}\\0&\hdots &&0 \end{pmatrix}\begin{pmatrix}x_1 \\ \vdots \\ x_n \end{pmatrix}^{(k)}+\begin{pmatrix} b_1 \\ \vdots \\ b_n \end{pmatrix} \end{eqnarray*}$

Liest man die Rekursionsvorschrift Zeilenweise aus, und stellt um, erhält man:

$\begin{eqnarray*} a_{ii}x_i^{(k+1)} = -\sum_{j=1}^{i-1} a_{ij}x_j^{(k+1)} - \sum_{j=i+1}^{n} a_{ij}x_j^{(k)} + b_i\quad \forall~i =1,...,n \end{eqnarray*}$

Hier fließen also in die Berechnung von $\begin{eqnarray*} x_i^{(k+1)} \end{eqnarray*}$ alle bis dahin schon verbesserten Werte $\begin{eqnarray*} x_j^{(k+1)} \end{eqnarray*}$ ein. Da also eine Verbesserung in jedem Schritt erfolgt, nennt man das Verfahren auch Einzelschrittverfahren.

05.07.2007, 14:16

tigerbine

Auf diesen Beitrag antworten »

7e. SOR-Verfahren (David Young)
Hier gilt:

$\begin{eqnarray*} P=A_L - (1-\frac{1}{\omega})\cdot diag(A) \end{eqnarray*}$
$\begin{eqnarray*} \begin{pmatrix}\frac{1}{\omega}\cdot a_{11} &&&0 \\a_{21}&\ddots & & & \\ \vdots &\ddots& \\ a_{n1}&\hdots &a_{nn-1} & \frac{1}{\omega}\cdot a_{nn}\end{pmatrix} \begin{pmatrix} x_1 \\ \\ \vdots \\ x_n \end{pmatrix} ^{(k+1)}= \begin{pmatrix} (\frac{1}{\omega}-1)\cdot a_{11} & -a_{12} & \hdots & -a_{1n} \\ \vdots &\ddots && \vdots \\ &&\ddots&-a_{n-1n}\\0&\hdots &&(\frac{1}{\omega}-1)\cdot a_{nn} \end{pmatrix}\begin{pmatrix}x_1 \\ \vdots \\ x_n \end{pmatrix}^{(k)}+\begin{pmatrix} b_1 \\ \vdots \\ b_n \end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} \omega = 1 \Rightarrow \text{Gauß-Seidel-Verfahren} \end{eqnarray*}$

Successive OverRelaxation ist definiert für beliebige Parameter $\begin{eqnarray*} \omega \neq 0 \end{eqnarray*}$ . Der Name entstand dadurch, weil sich für die zuerst untersuchten (positiv definiten) Matrizen $\begin{eqnarray*} \omega > 1 \end{eqnarray*}$ als geeignete Wahl herausgestellt hat.

05.07.2007, 14:28

tigerbine

Auf diesen Beitrag antworten »

7f. Konvergenzsatz für GSV und ESV und Fehlerabschätzung (Starkes Zeilensummenkriterium)
Für die Matrix A gelte (ebentuell nach Zeilen- Spaltenvertauschung)

$\begin{eqnarray*} \rho:=\max_{i=1,...,n}~\sum_{k=1 \atop k \neq i}^{n}| \frac{a_{ik}}{a_{ii}}|~<1 \end{eqnarray*}$

Eine andere Schreibweise des Kriteriums wäre:

$\begin{eqnarray*} \sum_{k=1 \atop k \neq i}^n~|a_{ik}| < |a_{ii}| \quad \forall~i=1,..,n \end{eqnarray*}$

D.h. die Matrix A ist strikt zeilendiagonal dominant.

Dann gilt:

Das lineare Gleichungssystem Ax=b ist regulär, also eindeutig lösbar.
Die vom GSV und ESV erzeugte folge $\begin{eqnarray*} x^{(k)} \end{eqnarray*}$ konvergiert für jeden Startpunkt $\begin{eqnarray*} x^{(0)} \end{eqnarray*}$ gegen die theoretische Lösung x.
Der Abstand eines Folgengliedes $\begin{eqnarray*} x^{(k)} \end{eqnarray*}$ von der Lösung x ist abschätzbar durch:

$\begin{eqnarray*} \max_{i=1,...,n}|x_i^{(k)}-x| \leq \frac{\rho^k}{1-\rho} \cdot \max_{i=1,...,n} | x_i^{(1)}-x_i^{(0)}| \end{eqnarray*}$

Eine Aussage ob GSV oder ESV schneller konvergiert, läßt sich im Allgemeinen nicht treffen. Die Verfahren konvergieren umso besser, je kleiner (mind. < 1) der Spektralradius der Iterationsmatrix M ist.

05.07.2007, 16:24

tigerbine

Auf diesen Beitrag antworten »

7g. Beweise des Konvergenssatzes für GSV und ESV
Lehrer

Querverweis: [Workshop - Fixpunktiterationen]

Starkes Zeilensummenkriterium für das GSV

Aus der strikten Diagonaldominanz von A folgt zunächst schon einmal

$\begin{eqnarray*} a_{ii} \neq 0~\forall i=1,...,n \end{eqnarray*}$

Dies sichert die Durchführbarkeit des GSV. Dieses hatten wir wie folgt aufgestellt:

Zitat:

Damit kann man nun die Iterationsvorschriften aufstellen:

1. $\begin{eqnarray*} x^{(k+1)}= (I-P^{-1}A)x^{(k)} + P^{-1}b \end{eqnarray*}$

2. $\begin{eqnarray*} Px^{(k+1)}=(P-A)x^{(k)} + b \end{eqnarray*}$

3. $\begin{eqnarray*} P = \text{diag}(A) \end{eqnarray*}$

Es ergibt sich damit aus (1) und durch Darstellung von A als Summe dreier Matrizen (unteres Dreieck, Diagonale, oberes Dreieck):

$\begin{eqnarray*} A= P+ L + R \end{eqnarray*}$

$\begin{eqnarray*} x^{(k+1)} &&= (I-P^{-1}A)x^{(k)}+P^{-1}b<br /> &&=\Bigl( I-P^{-1}(P+L+R) \Bigr) x^{(k)} + P^{-1}b <br /> && = -P^{-1}(L+R)x^{(k)} + P^{-1}b \end{eqnarray*}$

Somit lautet die Iterationsmatrix M des GSV (Jacobi-Verfahrens):

$\begin{eqnarray*} M_J &&=(I-P^{-1}A) = -P^{-1}(L+R) \\&& = -\begin{pmatrix} \frac{1}{a_{11}} & & 0 \\ &\ddots & \\ 0&& \frac{1}{a_{nn}}\end{pmatrix} \begin{pmatrix}0 & a_{12} &\hdots &a_{1n} \\ a_{21} & & \ddots &\vdots \\\vdots & \ddots &&a_{n-1,n} \\a_{n1}&\hdots&a_{n,n-1}&0 \end{pmatrix} \end{eqnarray*}$

Wählen wir als induzierte Matrixnorm die Zeilensummennorm, so erhalten wir:

$\begin{eqnarray*} ||M_J||_{\infty} = ||I-P^{-1}A||_{\infty} = \max_{i=1,...,n}~\frac{1}{|a_{ii}|} \cdot \sum_{j=1 \atop j \neq i}^n~|a_{ij}|< 1 \end{eqnarray*}$

Damit folgt die Konvergenz aus [Workshop - Fixpunktiterationen]

Starkes Zeilensummenkriterium für das ESV

Aus der strikten Diagonaldominanz von A folgt zunächst schon einmal

$\begin{eqnarray*} a_{ii} \neq 0~\forall i=1,...,n \end{eqnarray*}$

Dies sichert die Durchführbarkeit des ESV. Dieses hatten wir wie folgt aufgestellt:

Zitat:

Die Iterationsmatrix des ESV(Gauss-Seidel-Verfahren) hat dann also die folgende Gestalt:

$\begin{eqnarray*} M_{GS} &&= (I-P^{-1}A) = - (A_L)^{-1} R \\&&=-\begin{pmatrix}a_{11} &&0 \\\vdots &\ddots& \\ a_{n1}&\hdots & a_{nn}\end{pmatrix}^{-1} \begin{pmatrix} 0 & a_{12} & \hdots & a_{1n} \\ \vdots &\ddots && \vdots \\ &&\ddots&a_{n-1,n}\\0&\hdots &&0 \end{pmatrix} \end{eqnarray*}$

Gemäß Definition der Zeilensummennorm gilt:

$\begin{eqnarray*} ||M_{GS}||_{\infty} = \max_{||x||_{\infty} = 1}~||M_{GS}x||_{\infty} \end{eqnarray*}$

Sei daher ein $\begin{eqnarray*} x \in \mathbb R^n,~||x||_{\infty}=1 \end{eqnarray*}$ beliebig gegeben. Aus der Definition der Iterationsmatrix folgt für $\begin{eqnarray*} y:=M_{GS}x \end{eqnarray*}$ mit der Darstellung 2:

$\begin{eqnarray*} \begin{pmatrix}a_{11} &&0 \\\vdots &\ddots& \\ a_{n1}&\hdots & a_{nn}\end{pmatrix} \begin{pmatrix} y_1 \\ \vdots \\y_n \end{pmatrix} =- \begin{pmatrix} 0 & a_{12} & \hdots & a_{1n} \\ \vdots &\ddots && \vdots \\ &&\ddots&a_{n-1,n}\\0&\hdots &&0 \end{pmatrix} \begin{pmatrix} x_1 \\ \vdots \\x_n\end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} y_i = \frac{1}{a_{ii}} \cdot \Bigl(-\sum_{j=1}^{i-1}~a_{ij}y_j-\sum_{j=i+1} ^n~a_{ij}x_j \Bigr) \quad \forall i=1,..,n \end{eqnarray*}$

Nun soll gezeigt werden, dass gilt:

$\begin{eqnarray*} |y_i| \leq \kappa :=||M_J||_{\infty} \end{eqnarray*}$

Dies geschieht durch Induktion. Für i=1 gilt:

$\begin{eqnarray*} |y_1| \leq \frac{1}{a_{11}} \Bigl( \sum_{j=2}^{n}~|a_{1j}| \cdot |x_j|| \Bigr) \leq \frac{1}{|a_{11}|}~|a_{1j}| \cdot \underbrace{||x||_{\infty}}_{=1} \leq ||M_J||_{\infty} = \kappa \end{eqnarray*}$

Gilt nun bereits $\begin{eqnarray*} |y_i| \leq \kappa \end{eqnarray*}$ für j=1,...,i-1, so folgt:

$\begin{eqnarray*} |y_i| && \leq \frac{1}{|a_{ii}|} \Bigl( \sum_{j=1}^{i-1}~|a_{ij}| \cdot \underbrace{|y_j|}_{\leq \kappa} +\sum_{j=i+1} ^n~|a_{ij}| \cdot \underbrace{|x_j|}_{\leq ||x||_{\infty}} \Bigr) \\&& \frac{1}{|a_{ii}|} \Bigl( \sum_{j=1}^{i-1}~|a_{ij}| \cdot \underbrace{\kappa}_{<1} +\sum_{j=i+1} ^n~|a_{ij}| \cdot \underbrace{||x_j||_{\infty}}_{=1} \Bigr) \\ && \leq \frac{1}{|a_{11}|} \Bigl(\sum_{j=1}^{i-1}~|a_{ij}|+ \sum_{j=i+1} ^n~|a_{ij}|\Bigr) \\&& \leq ||M_j||_{\infty} \\&&= \kappa \\&& < 1 \end{eqnarray*}$

Somit ist $\begin{eqnarray*} ||y||_{\infty} \leq \kappa \end{eqnarray*}$ und damit auch $\begin{eqnarray*} ||M_{GS}||_{\infty} \leq \kappa \end{eqnarray*}$ , was zu zeigen war.

(Beachte hierzu die Verträglichkeit der Norm) $\begin{eqnarray*} \Box \end{eqnarray*}$

16.08.2007, 13:56

tigerbine

Auf diesen Beitrag antworten »

Ausblick
Mit der Lösung zum Problem Ax=b äquivalenter Probleme beschäftigt sich der nächste Workshop.

Neue Frage »

Antworten »

[WS] Lineare Gleichungssysteme 3 - Iterative Verfahren

Verwandte Themen