Schurkomplement

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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 - C A^{-1} B\,

heißt Schur-Komplement von A in M.

Interpretation als Ergebnis der Gaußelimination[Bearbeiten]

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 \\ -C A^{-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:

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

Daher kann die Inverse von M aus der Inversen von A und seines Schur-Komplements S berechnet werden:

\left(\begin{matrix} A & B \\ C & D \end{matrix}\right)^{-1} = \left(\begin{matrix} A^{-1} + A^{-1} B S^{-1} C A^{-1} & -A^{-1} B S^{-1} \\ -S^{-1} C A^{-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 \\ -C A^{-1} & I_m \end{matrix}\right).

Eigenschaften[Bearbeiten]

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-Komplent von M1 * M2 bezeichnet, das in entsprechender Weise wie für M_1,M_2 gebildet wird, gilt, dass das Schur-Komplement des Produkt gleich dem Produkt der Schur-Komplemente ist:  S_* = S_1 * S_2

Anwendung bei der Lösung linearer Gleichungssysteme[Bearbeiten]

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

A x = 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_{\textrm{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[Bearbeiten]

Literatur[Bearbeiten]