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 Kap1 Theorie 3: Der Gauß-Algorithmus für lineare Gleichungssysteme

Hallo, ich bin Sergej. In diesem Video lernen wir die grundsätzliche Vorgehensweise beim Lösen linearer Gleichungssysteme. Diese Vorgehensweise heißt "der Algorithmus von Gauß" oder "das gaußsche Eliminationsverfahren". Wenn wir ein lineares Gleichungssystem haben, dann besitzt es entweder genau eine Lösung oder es besitzt keine Lösungen oder es hat unendlich viele Lösungen. In diesem Video wollen wir lernen, wie man es herausfindet, ob das Gleichungssystem lösbar ist, ob genau eine Lösung vorhanden ist oder ob keine Lösungen vorhanden sind. Wenn die Lösungen existieren, dann möchte man natürlich die Lösungen berechnen und wir lernen hier dem Grundsatz nach, wie das geht. Das ist das Programm für dieses Video und den Algorithmus von Gauß habe ich in mehrere Schritte unterteilt. Lasst uns jetzt die Einzelheiten anschauen. Im ersten Schritt soll man das lineare Gleichungssystem von der Gleichungsform - wie hier - auf die Matrixform umschreiben. Wichtig dabei sind 2 Matrizen: Erstens die sogenannte Koeffizientenmatrix. Wir schauen auf das Gleichungssystem und schreiben die rot markierten Zahlen von den Gleichungen in eine Matrix zusammen. a11 bis a1n usw. Wir schreiben das in eine Matrix zusammen und diese Matrix heißt "die Koeffizientenmatrix" und wird normalerweise mit A bezeichnet. Noch wichtiger ist die erweiterte Koeffizientenmatrix. Sie besteht einmal aus der Koeffizientenmatrix und sie wird erweitert um eine zusätzliche Spalte. Diese zusätzliche Spalte nehme ich von der rechten Seite des linearen Gleichungssystems. Also ich nehme diese frei stehenden Koeffizienten auf der rechten Seite b1, b2 bis bm und schreibe sie dann hinzu zu der Koeffizientenmatrix. Auf diese Weise ergibt sich die erweiterte Koeffizientenmatrix. Mit dieser letzteren Matrix wollen wir ganz viel anstellen. Im Schritt 2 sollen wir die erweiterte Koeffizientenmatrix des Systems auf die normierte Zeilenstufenform bringen, indem wir elementare Zeilenumformungen benutzen. Falls ihr euch nicht ganz sicher seid, was die normierte Zeilenstufenform ist, dann könnt ihr euch dafür 3 Videos in diesem Themenkreis anschauen. In einem Video - "Theorie 1" - habe ich grundsätzlich erklärt, was die Zeilenstufenform ist. Im zweiten Video habe ich gesagt, wie man die normierte Zeilenstufenform berechnet. Ins Besondere erkläre ich dort, was die elementaren Zeilenumformungen sind. Es gibt noch ein drittes Video - "Aufgabe 1". Da behandele ich ein umfangreiches Beispiel zur Berechnung der normierten Zeilenstufenform. Diese Technik muss man beherrschen, um mit dem Algorithmus von Gauß zu arbeiten. Nun möchte ich an das alles eine weitere Betrachtung anschließen. Ich möchte motivieren. Wozu braucht man denn diese normierte Zeilenstufenform und was verbirgt sich dahinter? Zur Motivation lasst uns ein einfaches Beispiel anschauen, ein lineares Gleichungssystem lösen. Motivation - löse das folgende lineare Gleichungssystem und ich nehme etwas ganz Einfaches: x+y=-1 -x+3×y=9 Wir wollen mit den fast intuitiven Methoden dieses lineare Gleichungssystem lösen. Wir sehen, oben haben wir x, unten haben wir -x. Absolut offensichtlich: Wenn wir die beiden Gleichungen addieren, dann verschwindet x. Wir eliminieren auf diese Weise x. Also tun wir das. Auf die zweite Gleichung addiere ich die erste Gleichung und bekomme das Folgende: Die erste Gleichung bleibt bestehen. Die zweite Gleichung hat die folgende Form: x+(-x)=0 y+3×y=4×y und -1+9=8 Dann teile ich die zweite Gleichung durch 4 - offensichtlich - und dann weiß ich schon, wie y aussieht. Also ich multipliziere in anderen Worten die zweite Gleichung mit dem Faktor ¼ und bekomme Folgendes: y=2 Also: 8÷4=2 Und die erste Gleichung bleibt erst einmal bestehen: x+y=-1 Ich sehe y=2, wenn ich das in die erste Gleichung einsetze, dann ergibt sich, dass x=-3 und das Gleichungssystem ist gelöst. Sehr einfache, naheliegende Schritte. Nun lasst uns die 2 Schritte durchführen, die ich euch schon empfohlen habe im Gauß-Algorithmus. Als Erstes müssen wir das Gleichungssystem von der Gleichungsform auf die Matrixform umschreiben. Tun wir das. In der ersten Gleichung haben wir die Koeffizienten 1 und 1. In der zweiten Gleichung haben wir die Koeffizienten -1 und 3. Die freien Koeffizienten sind -1 und 9. Nun wollen wir die normierte Zeilenstufenform von der erweiterten Koeffizientenmatrix berechnen. Das eine Pivotelement hier links oben ist schon vorhanden, die 1 ist da. Wir sollen unterhalb von 1 eine 0 erzeugen. Wie tun wir das? Wir addieren die erste Zeile auf die zweite Zeile. 2. Zeile plus 1. Zeile ergibt uns die folgende Matrix: Die erste Zeile bleibt stehen. 1+(-1)=0, 1+3=4 und -1+9=8. Das ist schon die Zeilenstufenform. Jetzt wollen wir die zweite Zeile noch normieren. Dazu müssen wir die zweite Zeile durch 4 teilen und wir bekommen die folgende Matrix: 1, 1, -1. 0, 1, 2. Wir sehen, dass die Berechnung der normierten Zeilenstufenform nur eine abgekürzte Schreibweise für die üblichen Manipulationen von linearen Gleichungen. Was sind die üblichen Manipulationen? Das heißt, eine Gleichung auf die andere addieren, die eine Gleichung von der Anderen subtrahieren, die Gleichung mit einer von 0 verschiedenen Zahl multiplizieren. Wir tun das in einer geeigneten Weise, sodass wir die Variablen eliminieren. Die Berechnung der normierten Zeilenstufenform ist nichts anderes, das ist einfach nur eine abgekürzte Schreibweise dafür - in der Matrixschreibweise, in der normierten Zeilenstufenform lassen wir die Variablen x und y aus. Auf die kommt es nicht wirklich an. Entscheidend sind die Koeffizienten, die vor den Variablen stehen und die manipulieren wir. Wir führen diese Zeilenumformungen auf die Art und Weise, dass wir am Ende besonders bequeme Matrixformen bekommen, von denen wir die Lösung praktisch schon ablesen können. Fazit: Das verbirgt sich hinter der Zeilenstufenform, dazu braucht man sie. Aber nicht alle Beispiele, nicht alle Gleichungssysteme, sind so einfach wie dieses Gleichungssystem. Hier sieht man es schon. Für dieses Gleichungssystem braucht man keinen Gauß-Algorithmus. Um allgemeinere Gleichungssysteme zu lösen, da brauchen wir ein bisschen mehr Maschinerie und die sehen wir in den nächsten Schritten. Im dritten Schritt müssen wir den Rang der Koeffizientenmatrix und den Rang der erweiterten Koeffizientenmatrix ermitteln. Wie tut man das? Wir schauen uns die normierte Zeilenstufenform an. Erst einmal verdecken wir die letzte Spalte, die habe ich hier rot markiert, und zählen die Einsen, zählen die Pivot-Einsen. Also hier haben wir eine Pivot-1, hier haben wir eine Pivot-1 usw., mit der letzten Spalte verdeckt. Die Anzahl der Pivot-Einsen ist dann der Rang der Koeffizientenmatrix, dann notieren wir eine Zahl. Dann geben wir die letzte Spalte der erweiterten Koeffizientenmatrix frei und zählen wieder die Einsen und die Anzahl der Pivot-Einsen ist dann der Rang der erweiterten Koeffizientenmatrix. Es ist völlig klar, dass wir hier nur 2 Situationen haben können. Erstens: Wir haben dann in den letzten 2 Spalten der normierten Zeilenstufenform eine durchgehende Stufe. Wenn wir hier eine durchgehende Stufe haben, dann ist der Rang der erweiterten Koeffizientenmatrix gleich dem Rang der Koeffizientenmatrix und wir haben die Gleichheit. Rang(A)=Rang(A|B) Oder es kann vorkommen, dass in der letzten Spalte, in der rot markierten Spalte, eine zusätzliche Stufe auftritt. Wenn das der Fall ist, dann ist der Rang der erweiterten Koeffizientenmatrix um 1 höher: Rang(A)+1=Rang der erweiterten Koeffizientenmatrix Also wir berechnen die beiden Zahlen, Rang(A) und Rang (A|B), und zur Information: Es kann nur einer der beiden Fälle vorkommen. Im Schritt 4 sollen wir entscheiden, ob das System Lösungen hat und wenn ja, wie viele. Das ist ganz einfach, wenn wir die Informationen über den Rang haben. Das ist eine Fallunterscheidung. Wenn der Rang der Koeffizientenmatrix echt kleiner ist als der Rang der erweiterten Koeffizientenmatrix, dann hat das System keine Lösungen. Ergänzend dazu sage ich, dass in diesem Fall die normierte Zeilenstufenform der erweiterten Koeffizientenmatrix folgende merkwürdige Zeile hat. Also in diesem Fall tritt die folgende Zeile auf. Auf der linken Seite stehen lauter Nullen und nach dem Strich steht die 1. Wenn eine solche Zeile vorkommt, dann bedeutet das automatisch, dass die Ränge verschieden sind und das Gleichungssystem keine Lösungen hat. Ansonsten, wenn die Ränge gleich sind, dann hat das System Lösungen - auf jeden Fall. Die Frage ist: Wie viele? Da ist eine weitere Fallunterscheidung. Wir sollen den Rang der Koeffizientenmatrix mit der Anzahl der Spalten der Koeffizientenmatrix vergleichen. Anzahl der Spalten ist zugleich die Anzahl der Variablen im Gleichungssystem. Wenn die beiden Größen gleich sind, dann hat das System genau eine Lösung. Wenn aber der Rang der Koeffizientenmatrix kleiner als die Anzahl der Spalten der Koeffizientenmatrix ist, dann hat das System unendlich viele Lösungen. Und wenn das System keine Lösungen hat, dann hören wir einfach nur auf. Das ist das Ergebnis: Das System hat keine Lösungen. Wenn das System Lösungen besitzt, dann sind wir daran interessiert, die Lösungen zu berechnen. Im Fall, wenn das lineare Gleichungssystem genau eine Lösung hat, wird die normierte Zeilenstufenform der erweiterten Koeffizientenmatrix so aussehen. Was haben wir da genauer? Wir haben links oben einen quadratischen Block, auf der Diagonalen des quadratischen Blocks stehen die Einsen, die Pivot-Einsen, unterhalb von Einsen stehen immer die Nullen, oberhalb von Einsen stehen irgendwelche Zahlen. Außerdem kann es optional einen unteren Block geben. Der besteht aus den Nullen. Der kann vorhanden sein, muss es aber nicht. Wenn wir das haben, ist die Frage: Wie berechnen wir die eindeutig bestimmte Lösung des linearen Gleichungssystems? Dazu sollen wir durch elementare Zeilenumformungen erreichen, dass oberhalb von Pivot-Einsen die Nullen stehen. Wir sollen alles oberhalb von Pivot-Einsen eliminieren. Wie tut man das? Zum Beispiel, um dieses Element zu eliminieren, sollen wir von der ersten Zeile das entsprechende Vielfache der zweiten Zeile abziehen. So machen wir das dann mit jeder 1. Also oberhalb von jeder 1 können wir dann die Nullen erzeugen. Wenn wir damit fertig sind, dann haben wir die Matrix in dieser Form. Auf der rechten Seite, hier in dieser Spalte, werden sich dann bestimmte Zahlen herauskristallisieren. Das sind genau die Lösungen unseres Gleichungssystems. Wenn wir die Matrix auf diese Form gebracht haben, dann können wir die Lösung schon sofort daraus ablesen. Wenn wir das haben, dann folgt daraus, dass: x1=c1 - Ich lese dann diese Zeile ab. x2=c2 usw. xn=cn So ermitteln wir die Lösung in dem Fall, wo das System eindeutig bestimmte Lösungen hat. Im Fall, wenn das Gleichungssystem unendlich viele Lösungen hat, wird die normierte Zeilenstufenform der erweiterten Koeffizientenmatrix des Systems typischerweise so aussehen. In diesem Fall wird es garantiert vorkommen, dass es eine Stufe gibt, die mehrere Spalten breit ist - 2, 3 oder mehr Spalten breit. Wie gewohnt: Der Nullenblock links kann vorhanden sein, muss es aber nicht und der Nullenblock hier unten kann vorhanden sein, muss es aber nicht. So wird die normierte Zeilenstufenform aussehen. Und jetzt kommt die spannende Frage: Wie schreibe ich diese unendlich vielen Lösungen auf? Das ist sehr wichtig, wird relevant für viele Themen weiter in diesem Kurs "Lineare Algebra". Die Vorgehensweise hier ist ein wenig umständlich. Da müsste ich viel zu viel Rotation einführen und viel die Tafel vollschreiben, um dann die allgemeine Vorgehensweise in diesem Fall zu präsentieren. Deswegen habe ich mich so entschieden, dass ich dazu ein typisches Beispiel behandele. Wer daran interessiert ist, diesen Fall zu betrachten, der schaue sich bitte das Video mit der Aufgabe 4 "Lineares Gleichungssystem mit unendlich vielen Lösungen" an. Dort präsentiere ich an einem konkreten Beispiel die universelle Vorgehensweise in diesem Fall. Wenn man dieses Beispiel gesehen hat und verstanden hat, dann hat man alles verstanden. Gut, das ist der Algorithmus von Gauß. Wichtig ist, dass man die normierte Zeilenstufenform berechnen kann. Wichtig ist, dass man von der normierten Zeilenstufenform den Rang der Matrix ablesen kann. Wenn man diese Informationen hat, kann man anhand vom Algorithmus von Gauß entscheiden, ob das System lösbar ist, wie viele Lösungen es hat und man kann dann diese Lösungen auch berechnen. Ich hoffe, das war hilfreich. Vielen Dank fürs Zuschauen.

Informationen zum Video
3 Kommentare
  1. Default

    gut - ich hatte Mühe, dem Tempo zu folgen

    Von Sperling Ploen, vor mehr als 3 Jahren
  2. Default

    klar deutlich perfekt

    Von Denisa500, vor etwa 4 Jahren
  3. Default

    Vielen Dank zum wiederholten Male für die Klarheit,die Verständlichkeit, die hervorragende Grafik der Tafelbilder und die präzisen Erklärungen!

    Von Schilli, vor mehr als 4 Jahren