Schur-Komplement

In der linearen Algebra bezeichnet das Schur-Komplement eine Matrix, die sich aus den einzelnen Blöcken einer größeren Matrix berechnet. Das Schur-Komplement ist nach Issai Schur benannt.

Definition

Sei M eine $(n+m) \times (n+m)$-Matrix, die aus vier Teilblöcken zusammengesetzt ist:

$M=\left(\begin{matrix} A & B \\ C & D \end{matrix}\right)$.

Dabei sei A eine $n \times n$-, B eine $n \times m$-, C eine $m \times n$- und D eine $m \times m$-Matrix. Des Weiteren sei vorausgesetzt, dass A invertierbar ist.

Die Matrix

$S = D - C A^{-1} B\,$

heißt Schur-Komplement von A in M.

Interpretation als Ergebnis der Gaußelimination

Das Schur-Komplement lässt sich als Ergebnis eines Schritts des Gaußschen Eliminationsverfahrens auf Ebene der Matrixblöcke interpretieren: Die formale Anwendung der Gaußelimination auf die $2 \times 2$-Blockmatrix M entspricht der Multiplikation von links mit der Matrix

$L=\left(\begin{matrix} I_n & 0 \\ -C A^{-1} & I_m \end{matrix}\right),$

wobei I_n und I_m die $n \times n$ bzw. $m \times m$ Einheitsmatrizen bezeichnen. Das Schur-Komplement erscheint dann im unteren, rechten Block der Produktmatrix:

$L M = \left(\begin{matrix} A & B \\ 0 & -C A^{-1} B + D \end{matrix}\right).$

Daher kann die Inverse von M aus der Inversen von A und seines Schur-Komplements S berechnet werden:

$\left(\begin{matrix} A & B \\ C & D \end{matrix}\right)^{-1} = \left(\begin{matrix} A^{-1} + A^{-1} B S^{-1} C A^{-1} & -A^{-1} B S^{-1} \\ -S^{-1} C A^{-1} & S^{-1} \end{matrix}\right)$

oder auch

$\left(\begin{matrix} A & B \\ C & D \end{matrix}\right)^{-1} = \left(\begin{matrix} I_n & -A^{-1} B \\ 0 & I_m \end{matrix}\right) \left(\begin{matrix} A^{-1} & 0 \\ 0 & S^{-1} \end{matrix}\right) \left(\begin{matrix} I_n & 0 \\ -C A^{-1} & I_m \end{matrix}\right).$

Eigenschaften

Wenn M symmetrisch und positiv definit ist, dann ist es auch S.

Für zwei invertierbare Matrizen gleicher Größe M₁ und M₂ mit den Teilmatrizen A₁,B₁,C₁,D₁ bzw. A₂,B₂,C₂,D₂ seien S₁ und S₂ die entsprechenden Schur-Komplemente von A₁ in M₁, bzw. A₂ in M₂. Mit der Definition des folgenden Matrix-Produkts

A * B = A(A + B) ^{− 1}B und wenn S _* das Schur-Komplent von M1 * M2 bezeichnet, das in entsprechender Weise wie für M₁,M₂ gebildet wird, gilt, dass das Schur-Komplement des Produkt gleich dem Produkt der Schur-Komplemente ist: S _* = S₁ * S₂

Anwendung bei der Lösung linearer Gleichungssysteme

Das Schur-Komplement kann zur Lösung von linearen Gleichungssystemen der Form

$\left(\begin{matrix} A & B \\ C & D \end{matrix}\right) \left(\begin{matrix} x \\ y \end{matrix}\right) = \left(\begin{matrix} f \\ g \end{matrix}\right)$

eingesetzt werden. Dabei bezeichnen x und f Vektoren der Länge n und y und g Vektoren der Länge m.

Multiplikation der ersten Gleichung von links mit − CA ^{− 1} und Addition zur zweiten Gleichung liefert

$(D-C A^{-1} B) y = g - C A^{-1} f.\,$

Wenn man also A und S invertieren kann, dann kann man diese Gleichung für y lösen und dann

$A x = f - By\,$

berechnen, um die Lösung (x,y) des ursprünglichen Problems zu erhalten.

Die Lösung eines $(n+m) \times (n+m)$-Systems reduziert sich damit auf die Lösung eines $n \times n$- und eines $m \times m$-Systems.

Eine wichtige Bemerkung in diesem Zusammenhang ist die Tatsache, dass die inverse Matrix A ^{− 1} in manchen iterativen numerischen Algorithmen wie Krylov-Unterraum-Verfahren nicht explizit gebildet werden muss. Wie eine genauere Betrachtung der zu lösenden Gleichungssysteme zeigt, wird nur die Wirkung von A ^{− 1} auf die Vektoren f und, im Laufe der iterativen Lösung von (D − CA ^{− 1}B)y = g − CA ^{− 1}f, auf die vorherige Lösung y_alt benötigt, sodass die Bildung der Inversen als Lösung eines linearen Gleichungssystems aufgefasst werden kann. Gerade bei dünn besetzten Matrizen ist dadurch eine sehr effiziente Lösung möglich.

Siehe auch

• Sattelpunktproblem