Splitting-Verfahren

In der numerischen Mathematik sind Splitting-Verfahren klassische iterative Verfahren zum Lösen linearer Gleichungssysteme $Ax=b$ mit einer Matrix $A\in \mathbb {C} ^{n\times n}$ und rechter Seite $b\in \mathbb {C} ^{n}.$ Im Unterschied zu direkten Verfahren nähert man sich dabei ausgehend von einer Startnäherung schrittweise der gesuchten Lösung an und bricht ab, sobald die Genauigkeit hoch genug ist.

Herleitung

Zu Beginn spalten wir die Systemmatrix auf

A=B+(A-B),

wobei $B\in \mathbb {C} ^{n\times n}$ invertierbar ist. Nun können wir das lineare Gleichungssystem äquivalent umformen

Ax=b\quad \iff \quad B^{-1}(B+(A-B))x=B^{-1}b.

Daraus ergibt sich die Fixpunktgleichung

x=B^{-1}(B-A)x+B^{-1}b.

Setzt man

M:=B^{-1}(B-A)=I-B^{-1}A,

wobei $I$ die Einheitsmatrix bezeichnet, so folgt die Fixpunktiteration.

Iterationsvorschrift

Das zugehörige Splitting-Verfahren lautet:

Wähle einen Startvektor $x_{0}\in \mathbb {C} ^{n}$ , beispielsweise $x_{0}=b$ .
Berechne iterativ für $k\in \mathbb {N}$ mit vorheriger Schätzung $x_{k-1}$ und $\;M=(I-B^{-1}A)$ den nächsten Vektor
$x_{k}\leftarrow Mx_{k-1}+B^{-1}b.$

Richardson-Iteration

Mit dem Residuum

r_{k-1}=b-Ax_{k-1}

lässt sich die Iteration schreiben als

x_{k}=x_{k-1}+B^{-1}r_{k-1},

denn $x_{k-1}+B^{-1}(b-Ax_{k-1})=(I-B^{-1}A)x_{k-1}+B^{-1}b$ .
Damit ist jedes Splitting-Verfahren dieser Form äquivalent zu einer vorkonditionierten Richardson-Iteration mit Vorkonditionierer $B$ . Für $B=I$ erhält man die klassische Richardson-Iteration.

Abbruchkriterium

Die Iteration kann abgebrochen werden, sobald die Norm des Residuums $r_{k}=b-Ax_{k}$ eine vorgegebene Fehlerschranke unterschreitet.

Konvergenz

Mit dem Fehler zu einem Fixpunkt $e_{k}:=x_{k}-x^{*}$ lässt sich der Fehler ausdrücken

e_{k}=M^{k}e_{0}.

$M^{k}\to {\textbf {0}}$ konvergiert genau dann, wenn der Spektralradius der Iterationsmatrix $M$ kleiner als $1$ ist, i.e.

\rho (M)<1.

Dabei bezeichnet $\sigma (M)$ das Spektrum von $M$ , also die Menge der Eigenwerte von $M$ , und $\rho (M):=\max _{\lambda \in \sigma (M)}|\lambda |$ den Spektralradius von $M$ .
Mit Hilfe des banachschen Fixpunktsatzes folgt außerdem die lineare Konvergenzgeschwindigkeit der gesamten Verfahrensklasse. Je kleiner der Spektralradius ist, desto schneller konvergiert das Verfahren.

Falls sich $B$ und $A$ nur wenig unterscheiden, kann man mit dem Störungslemma zeigen, dass auch der Spektralradius von $M$ klein ist.

Übersicht klassischer Splitting-Verfahren

Die klassischen Splitting-Verfahren basieren auf der Zerlegung $A=L+D+R$ , wobei $D:=\operatorname {diag} (A)$ die Diagonalmatrix, $L:=\operatorname {tril} (A,-1)$ die strikte untere Dreiecksmatrix und $R:=\operatorname {triu} (A,1)$ die strikte obere Dreiecksmatrix von $A$ bezeichnet.

Jacobi-Verfahren: $B=D$ .
Richardson-Verfahren: $B=(1/\tau )I$ mit einem Parameter $|\tau |>1$ .
Gauß-Seidel-Verfahren: $B=D+L$ .
SOR-Verfahren: $B=(1/\omega )D+L$ mit einem Relaxationsparameter $\omega \neq 0$ .
SSOR-Verfahren: symmetrisierte Variante des SOR-Verfahrens.
Eine Möglichkeit der Nachiteration für das gaußsche Eliminationsverfahren ergibt sich durch $B=L_{\mathrm {LU} }U_{\mathrm {LU} }$ , wobei $L_{\mathrm {LU} }U_{\mathrm {LU} }$ eine LU-Zerlegung von $A$ bezeichnet.

Aufwand und praktische Bedeutung

Damit ergibt sich ein Gegensatz zwischen schneller Konvergenz und geringen Kosten pro Iteration:

Schnelle Konvergenz wird erreicht, wenn $B$ die Matrix $A$ gut approximiert.
Geringe Kosten pro Iteration erhält man, wenn $B$ einfach invertierbar ist.

Insgesamt sind Splitting-Verfahren für viele praktische Probleme als eigenständige Verfahren zu langsam. Aufgrund ihrer einfachen Anwendbarkeit eignen sie sich jedoch gut als Vorkonditionierer. Darüber hinaus können viele Splitting-Verfahren als Glätter in einem Mehrgitterverfahren verwendet werden.

Modifikationen

Man unterscheidet zwischen stationären Verfahren mit konstanter Iterationsmatrix und instationären Verfahren, wo die Matrizen $M$ vom Index $i$ abhängen dürfen.

Literatur

Andreas Meister: Numerik linearer Gleichungssysteme. 2. Auflage. Vieweg, Wiesbaden 2005, ISBN 3-528-13135-7.
Christian Kanzow: Numerik linearer Gleichungssysteme. Direkte und iterative Verfahren. Springer, Berlin/Heidelberg 2005, ISBN 978-3-540-20654-5.
Wolfgang Hackbusch: Iterative Lösung großer schwachbesetzter Gleichungssysteme. 2. Auflage. Teubner, Stuttgart 1993, ISBN 3-519-12372-X.