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 ABCD 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 CA 1B 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 In0 CA 1Im displaystyle L left begin matrix I n amp 0 CA 1 amp I m end matrix right nbsp wobei In displaystyle I n nbsp und Im 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 LM AB0D CA 1B 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 ABCD 1 A 1 A 1BS 1CA 1 A 1BS 1 S 1CA 1S 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 ABCD 1 In A 1B0Im A 100S 1 In0 CA 1Im 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 M1 displaystyle M 1 nbsp und M2 displaystyle M 2 nbsp mit den Teilmatrizen A1 B1 C1 D1 displaystyle A 1 B 1 C 1 D 1 nbsp bzw A2 B2 C2 D2 displaystyle A 2 B 2 C 2 D 2 nbsp seien S1 displaystyle S 1 nbsp und S2 displaystyle S 2 nbsp die entsprechenden Schur Komplemente von A1 displaystyle A 1 nbsp in M1 displaystyle M 1 nbsp bzw A2 displaystyle A 2 nbsp in M2 displaystyle M 2 nbsp Mit der Definition des folgenden Matrix Produkts A B A A B 1B displaystyle A B A A B 1 B nbsp und wenn S displaystyle S nbsp das Schur Komplement von M1 M2 displaystyle M 1 M 2 nbsp bezeichnet das in entsprechender Weise wie fur M1 M2 displaystyle M 1 M 2 nbsp gebildet wird gilt dass das Schur Komplement des Produkts gleich dem Produkt der Schur Komplemente ist S S1 S2 displaystyle S S 1 S 2 nbsp Anwendung bei der Losung linearer Gleichungssysteme BearbeitenDas Schur Komplement kann zur Losung von linearen Gleichungssystemen der Form ABCD xy fg 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 Ax By f displaystyle Ax By f nbsp Cx Dy g displaystyle Cx Dy g nbsp Multiplikation der ersten Gleichung von links mit CA 1 displaystyle CA 1 nbsp und Addition zur zweiten Gleichung liefert D CA 1B y g CA 1f 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 Ax f By 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 CA 1B y g CA 1f displaystyle D CA 1 B y g CA 1 f nbsp auf die vorherige Losung yalt 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