Advent, Advent, 1 Monat weihnachtliche Laufzeit geschenkt.

Nicht bis zur Bescherung warten, Aktion nur gültig bis zum 18.12.2016!

Cholesky-Zerlegung 12:40 min

Textversion des Videos

Transkript Cholesky-Zerlegung

Hallo, hier ist Christoph mit einem Video zur Cholesky-Zerlegung einer Matrix. Es gilt der folgende Satz: Eine Matrix hat genau dann eine Cholesky-Zerlegung, wenn sie positiv definit ist. Es geht in diesem Video nicht weiter darum, welche Eigenschaften eine positiv definite Matrix sonst noch hat, wir müssen nur eine positiv definite Matrix gegeben haben, um eine Cholesky-Zerlegung berechnen zu können. Gesucht ist nun also die Cholesky-Zerlegung von A. Die Cholesky-Zerlegung von A ist das Produkt ST×S, wobei S eine obere Dreiecksmatrix ist, die es nun zu finden gilt. Mit ST ist dabei die Transponierte der Matrix S gemeint, das heißt, die Matrix, die sich ergibt, wenn man die Elemente in S an der Hauptdiagonalen spiegelt. Die Matrix S ist per Definition eine obere Dreiecksmatrix. S transponiert also eine untere Dreiecksmatrix. Damit wird A hier in ein Produkt aus linker unterer Dreiecksmatrix und rechter oberer Dreiecksmatrix aufgeteilt. Ich möchte an dieser Stelle nur auf die Analogie zur Leerzerlegung hinweisen. Hier habe ich die Notation der Einträge der Matrix S gezielt. Der 1. Index steht dabei für die Zeile, der 2. für die Spalte. Ein allgemeines Element der Matrix S nennen wir im Folgenden Sij, wobei i die Zeile und j die Spalte angibt. Es folgen nun die beiden Formeln, die man benötigt, um eine Cholesky-Zerlegung zu berechnen. Für i=j, also Hauptdiagonalelemente gilt: Sii=\sqrt(Aii)-?über SKi², wobei K von 1 bis i-1 läuft. Aii ist dabei das i des Hauptdiagonalelements unserer Matrix A. An dieser Stelle noch ein kleiner praktischer Hinweis. Aufgrund der Wurzel in der Formel für Sii können die Hauptdiagonalelemente der Matrix S nie negativ sein. Solltet ihr also doch aus irgendeinem Grund mal ein negatives Hauptdiagonalelement in der Cholesky-Zerlegung haben, wisst ihr, dass ihr euch verrechnet habt. Für alle anderen Elemente Sij gilt: 0, wenn i>j ist, da wir es ja mit einer oberen Dreiecksmatrix zu tun haben, und sonst 1/Sii×Aij-?über SKi×SKj, wobei K auch von 1 bis i-1 läuft. Um mit diesen Formeln die Cholesky-Zerlegung berechnen zu können, muss man zeilenweise vorgehen, das heißt, Zeile für Zeile von oben nach unten berechnen. In jeder Zeile benötigen wir als Erstes das Hauptdiagonalelement. Daher bietet es sich an, jede Zeile von links nach rechts zu durchlaufen. Da die Formeln auf den ersten Blick etwas kompliziert aussehen, wollen wir uns nun am Beispiel einer 3-Kreuz-3-Matrix angucken, was diese Formeln zu bedeuten haben und für jedes Element einzeln die Formel ausschreiben. Zur besseren Übersicht habe ich die Initiierung der einzelnene Matrixeinträge noch einmal skizziert. An dieser Stelle vielleicht doch noch ein kleiner Hinweis zu positiv definiten Matrizen: Damit eine Matrix positiv definit sein kann, muss sie auf jeden Fall symmetrisch sein. Hier noch einmal die Formeln. Wir beginnen mit der 1. Zeile von links nach rechts. Da S11 ein Hauptdiagonalelement ist, brauchen wir die linke Formel für Sii. i ist dabei 1. Die Summe geht nun von K01 bis 0 und ist per Definition somit 0, da die obere Grenze kleiner ist als die untere. Es ergibt sich die Formel: \sqrt(A11-0). Somit ist S11=1. Für S12 brauchen wir nun die rechte Formel: i=1, j=2. Die Summe ist wieder 0, da sie von K=1 bis 0 geht. Übrig bleibt also nur noch 1/S11×A12. Analog gilt für S13=11/S11(A13). Die Ergebnisse der 1. Zeile habe ich nun oben links in die Matrix S eingetragen. Weiter geht's mit der 2. Zeile: Zuerst das Hauptdiagonalelement für i=2. Die Summe ist jetzt nicht mehr 0, sondern geht von K=1 bis 1, muss also für k=1 ausgewertet werden. SKi² ist dann S12². Somit ergibt sich für S22=\sqrt(A22-S12²). Genauso ist auch für S23 die Summe jetzt nicht mehr 0, sondern muss für K=1 ausgewertet werden. Es ergibt sich 1/S22×(A23-S12×S13). Wieder habe ich die Ergebnisse der 2. Zeile oben links eingetragen, da wir diese Ergebnisse der vorherigen Zeilen ja immer für die Berechnung der neuen Elemente brauchen. In der 3. Zeile müssen wir nur S33 berechnen. Wegen i=3 geht die Summe nun von K=1 bis 2, muss also für K=1 und für K=2 ausgewertet werden. Für K=1 ergibt sich S13², für K=2=S23². S33 ist somit \sqrt[A33-(S13²+S23²)]. Und schon haben wir alle Elemente unserer Matrix S berechnet. Zur Kontrolle können wir das Produkt S transponiert mal S bilden und sehen, dass wirklich die Matrix A dabei herauskommt. Anhand eines weiteren Beispiels einer 4-Kreuz-4-Matrix möchte ich euch nun die Summen in den beiden Formeln anschaulich darstellen. Hat man dieses Prinzip einmal verstanden, muss man sich nämlich nicht mehr mit den vielen Indizes herumschlagen, sondern sieht immer gleich sofort, was man zu tun hat. Die Summe in der Formel für die Hauptdiagonalelemente Sii bedeutet Folgendes: Man muss einfach alle Elemente oberhalb von Sii, also in der gleichen Spalte, quadrieren und anschließend zusammenaddieren. In der Formel für Sij ist es ein klein wenig komplizierter. Hier muss man sich sowohl die i- als auch die j-Spalte vorknöpfen und dann Zeile für Zeile die Elemente der i- und j-Spalte miteinander multiplizieren und am Ende alles zusammenaddieren. Also S1i×S1j+S2i×S2j+S3i×S3j und so weiter. Gucken wir uns das also nun an einem Beispiel mal an: Ich habe hier die Formel noch einmal notiert und von der dargestellten Matrix A sollen wir die Cholesky-Zerlegung berechnen. Im 1. Beispiel hatten wir schon gesehen, dass in der 1. Zeile die Summen immer wegfallen. Anschaulich kann man sich das so überlegen, dass es ja keine Elemente oberhalb der 1. Zeile mehr gibt. Somit vereinfacht sich die Rechnung sehr stark und S11 ist immer nur \sqrt(A11) und S1j ist immer nur A1j/S11. In unserem Fall ist die 1. Zeile der Matrix S gleich der 1. Zeile in Matrix A. Dies ist aber Zufall beziehungsweise liegt nur daran, dass A11=1 ist. Unten links notieren wir nun, was wir über die Matrix S bereits wissen. Die rechte Matrix dient im Folgenden der anschaulichen Darstellung. Wie immer beginnen wir mit dem Hauptdiagonalelement. Wir nehmen uns dazu das entsprechende Element der Matrix A, in diesem Fall die 5, und ziehen alle quadrierten Einträge der bisherigen Matrix S in der 2. Spalte davon ab. Anschließend ziehen wir daraus die Wurzel. Wir erhalten also 5-2²=1 und daraus die Wurzel, also 1. Wir berechnen nun das Element S23. Wir müssen also für jede bisher berechnete Zeile die Elemente der 2. und 3. Spalte miteinander multiplizieren und anschließend alles zusammenaddieren. In diesem Fall ist das nur 2×1. Dies ziehen wir nun von dem entsprechenden Element an der Stelle 23 in der Matrix A ab und teilen durch das gefundene Hauptdiagonalelement S22. Wir erhalten also 5-2×1 und das ganze geteilt durch 1, also 3. Dasselbe machen wir jetzt für das Element S23. Wir nehmen uns wieder das Element der Matrix A an dieser Stelle, in diesem Fall -2. Da wir jetzt bei dem Element 24 sind, müssen wir uns nur um die 2. und 4. Spalte von unserem bisherigen S angucken. Da wir erst 1 Zeile berechnet haben, haben wir in diesem Fall 2 mit -1 zu multiplizieren. Wenn wir dieses Ergebnis abziehen von dem Element A24, also der -2, erhalten wir 0. S24 ist also 0. Kommen wir zur nächsten Zeile, der 3. Zeile. Wieder berechnen wir zuerst das Hauptdiagonalelement. Dazu quadrieren wir alle bisher gefundenen Elemente in der 3. Spalte der Matrix S, also 1² und 3² und addieren diese zusammen. Das Ergebnis 10 ziehen wir wieder ab von dem Element in der Matrix A, an unserer Stelle, die wir gerade betrachten, 233. 14-10=4. Daraus die Wurzel ziehen und schon haben wir mit 2 unser Element S33 gefunden. Kommen wir also zu S34. Wir müssen uns nun also wieder die 3. und 4. Spalte von unserem bisherigen S angucken und dort Zeile für Zeile die Elemente dieser beiden Spalten multiplizieren. Also 1×-1 und 3×0. Dies zusammenaddiert und wieder von dem Element in der Matrix A abgezogen, ergibt 6. Dies teilen wir wie immer durch das Hauptdiagonalelement unserer 3. Zeile, der 2 und erhalten somit die 3. Das letzte verbleibende zu berechnende Element ist S44, wieder ein Hauptdiagonalelement. Wir müssen also nur alle bisher gefundenen Elemente in S in derselben Spalte quadrieren und zusammenaddieren. Also -1²+0²+0²+3² und das zusammenaddiert. Dann wieder abgezogen von dem Element in der Matrix A, also der 14, und die Wurzel gezogen. Wir erhalten die 2 als letztes fehlendes Element. Zum Schluss mal wieder eine kleine Zusammenfassung: A besitzt genau dann eine Cholesky-Zerlegung, also eine Matrix S, die obere Dreiecksmatrix ist, und für die gilt S transponiert ×S=A, wenn A positiv definiert ist. Dies sollte man sich für eventuell aufkommende Theoriefragen auf jeden Fall merken. Um die vorgestellten Formeln benutzen zu können, muss die Berechnung Zeile für Zeile von oben nach unten erfolgen. Das war's erst mal von meiner Seite zur Vorgehensweise bei der Berechnung der Cholesky-Zerlegung. In einem weiteren Video erkläre ich, wie man mithilfe der Cholesky-Zerlegung ein lineares Gleichungssystem löst. Bis dann, tschau - euer Christoph!

Informationen zum Video