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-CA^{-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\\-CA^{-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:

$LM=\left({\begin{matrix}A&B\\0&-CA^{-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}BS^{-1}CA^{-1}&-A^{-1}BS^{-1}\\-S^{-1}CA^{-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\\-CA^{-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_{1}$ und $M_{2}$ mit den Teilmatrizen $A_{1},B_{1},C_{1},D_{1}$ bzw $A_{2},B_{2},C_{2},D_{2}$ seien $S_{1}$ und $S_{2}$ die entsprechenden Schur-Komplemente von $A_{1}$ in $M_{1}$, bzw $A_{2}$ in $M_{2}$. 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_{1},M_{2}$ gebildet wird, gilt, dass das Schur-Komplement des Produkt gleich dem Produkt der Schur-Komplemente ist

$S_{*}=S_{1}*S_{2}$

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 erste Gleichung von links mit $-CA^{-1}$ und Addition zur zweiten Gleichung liefert

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

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

$Ax=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 einem iterativen numerischen Algorithmus 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_{\textrm {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.