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

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

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

Die Matrix

S = D − C A − 1 B {\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 ( 2 × 2 ) {\displaystyle (2\times 2)} -Blockmatrix M {\displaystyle M} entspricht der Multiplikation von links mit der Matrix

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

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

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

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

( A B C D ) − 1 = ( A − 1 + A − 1 B S − 1 C A − 1 − A − 1 B S − 1 − S − 1 C A − 1 S − 1 ) {\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

( A B C D ) − 1 = ( I n − A − 1 B 0 I m ) ( A − 1 0 0 S − 1 ) ( I n 0 − C A − 1 I m ) . {\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 M 1 {\displaystyle M_{1}} und M 2 {\displaystyle M_{2}} mit den Teilmatrizen A 1 , B 1 , C 1 , D 1 {\displaystyle A_{1},B_{1},C_{1},D_{1}} bzw. A 2 , B 2 , C 2 , D 2 {\displaystyle A_{2},B_{2},C_{2},D_{2}} seien S 1 {\displaystyle S_{1}} und S 2 {\displaystyle S_{2}} die entsprechenden Schur-Komplemente von A 1 {\displaystyle A_{1}} in M 1 {\displaystyle M_{1}} , bzw. A 2 {\displaystyle A_{2}} in M 2 {\displaystyle M_{2}} . Mit der Definition des folgenden Matrix-Produkts

A ∗ B = A ( A + B ) − 1 B {\displaystyle A*B=A(A+B)^{-1}B} und wenn S ∗ {\displaystyle S_{*}} das Schur-Komplement von M 1 ∗ M 2 {\displaystyle M_{1}*M_{2}} bezeichnet, das in entsprechender Weise wie für M 1 , M 2 {\displaystyle 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 {\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

( A B C D ) ( x y ) = ( f g ) {\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:

A x + B y = f {\displaystyle Ax+By=f\,}
C x + D y = g {\displaystyle Cx+Dy=g\,}

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

( D − C A − 1 B ) y = g − C A − 1 f . {\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

A x = f − B y {\displaystyle Ax=f-By\,}

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

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

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