imported>TiMauzi: TiMauzi verschob die Seite Schurkomplement nach Schur-Komplement und überschrieb dabei eine Weiterleitung

2019-09-15T18:12:25Z

TiMauzi verschob die Seite Schurkomplement nach Schur-Komplement und überschrieb dabei eine Weiterleitung

Neue Seite

In der [[Lineare Algebra|linearen Algebra]] bezeichnet das '''Schur-Komplement''' eine [[Matrix (Mathematik)|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'' [[Reguläre Matrix|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ßsches Eliminationsverfahren|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>-[[Einheitsmatrix|Einheitsmatrizen]] bezeichnen. Das Schur-Komplement erscheint dann im unteren, rechten Block des [[Matrizenprodukt]]s:
:<math>L M = \left(\begin{matrix} A & B \\ 0 & D - C A^{-1} B \end{matrix}\right).</math>

Daher kann die [[Inverse Matrix|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'' [[Symmetrische Matrix|symmetrisch]] ist, ist ''M'' dann und nur dann [[Definitheit|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 [[Untermatrix|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 [[Lineares Gleichungssystem|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 [[iteratives Verfahren|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ünnbesetzte Matrix|dünn besetzten Matrizen]] ist dadurch eine sehr [[Effizienz (Informatik)|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 ({{Google Buch|BuchID=k_wQTpdWvW0C|Seite=268}}).

[[Kategorie:Lineare Algebra]]

Schur-Komplement - Versionsgeschichte

imported>TiMauzi: TiMauzi verschob die Seite Schurkomplement nach Schur-Komplement und überschrieb dabei eine Weiterleitung