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{array}{cc}A& B\\ C& D\end{array}\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{array}{cc}{I}_n& 0\\ -C{A}^{-1}& I_m\end{array}\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{array}{cc}A& B\\ 0& D-C{A}^{-1}B\end{array}\right).$

Daher kann die Inverse von $M$ aus der Inversen von $A$ und von seinem Schur-Komplement $S$ berechnet werden:

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

oder auch

${\left(\begin{array}{cc}A& B\\ C& D\end{array}\right)}^{-1}=\left(\begin{array}{cc}{I}_n& -A^{-1}B\\ 0& I_m\end{array}\right)\left(\begin{array}{cc}{A}^{-1}& 0\\ 0& S^{-1}\end{array}\right)\left(\begin{array}{cc}{I}_n& 0\\ -C{A}^{-1}& I_m\end{array}\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{array}{cc}A& B\\ C& D\end{array}\right)\left(\begin{array}{c}x\\ y\end{array}\right)=\left(\begin{array}{c}f\\ g\end{array}\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 $-C{A}^{-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 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 $f$ und, im Laufe der iterativen Lösung von $(D-C{A}^{-1}B)y=g-C{A}^{-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, S. 268f (Vorlage:Google Buch).