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

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

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

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 f 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

Literatur

Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
© biancahoegel.de
Datum der letzten Änderung: Jena, den: 19.05. 2021