Splitting-Verfahren
# Splitting-Verfahren

In der numerischen Mathematik sind Splitting-Verfahren 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, falls die Genauigkeit hoch genug ist.

## Beschreibung

Das Verfahren ergibt sich über ein Splitting der Systemmatrix $A=B+(A-B)$ mit einer invertierbaren Matrix $B\in \mathbb {C} ^{n\times n}$.

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

Daraus erhält man die Fixpunktgleichung

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

Mit $M=B^{-1}(B-A)=I-B^{-1}A$, wobei $I$ die Einheitsmatrix bezeichnet, ergibt sich die Fixpunktiteration

* Wähle einen Startvektor $x_{0}\in \mathbb {C} ^{n}$.
* Setze $x_{k}=Mx_{k-1}+B^{-1}b=(I-B^{-1}A)x_{k-1}+B^{-1}b$.

Man kann die Iteration abbrechen, falls die Norm des Residuums $r_{k}=b-Ax_{k}$ eine vorgegebene Fehlerschranke unterschreitet. Das Verfahren konvergiert genau dann, wenn der Spektralradius der Matrix $M$ kleiner 1 ist. Mit Hilfe des banachschen Fixpunktsatzes folgt ferner die lineare Konvergenzgeschwindigkeit der gesamten Verfahrensklasse. Je kleiner der Spektralradius ist, umso 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. Damit ergibt sich ein Gegensatz von schneller Konvergenz ($B$ approximiert $A$ sehr gut) zu geringen Kosten pro Iteration ($B$ ist einfach invertierbar). Insgesamt sind diese Verfahren für viele praktische Probleme zu langsam. Allerdings stellen sie aufgrund ihrer einfachen Anwendbarkeit gute Vorkonditionierer dar. Darüber hinaus sind viele Splitting-Verfahren als Glätter in einem Mehrgitterverfahren geeignet.

## Beispiele

* Jacobi-Verfahren: $B=\operatorname {diag} (A)$ ist die Hauptdiagonale von $A$.
* Richardson-Verfahren: $B=\tau \cdot I$ mit einem Parameter $\tau$.
* Gauß-Seidel-Verfahren: $B=D+L$ die untere linke Dreiecksmatrix + Hauptdiagonale.
* Weitere sind das SOR-Verfahren $B=(1/\omega )D+L$ und SSOR.
* eine Möglichkeit der Nachiteration für das gaußsche Eliminationsverfahren: $B=LR$.

## 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.

