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 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 des Matrizenprodukts:

$LM=\left({\begin{matrix}A&B\\0&D-CA^{{-1}}B\end{matrix}}\right).$

Daher kann die Inverse von aus der Inversen von und von seinem Schur-Komplement 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

Unter der Voraussetzung, dass M symmetrisch ist, ist M dann und nur dann positiv definit, wenn A und das Schur-Komplement S positiv definit sind.

Analog zur oben angegebenen Definition lässt sich auch das Schur-Komplement zum Block D bilden.

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-Komplement von $M_{1}*M_{2}$ bezeichnet, das in entsprechender Weise wie für $M_{1},M_{2}$ gebildet wird, gilt, dass das Schur-Komplement des Produkts 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. Ausgeschrieben lautet dieses Gleichungssystem:

$Ax+By=f\,$

$Cx+Dy=g\,$

Multiplikation der ersten 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 nach y auflö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 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 und, im Laufe der iterativen Lösung von $(D-CA^{{-1}}B)y=g-CA^{{-1}}f$ , auf die vorherige Lösung $y_{\text{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

Literatur

Edgar Brunner, Ullrich Munzel: Nichtparametrische Datenanalyse. Springer, Berlin 2002, ISBN 3-540-43375-9.

Basierend auf einem Artikel in:

Wikipedia.de