Advent, Advent, 1 Monat weihnachtliche Laufzeit geschenkt.

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

Textversion des Videos

Transkript Lineare Gleichungssysteme mit Cholesky-Zerlegung lösen

Hallo, hier ist Christoph und in diesem Video erkläre ich euch, wie man mithilfe eine Cholesky-Zerlegung, ein lineares Gleichungssystem löst. Gegeben haben wir also ein lineares Gleichungssystem Ax = b und sollen dies mithilfe der Cholesky-Zerlegung von A lösen. Zur Erinnerung: Warum funktioniert dieses nur, wenn A positiv formuliert ist? Richtig, weil A nur dann eine Cholesky-Zerlegung besitzt. Wenn A also eine Cholesky-Zerlegung besitzt, das heißt A sich als Produkt aus ST und S zerlegen lässt, können wir nun schreiben: STSx=b. Definieren wir Sx nun als y, erhalten wir das Gleichungssystem STy=b. Die Vorgehensweise ist dabei die Folgende: Zuerst lösen wir das eben erhaltene Gleichungssystem STy=b und erhalten so den Vektor y. Dieser war ja definiert als S×x. Also können wir anschließend das Gleichungssystem Sx=y lösen und erhalten damit unseren Lösungsvektor x. Kommen wir nun zum ersten Beispiel: Wir haben also eine Matrix A und einen Vektor b gegeben und sollen mithilfe der Cholesky-Zerlegung von A das Gleichungssystem Ax=b lösen. Für dieses Beispiel gehen wir nun davon aus, dass wir die Cholesky-Zerlegung von A schon haben. Die Cholesky-Zerlegung genau dieser Matrix habe ich in meinem anderen Video zur Cholesky-Zerlegung berechnet. Als ersten Schritt müssen wir - wie eben gesehen - also das Gleichungssystem  ST×y=b lösen. Dazu schreiben wir uns die Matrix ST hin, rechts daneben den Vektor b und ordnen die Komponenten von y den entsprechenden Spalten von S zu, y1 also der ersten Spalte von S, y2 der zweiten Spalte und y3 der dritten Spalte. Ich denke die meisten von euch kennen diese Darstellung zur Lösung von linearen Gleichungssystemen. Da S eine Dreiecksmatrix ist - ST also auch - ist die Lösung dieses Gleichungssystems ziemlich einfach. Da S die untere Dreiecksmatrix ist, beginnen wir dieses Gleichungssystem von oben nach unten zu lösen. In der ersten Zeile hat ST nämlich nur einen Eintrag ungleich 0. Damit erhalten wir hier direkt y1=2. Mit diesen schon gefundenen y1 ergibt sich aus der zweiten Zeile: 2×y1, also 2×2+1×y2+0×y3=13. Wir können also wiederum ein y, in diesem Fall y2 direkt berechnen. Aus der dritten Zeile ergibt sich dann 1×y1,also 1×2, plus 3×y2,also 3×9, plus 2×y3=41 ---> 1×2+3×9+2×y3=41 Damit erhalten wir die letzte Komponente y3. Unser Vektor y ist also 2, 9, 6. Im nächsten Schritt müssen wir nun mit unserem gefundenen Vektor y das Gleichungssystem Sx=y lösen. Dazu schreiben wir das Gleichungssystem wieder in der Notation von eben hin. Im Gegensatz zu eben, verwenden wir jetzt hier die Matrix S statt S transponiert, haben also eine obere Dreiecksmatrix. Daher beginnen wir von unten das Gleichungssystem zu lösen. Berechnen uns also zunächst x3 aus der dritten Zeile. Aus der zweiten Zeile folgt nun 0×x1+1×x2+3×x3, also 3×3, gleich 9. X2 ergibt sich also zu 0. Aus der ersten Zeile ergibt sich nun, wiederum unter Verwendung der schon gefundenen Werte für x2 und x3, x1=-1. Somit ist unser Vektor x=-1, 0, 3, die gesuchte Lösung unseres linearen Gleichungssystems Ax=b und wir sind fertig. Wir wollen nun aber unser gefundenes Ergebnis einmal kontrollieren. Dies ist auch ganz einfach. Unsere gefundene Lösung für x soll ja das Gleichungssystem A×x=b lösen. Rechnen wir also einfach mal nach, was das Produkt A×x eigentlich ergibt. Wie wir sehen, ergibt dies den Vektor 2, 13 ,41. Dies ist der in der Aufgabe gegebene Vektor b. Somit haben wir richtig gerechnet. Um ein bisschen Routine in den Ablauf reinzukriegen, wollen wir uns nun noch ein zweites Beispiel angucken. Dieses Mal mit einer viel 4×4 Matrix A. Hierfür habe ich wieder eine uns schon bekannte Matrix A gewählt, nämlich die aus dem letzten Video. Dort haben wir die Cholesky-Zerlegung dieser Matrix schon berechnet. Wir können also wieder davon ausgehen, das wir diese Zerlegung schon haben und uns bleibt nur noch damit die Aufgabe das Gleichungssystem Ax=b zu lösen. Natürlich haben wir auch eine rechte Seite des Gleichungssystems b gegeben. Ich habe auch noch einmal den Ablaufplan notiert. Als Erstes lösen wir das Gleichungssystem STy=b und als Zweites das Gleichungssystem Sx=y. Wie immer schreiben wir uns also als Erstes das Gleichungssystem STy=b hin. Wieder lösen wir das Gleichungssystem zu erst von oben nach unten. Aus der ersten Zeile ergibt sich nämlich direkt y1=3. Aus der zweiten Zeile können wir dann berechnen 2×3+y2=11, woraus sich y2=5 ergibt. Ich denke ihr habt das Prinzip langsam verstanden. Die dritte Zeile ausgeschrieben und die gefundenen Lösungen für y1 und y2 eingesetzt, liefert y3=-2. Genauso erhalten wir aus der vierten Zeile y4=-4. Wir haben den Lösungsvektor y nun gefunden und können damit das nächste Gleichungssystem lösen. Dieses Gleichungssystem lautet - wer hätte das gedacht - Sx=y. Wie vorher lösen wir dieses zweite  Gleichungssystem von unten nach oben, berechnen also zu erst x4, dann x3, x2 und zum Schluss x1. Wir erhalten schließlich also die Lösung für x: x1=1, x2=-1, x3=2 und x4=-2. Wie schon bei der anderen Aufgabe, wollen wir auch hier unser Ergebnis einmal kontrollieren, indem wir die Lösung in das lineare Gleichungssystem einsetzen und das Produkt A×x berechnen. Auch hier sehen wir das genau der Vektor b rauskommt. Fassen wir nun noch mal die wichtigsten Punkte bei dem Lösen eines linearen Gleichungssystems mithilfe der Cholesky-Zerlegung zusammen. Noch einmal zur Erinnerung: Ein lineares Gleichungssystem kann man nur dann mithilfe der Cholesky-Zerlegung lösen, wenn A positiv definiert ist. Denn nur dann hat A eine Cholesky-Zerlegung. S ist eine obere Dreiecksmatrix. Wenn man A in das Produkt ST×S zerlegt, zerlegt man A also in das Produkt aus einer linken unteren Dreiecksmatrix und einer rechten oberen Dreiecksmatrix. Also das Gleiche, was man auch bei einer LR-Zerlegung tut. Die LR-Zerlegung kann aber immer berechnet werden, die Cholesky-Zerlegung wie gesagt nur, wenn A positiv definiert ist. Das Vorgehen zum Lösen des Gleichungssystems ist dann das Folgende: Zu erst wird das Gleichungssystem STy=b gelöst. Anschließend wird mit der Lösung y das Gleichungssystem Sx=y gelöst. Das Lösen dieser Gleichungssysteme funktioniert analog zum Lösen eines Gleichungssystems mithilfe der LR-Zerlegung. Wenn ihr dort also noch Übung benötigt, guckt euch ruhig das Video zur Lösung eines linearen Gleichungssystems mithilfe der LR-Zerlegung an. Das war es von mir in diesem Video. Bis bald euer Christoph.

Informationen zum Video
1 Kommentar
  1. Default

    Welchen Zweck verfolgt man mit der Cholesky Zerlegung?

    Von Numerologica, vor mehr als 2 Jahren