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 Lösen linearer Gleichungssysteme mit der LR-Zerlegung

Hallo, ich bin Christoph und zeige Euch in diesem Video, wie man mit Hilfe einer LR-Zerlegung ein lineares Gleichungssystem löst. Hierbei gehen wir davon aus, dass wir eine LR-Zerlegung schon gegeben haben. Ich habe in zwei vorangegangenen Videos bereits gezeigt, wie man eine LR-Zerlegung berechnet. Gegeben ist also ein lineares Gleichungssystem Ax=b und die LR-Zerlegung der quadratischen Matrix A. Gesucht ist die Lösung des linearen Gleichungssystems, also der Vektor x. Dieser soll mit Hilfe der LR-Zerlegung von A berechnet werden. Man könnte sich jetzt fragen, warum man ein lineares Gleichungssystem mit Hilfe der LR-Zerlegung berechnet, und nicht einfach immer die Matrix A invertiert und x durch A-1×b berechnet. In der Numerik vermeidet man es, Matrizen zu invertieren. Dies ist numerisch instabil, und Eingangsfehler sowie Rundungsfehler haben eine große Auswirkung auf das Ergebnis, verfälschen es also. Daher vermeidet man auch in diesem Fall, A zu invertieren und sucht eine andere Lösung, wie in diesem Fall die LR-Zerlegung. Der Ansatz ist dabei der Folgende: Wir wissen, dass sich A als Produkt L×R schreiben lässt. Damit wird aus dem Gleichungssystem Ax=b  L×R×x=b. Definieren wir uns nun einen Vektor y=R×x, so haben wir letztendlich das Gleichungssystem L×y=b, sowie das Gleichungssystem y=R×x. Wir haben nun also zwei voneinander abhängige Gleichungssysteme. Das Vorgehen ist das Folgende: Als Erstes lösen wir das Gleichungssystem L×y=b und erhalten den Vektor y. Anschließend lösen wir das Gleichungssystem R×x=y und erhalten dadurch die gesuchte Lösung x. Das Lösen beider Gleichungssysteme ist sehr einfach, wie ihr gleich sehen werdet, da L und R Dreiecksmatrizen sind. Die Vorgehensweise beim Lösen des Gleichungssystems hängt in gewissem Maße davon ab, ob man die LR-Zerlegung mit Pivotwahl oder ohne Pivotwahl gemacht hat. Als erstes Beispiel wollen wir uns angucken, was passiert, wenn man die LR-Zerlegung ohne Pivotwahl gemacht hat. Gegeben ist also eine Matrix A und ihre LR-Zerlegung. Ich habe hier wieder die gleichen Matrizen gewählt wie schon in den anderen Videos zur LR-Zerlegung. Außerdem haben wir einen Vektor b gegeben. Als Erstes müssen wir also das Gleichungssystem L×y=b lösen. Dazu schreiben wir uns die Matrix L hin, rechts daneben den Vektor b. Und oben y1, y2 und y3, denn y1 ist der ersten Spalte von L zugeordnet, y2 der zweiten Spalte und y3 der dritten Spalte. Ich gehe davon aus, dass die meisten von euch diese Darstellung zur Lösung von linearen Gleichungssystemen kennen. Da L eine untere Dreiecksmatrix ist, ist in der ersten Zeile nur ein Eintrag von 0 verschieden. Ausgeschrieben bedeutet die erste Zeile 1×y1+0×y2+0×y3=4. y1 ist hier also die einzige Unbekannte, sodass wir diese direkt berechnen können. Nachdem wir y1 berechnet haben, können wir aus der zweiten Zeile direkt y2 berechnen. Hier haben wir nämlich 1×y1, also können wir gleich einsetzen 1×4+1×y2+0×y3=2. In der dritten Zeile ergibt sich schließlich 2×y1, also 2×4 sind 8, minus 1×y2, also -1×(-2) sind +2 plus 1×y3=7. Daraus ergibt sich y3, sodass wir den kompletten Vektor y nun haben. Der Vektor y ist also (4 -2 -3). Dieser Vektor y ist nun die rechte Seite in unserem Gleichungssystem Rx=y. Dieses schreiben wir wieder nach dem bekannten Schema auf. Links die Matrix R, rechts der Vektor y. Da R eine obere Dreiecksmatrix ist, haben wir nun in der letzten Zeile nur einen Eintrag ?0. Daher beginnen wir dieses Mal mit der Berechnung der dritten Komponente des Lösungsvektors, also x3 zuerst. Aus der letzten Zeile ergibt sich relativ einfach x3=-1. Die zweite Zeile ergibt 0×x1+2×x2+6×x3 (für x3 können wir gleich wieder die schon gefundene Lösung -1 einsetzen) gleich -2. Daraus können wir direkt x2 berechnen. Schließlich ergibt die erste Zeile 1×x1+4×x2+5×x3=4, und durch Einsetzen der Lösung für x2 und x3 x1=1. Und schon haben wir unseren Lösungsvektor x gefunden. x ist gleich (1 2 -1). Die Kontrolle ist hier relativ einfach. A×x soll ja b ergeben. Dies kann man leicht im Kopf nachrechnen, indem man A mit x multipliziert und guckt, ob b rauskommt. A×x ist in diesem Fall für die erste Zeile 1×1+4×2+5×(-1)=4. In der zweiten Zeile ergibt sich 1×1+6×2+11×(-1)=2 und in der dritten Zeile 2×1+6×2+7×(-1)=7. Dies ist genau der Vektor b mit dem wir gestartet sind. Unser Ergebnis ist also richtig. Fassen wir den Ablaufplan noch einmal zusammen: Als Erstes müssen wir das Gleichungssystem Ly=b lösen. Dies tun wir von vorne nach hinten, das heißt von oben nach unten. Wir berechnen also zuerst die erste Komponente des Vektors y, y1. Dann y2 und so weiter. Haben wir den Vektor y nun gefunden, können wir mit ihm das Gleichungssystem Rx=y lösen. Dies tun wir von hinten nach vorne, das heißt von unten nach oben. Wir können also zuerst xn berechnen, dann x(n-1) und so weiter und als letztes x1. Im nächsten Video werden wir uns anschauen, was man beim Lösen des Gleichungssystems beachten muss, wenn man die LR-Zerlegung zuvor mit Pivotwahl gemacht hat. Bis dann, Euer Christoph.  

Informationen zum Video