Splitting-Verfahren

In der numerischen Mathematik sind Splitting-Verfahren klassische iterative Verfahren zum Lösen linearer Gleichungssysteme ${\displaystyle Ax=b}$ mit einer Matrix ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ und rechter Seite ${\displaystyle 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

${\displaystyle A=B+(A-B),}$

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

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

Daraus ergibt sich die Fixpunktgleichung

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

Setzt man

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

wobei ${\displaystyle I}$ die Einheitsmatrix bezeichnet, so folgt die Fixpunktiteration.

Iterationsvorschrift

Das zugehörige Splitting-Verfahren lautet:

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

   ${\displaystyle x_{k}\leftarrow Mx_{k-1}+B^{-1}b.}$

Konvergenz

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

${\displaystyle e_{k}=M^{k}e_{0}.}$

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

${\displaystyle \rho (M)<1.}$

Dabei bezeichnet ${\displaystyle \sigma (M)}$ das Spektrum von ${\displaystyle M}$, also die Menge der Eigenwerte von ${\displaystyle M}$, und ${\displaystyle \rho (M):=\max _{\lambda \in \sigma (M)}|\lambda |}$ den Spektralradius von ${\displaystyle 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 ${\displaystyle B}$ und ${\displaystyle A}$ nur wenig unterscheiden, kann man mit dem Störungslemma zeigen, dass auch der Spektralradius von ${\displaystyle M}$ klein ist.

Übersicht klassischer Splitting-Verfahren

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

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

Aufwand und praktische Bedeutung

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

• Schnelle Konvergenz wird erreicht, wenn ${\displaystyle B}$ die Matrix ${\displaystyle A}$ gut approximiert.
• Geringe Kosten pro Iteration erhält man, wenn ${\displaystyle 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.

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.