Splitting-Verfahren

In der numerischen Mathematik sind Splitting-Verfahren klassische iterative Verfahren zum Lösen linearer Gleichungssysteme Ax=b mit einer Matrix A∈ℂn×n und rechter Seite b∈ℂ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∈ℂn×n invertierbar ist. Nun können wir das lineare Gleichungssystem äquivalent umformen

Ax=b⟺B−1(B+(A−B))x=B−1b.

Daraus ergibt sich die Fixpunktgleichung

x=B−1(B−A)x+B−1b.

Setzt man

M:=B−1(B−A)=I−B−1A,

wobei I die Einheitsmatrix bezeichnet, so folgt die Fixpunktiteration.

Iterationsvorschrift

Das zugehörige Splitting-Verfahren lautet:

  1. Wähle einen Startvektor x0∈ℂn, beispielsweise x0=b.
  2. Berechne iterativ für k∈ℕ mit vorheriger Schätzung xk−1 und M=(I−B−1A) den nächsten Vektor
    xk←Mxk−1+B−1b.

Richardson-Iteration

Mit dem Residuum

rk−1=b−Axk−1

lässt sich die Iteration schreiben als

xk=xk−1+B−1rk−1,

denn xk−1+B−1(b−Axk−1)=(I−B−1A)xk−1+B−1b.
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 rk=b−Axk eine vorgegebene Fehlerschranke unterschreitet.

Konvergenz

Mit dem Fehler zu einem Fixpunkt ek:=xk−x∗ lässt sich der Fehler ausdrücken

ek=Mke0.

Mk→𝟎 konvergiert genau dann, wenn der Spektralradius der Iterationsmatrix M kleiner als 1 ist, i.e.

ρ(M)<1.

Dabei bezeichnet σ(M) das Spektrum von M, also die Menge der Eigenwerte von M, und ρ(M):=maxλ∈σ(M)|λ| 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:=diag⁡(A) die Diagonalmatrix, L:=tril⁡(A,−1) die strikte untere Dreiecksmatrix und R:=triu⁡(A,1) die strikte obere Dreiecksmatrix von A bezeichnet.

Aufwand und praktische Bedeutung

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

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.