www.wikidata.de-de.nina.az

Schur Komplement In der linearen Algebra bezeichnet das eine Matrix die sich aus den einzelnen Blöcken einer größeren Ma

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 Bearbeiten

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

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

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

Anwendung bei der Lösung linearer Gleichungssysteme 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.

Siehe auch Bearbeiten

Literatur Bearbeiten

  • Edgar Brunner, Ullrich Munzel: Nichtparametrische Datenanalyse. Springer, Berlin 2002, ISBN 3-540-43375-9, S. 268f (eingeschränkte Vorschau in der Google-Buchsuche).
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
In der linearen Algebra bezeichnet das Schur Komplement eine Matrix die sich aus den einzelnen Blocken einer grosseren Matrix berechnet Das Schur Komplement ist nach Issai Schur benannt Inhaltsverzeichnis 1 Definition 2 Interpretation als Ergebnis der Gausselimination 3 Eigenschaften 4 Anwendung bei der Losung linearer Gleichungssysteme 5 Siehe auch 6 LiteraturDefinition BearbeitenSei M eine n m n m displaystyle n m times n m nbsp Matrix die aus vier Teilblocken zusammengesetzt ist M A B C D displaystyle M left begin matrix A amp B C amp D end matrix right nbsp Dabei sei A eine n n displaystyle n times n nbsp B eine n m displaystyle n times m nbsp C eine m n displaystyle m times n nbsp und D eine m m displaystyle m times m nbsp Matrix Des Weiteren sei vorausgesetzt dass A invertierbar ist Die Matrix S D C A 1 B displaystyle S D CA 1 B nbsp heisst Schur Komplement von A in M Interpretation als Ergebnis der Gausselimination BearbeitenDas Schur Komplement lasst sich als Ergebnis eines Schritts des Gaussschen Eliminationsverfahrens auf Ebene der Matrixblocke interpretieren Die formale Anwendung der Gausselimination auf die 2 2 displaystyle 2 times 2 nbsp Blockmatrix M displaystyle M nbsp entspricht der Multiplikation von links mit der Matrix L I n 0 C A 1 I m displaystyle L left begin matrix I n amp 0 CA 1 amp I m end matrix right nbsp wobei I n displaystyle I n nbsp und I m displaystyle I m nbsp die n n displaystyle n times n nbsp bzw m m displaystyle m times m nbsp 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 amp B 0 amp D CA 1 B end matrix right nbsp Daher kann die Inverse von M displaystyle M nbsp aus der Inversen von A displaystyle A nbsp und von seinem Schur Komplement S displaystyle S nbsp 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 amp B C amp D end matrix right 1 left begin matrix A 1 A 1 BS 1 CA 1 amp A 1 BS 1 S 1 CA 1 amp S 1 end matrix right nbsp 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 amp B C amp D end matrix right 1 left begin matrix I n amp A 1 B 0 amp I m end matrix right left begin matrix A 1 amp 0 0 amp S 1 end matrix right left begin matrix I n amp 0 CA 1 amp I m end matrix right nbsp Eigenschaften BearbeitenUnter 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 lasst sich auch das Schur Komplement zum Block D bilden Fur zwei invertierbare Matrizen gleicher Grosse M 1 displaystyle M 1 nbsp und M 2 displaystyle M 2 nbsp mit den Teilmatrizen A 1 B 1 C 1 D 1 displaystyle A 1 B 1 C 1 D 1 nbsp bzw A 2 B 2 C 2 D 2 displaystyle A 2 B 2 C 2 D 2 nbsp seien S 1 displaystyle S 1 nbsp und S 2 displaystyle S 2 nbsp die entsprechenden Schur Komplemente von A 1 displaystyle A 1 nbsp in M 1 displaystyle M 1 nbsp bzw A 2 displaystyle A 2 nbsp in M 2 displaystyle M 2 nbsp Mit der Definition des folgenden Matrix Produkts A B A A B 1 B displaystyle A B A A B 1 B nbsp und wenn S displaystyle S nbsp das Schur Komplement von M 1 M 2 displaystyle M 1 M 2 nbsp bezeichnet das in entsprechender Weise wie fur M 1 M 2 displaystyle M 1 M 2 nbsp 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 nbsp Anwendung bei der Losung linearer Gleichungssysteme BearbeitenDas Schur Komplement kann zur Losung von linearen Gleichungssystemen der Form A B C D x y f g displaystyle left begin matrix A amp B C amp D end matrix right left begin matrix x y end matrix right left begin matrix f g end matrix right nbsp eingesetzt werden Dabei bezeichnen x und f Vektoren der Lange n und y und g Vektoren der Lange m Ausgeschrieben lautet dieses Gleichungssystem A x B y f displaystyle Ax By f nbsp C x D y g displaystyle Cx Dy g nbsp Multiplikation der ersten Gleichung von links mit C A 1 displaystyle CA 1 nbsp 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 nbsp Wenn man also A und S invertieren kann dann kann man diese Gleichung nach y auflosen und dann A x f B y displaystyle Ax f By nbsp berechnen um die Losung x y displaystyle x y nbsp des ursprunglichen Problems zu erhalten Die Losung eines n m n m displaystyle n m times n m nbsp Systems reduziert sich damit auf die Losung eines n n displaystyle n times n nbsp und eines m m displaystyle m times m nbsp Systems Eine wichtige Bemerkung in diesem Zusammenhang ist die Tatsache dass die inverse Matrix A 1 displaystyle A 1 nbsp in manchen iterativen numerischen Algorithmen wie Krylov Unterraum Verfahren nicht explizit gebildet werden muss Wie eine genauere Betrachtung der zu losenden Gleichungssysteme zeigt wird nur die Wirkung von A 1 displaystyle A 1 nbsp auf die Vektoren f displaystyle f nbsp und im Laufe der iterativen Losung von D C A 1 B y g C A 1 f displaystyle D CA 1 B y g CA 1 f nbsp auf die vorherige Losung y alt displaystyle y text alt nbsp benotigt sodass die Bildung der Inversen als Losung eines linearen Gleichungssystems aufgefasst werden kann Gerade bei dunn besetzten Matrizen ist dadurch eine sehr effiziente Losung moglich Siehe auch BearbeitenSattelpunktproblemLiteratur BearbeitenEdgar Brunner Ullrich Munzel Nichtparametrische Datenanalyse Springer Berlin 2002 ISBN 3 540 43375 9 S 268f eingeschrankte Vorschau in der Google Buchsuche Abgerufen von https de wikipedia org w index php title Schur Komplement amp oldid 192282347