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

<math>M=\left(\begin{matrix} A & B \\ C & D \end{matrix}\right)</math>.

Dabei sei A eine <math>n \times n</math>-, B eine <math>n \times m</math>-, C eine <math>m \times n</math>- und D eine <math>m \times m</math>-Matrix. Des Weiteren sei vorausgesetzt, dass A invertierbar ist.

Die Matrix

<math>S = D - C A^{-1} B\,</math>

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 <math>(2 \times 2)</math>-Blockmatrix <math>M</math> entspricht der Multiplikation von links mit der Matrix

<math>L=\left(\begin{matrix} I_n & 0 \\ -C A^{-1} & I_m \end{matrix}\right),</math>

wobei <math>I_n</math> und <math>I_m</math> die <math>(n \times n)</math>- bzw. <math>(m \times m)</math>-Einheitsmatrizen bezeichnen. Das Schur-Komplement erscheint dann im unteren, rechten Block des Matrizenprodukts:

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

Daher kann die Inverse von <math>M</math> aus der Inversen von <math>A</math> und von seinem Schur-Komplement <math>S</math> berechnet werden:

<math>\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)</math>

oder auch

<math>\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).</math>

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 <math>M_1</math> und <math>M_2</math> mit den Teilmatrizen <math>A_1,B_1,C_1,D_1</math> bzw. <math>A_2,B_2,C_2,D_2</math> seien <math>S_1</math> und <math>S_2</math> die entsprechenden Schur-Komplemente von <math>A_1</math> in <math>M_1</math>, bzw. <math>A_2</math> in <math>M_2</math>. Mit der Definition des folgenden Matrix-Produkts

<math> A * B = A (A+B)^{-1} B </math> und wenn <math>S_*</math> das Schur-Komplement von <math>M_1 * M_2</math> bezeichnet, das in entsprechender Weise wie für <math>M_1,M_2</math> gebildet wird, gilt, dass das Schur-Komplement des Produkts gleich dem Produkt der Schur-Komplemente ist: <math> S_* = S_1 * S_2 </math>

Anwendung bei der Lösung linearer Gleichungssysteme

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

<math>\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)</math>

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:

<math>Ax + By = f \, </math>

<math>Cx + Dy = g \, </math>

Multiplikation der ersten Gleichung von links mit <math>-C A^{-1}</math> und Addition zur zweiten Gleichung liefert

<math>(D-C A^{-1} B) y = g - C A^{-1} f.\,</math>

Wenn man also A und S invertieren kann, dann kann man diese Gleichung nach y auflösen und dann

<math>A x = f - By\,</math>

berechnen, um die Lösung <math>(x, y)</math> des ursprünglichen Problems zu erhalten.

Die Lösung eines <math>(n+m) \times (n+m)</math>-Systems reduziert sich damit auf die Lösung eines <math>n \times n</math>- und eines <math>m \times m</math>-Systems.

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

| {{#if: {{#if: ||1}} {{#if: k_wQTpdWvW0C ||1}} | <0|&pg={{#if:|RA{{{Band}}}-}}PA268|&pg=268}}{{#if:|&q=}}#v=onepage|{{#if:|&pg=|}}{{#if:|&q=}}}}{{#if:|q=%7B%7B%7BSuchbegriff%7D%7D%7D}}|{{#if:|q=%7B%7B%7BSuchbegriff%7D%7D%7D}}}} {{#if:|{{#invoke:WLink|getEscapedTitle|{{{Linktext}}}}}|eingeschränkte Vorschau}}{{#if:|| in der Google-Buchsuche}}{{#ifeq:|US|-USA}}{{#if: k_wQTpdWvW0C |{{#invoke: Vorlage:GoogleBook|fine |id=k_wQTpdWvW0C |errN=Parameter „BuchID“ hat falsche Länge |errC=Parameter „BuchID“ enthält ungültige Zeichen |errH=# in der „BuchID“ |errP=Parameterzuweisungen in der „BuchID“ |class=editoronly |cat={{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Google Buch}} |template= Vorlage:Google Buch}} }} | {{#ifeq: 0 | 0 | }}}} | {{#ifeq: 0 | 0 | }}}}{{#invoke:TemplatePar|check |all= |opt= Suchbegriff= BuchID= Seite= Band= SeitenID= Hervorhebung= Linktext= Land= KeinText= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Google Buch}} |template= Vorlage:Google Buch |format= }}{{#if:|{{#if:{{#invoke:WLink|isBracketedLink|{{{Linktext}}}}}|}}}}).