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 ${\displaystyle (n+m)\times (n+m)}$-Matrix, die aus vier Teilblöcken zusammengesetzt ist:

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

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

Die Matrix

${\displaystyle 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 ${\displaystyle (2\times 2)}$-Blockmatrix ${\displaystyle M}$ entspricht der Multiplikation von links mit der Matrix

${\displaystyle L=\left({\begin{matrix}I_{n}&0\\-CA^{-1}&I_{m}\end{matrix}}\right),}$

wobei ${\displaystyle I_{n}}$ und ${\displaystyle I_{m}}$ die ${\displaystyle (n\times n)}$- bzw. ${\displaystyle (m\times m)}$-Einheitsmatrizen bezeichnen. Das Schur-Komplement erscheint dann im unteren, rechten Block des Matrizenprodukts:

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

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

${\displaystyle \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

${\displaystyle \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 ${\displaystyle M_{1}}$ und ${\displaystyle M_{2}}$ mit den Teilmatrizen ${\displaystyle A_{1},B_{1},C_{1},D_{1}}$ bzw. ${\displaystyle A_{2},B_{2},C_{2},D_{2}}$ seien ${\displaystyle S_{1}}$ und ${\displaystyle S_{2}}$ die entsprechenden Schur-Komplemente von ${\displaystyle A_{1}}$ in ${\displaystyle M_{1}}$, bzw. ${\displaystyle A_{2}}$ in ${\displaystyle M_{2}}$. Mit der Definition des folgenden Matrix-Produkts

${\displaystyle A*B=A(A+B)^{-1}B}$ und wenn ${\displaystyle S_{*}}$ das Schur-Komplement von ${\displaystyle M_{1}*M_{2}}$ bezeichnet, das in entsprechender Weise wie für ${\displaystyle M_{1},M_{2}}$ gebildet wird, gilt, dass das Schur-Komplement des Produkts gleich dem Produkt der Schur-Komplemente ist: ${\displaystyle S_{*}=S_{1}*S_{2}}$

Anwendung bei der Lösung linearer Gleichungssysteme

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

${\displaystyle \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:

${\displaystyle Ax+By=f\,}$

${\displaystyle Cx+Dy=g\,}$

Multiplikation der ersten Gleichung von links mit ${\displaystyle -CA^{-1}}$ und Addition zur zweiten Gleichung liefert

${\displaystyle (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

${\displaystyle Ax=f-By\,}$

berechnen, um die Lösung ${\displaystyle (x,y)}$ des ursprünglichen Problems zu erhalten.

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

Eine wichtige Bemerkung in diesem Zusammenhang ist die Tatsache, dass die inverse Matrix ${\displaystyle 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 ${\displaystyle A^{-1}}$ auf die Vektoren ${\displaystyle f}$ und, im Laufe der iterativen Lösung von ${\displaystyle (D-CA^{-1}B)y=g-CA^{-1}f}$, auf die vorherige Lösung ${\displaystyle 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 (eingeschränkte Vorschau in der Google-Buchsuche).