Schur-Komplement

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Schurkomplement)
Zur Navigation springen Zur Suche springen

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.

Sei M eine -Matrix, die aus vier Teilblöcken zusammengesetzt ist:

.

Dabei sei A eine -, B eine -, C eine - und D eine -Matrix. Des Weiteren sei vorausgesetzt, dass A invertierbar ist.

Die Matrix

heißt Schur-Komplement von A in M.

Interpretation als Ergebnis der Gaußelimination

[Bearbeiten | Quelltext 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 -Blockmatrix entspricht der Multiplikation von links mit der Matrix

wobei und die - bzw. -Einheitsmatrizen bezeichnen. Das Schur-Komplement erscheint dann im unteren, rechten Block des Matrizenprodukts:

Daher kann die Inverse von aus der Inversen von und von seinem Schur-Komplement berechnet werden:

oder auch

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 und mit den Teilmatrizen bzw. seien und die entsprechenden Schur-Komplemente von in , bzw. in . Mit der Definition des folgenden Matrix-Produkts

und wenn das Schur-Komplement von bezeichnet, das in entsprechender Weise wie für gebildet wird, gilt, dass das Schur-Komplement des Produkts gleich dem Produkt der Schur-Komplemente ist:

Anwendung bei der Lösung linearer Gleichungssysteme

[Bearbeiten | Quelltext bearbeiten]

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

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:

Multiplikation der ersten Gleichung von links mit und Addition zur zweiten Gleichung liefert

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

berechnen, um die Lösung des ursprünglichen Problems zu erhalten.

Die Lösung eines -Systems reduziert sich damit auf die Lösung eines - und eines -Systems.

Eine wichtige Bemerkung in diesem Zusammenhang ist die Tatsache, dass die inverse Matrix 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 auf die Vektoren und, im Laufe der iterativen Lösung von , auf die vorherige Lösung 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.