Das Gausche-Eliminationsverfahren, das kann Gleichungssysteme verarzten, bei denen die Zahl der Gleichungen nicht gleich der Zahl der Unbekannten ist. Hat auch kein Problem damit, wenn es nicht genau eine Lösung gibt oder wenn es gar keine Lösung gibt, wenn es unendlich viele Lösungen gibt.

Und der Rechenaufwand und die Rundungsfehler, wenn man es bleibt, wenn man es geschickt macht, im Rahmen. Es gibt noch geschickte Verfahren, aber das Gausche-Eliminationsverfahren ist das erste, was man tatsächlich auch mal auf größere Probleme loslassen kann.

Ich führe das am Beispiel vor. Das Gausche-Eliminationsverfahren steht hier im Skript. Ein Gleichungssystem mit drei Gleichungen, vier Unbekannten.

Also etwas, was das Kramerverfahren schon gar nicht kann. Upsala, da geht es 4, plus 4y minus 3z plus 4w ist gleich 7. 3x, 2y minus z plus 6w ist gleich 3.

Und hier habe ich minus 5x plus 5y plus 2z gleich 5. So, vier unbekannte, drei Gleichungen.

Das Kramerverfahren wird da schon das Handtuch werfen, weil eine Determinante mit drei Zeilen, vier Spalten nicht hinhaut. Das Gausche-Eliminationsverfahren kann das.

Das Ziel ist nun folgendes. Erster Schritt. Da steht auch noch ein Text, das ist so viel zu schreiben, dass ich selbst getippt habe. Im ersten Schritt versucht man eine obere Dreiecksform hinzukriegen. Eine Matrix in einer oberen Dreiecksform.

Ich würde sagen, es soll nur auf der Diagonal oder darüber was stehen. Das wäre die Diagonale. Es soll nur auf der Diagonal und darüber was stehen. Nicht unter der Diagonal. Das nennt sich obere Dreiecksform. Also ich möchte das so umformen, dass es so aussieht, wie es im Strip steht.

Die erste Gleichung kann sogar so bleiben an dem hier. 14 minus 3z plus 4w ist gleich 7. Und die anderen Gleichungen möchte ich jetzt so umbauen, dass alles unter der Diagonalen rausfliegt.

Die hier stehen unter der Diagonal für gleich vor, wie man das machen kann. Das ist die Elimination. Ich möchte aus der zweiten Gleichung das x eliminieren. Ich möchte in der zweiten Gleichung nur so etwas haben, wie irgendwas mal y plus irgendwas mal z plus irgendwas mal w ist gleich irgendwas.

So möchte ich die zweite Gleichung umformen. Das mache ich gleich einfach mit der ersten und der zweiten Gleichung zusammen. Ich nehme von der ersten Gleichung das richtige Vielfache auf, die zweite Gleichung, dann ist das 3x da weg. Da steht ein Loch. Ähnlich kriege ich gleich die dritte Gleichung, klein geschlagen.

Im ersten Schritt nehme ich nur den ersten weg. Und dann wird es noch einen weiteren Schritt geben, indem ich auch den wegnehme. Und aus der dritten Gleichung wird sowas dann. Irgendwas mal z plus irgendwas mal w ist gleich ein Fragezeichen. Das wäre die Elimination. Deshalb Eliminationsverfahren.

Das Eliminieren an der Stelle. Ich eliminiere Variablen. Je weiter ich nach unten komme, umso mehr Variablen eliminiere ich. Im Detail gleich wie es geht. Wenn ich so weit bin, dann kann ich rückwärts rechnen.

Zweiter Schritt, dass ich jetzt auflöse. Von unten auflösen. Das steht auch noch im Skript.

Ich nehme mir die unterste Gleichung. Wenn Sie so eine Gleichung sehen. Irgendwas mal z, irgendwas mal w ist gleich irgendwas. Mit konstanten Zahlen. Was wissen Sie über so eine Gleichung? Wir können in der Tat nach einem auflösen. Wenn da so etwas stünde. 3z plus 4w ist gleich 7.

Dann lösen Sie nach z auf und Sie haben z in Abhängigkeit von w. W ist frei wählbar. W ist frei wählbar und z würde aus w folgen. Mit einem Könnchen Salz muss ich gleich noch sagen. Aber das wäre das typische was passiert. Hier unten löse ich nach z auf.

W ist frei wählbar. Z folgt aus w. W frei wählbar. Z folgt aus w. Dann kenne ich y. Wenn hier nichts schief geht. Aus der zweiten Gleichung. W frei wählbar. Z hatte ich schon. Y hatte ich schon. Dann kenne ich aus der ersten Gleichung x. Also es geht von unten nach oben dann einfach auf. Eine Gleichung nach der anderen.

Schließt sich der Reißverschluss. Und zum Schluss kenne ich alle. Beziehungsweise hier sehen Sie schon was zur Eindeutigkeit. Das kann das Verfahren behandeln. Ich habe hier rausgekriegt. W kann ich wählen. Frei wählen. Und der Rest hängt von w ab. Die Lösungsmenge wird also eine Gerade sein. Was eindimensional ist. Es kann an einer Stelle.

Nicht nur an einer Stelle. Es kann an diversen Stellen schief gehen. Typischerweise nicht. Aber es kann hin und wieder schief gehen. Was könnte hier bei der untersten Gleichung schief gehen. Wenn es nicht so funktioniert. Wie gerade gesagt. Also im Allgemeinen wird hier unten eine vernünftige Gleichung stehen.

So etwas wie 3z plus 4w gleich 7. Wenn da jetzt nun so etwas stünde wie 0z plus 0w gleich 7. Müsste man einmal das Gehirn anschalten und feststellen. Ups. Das ist nicht lösbar. Egal welches z und egal welches w ich einsetze. Das ist nicht lösbar. Also vorsichtig mit Nullen in diesem gauschen Verfahren.

An den Stellen muss man aufpassen. Wenn an den falschen Stellen Nullen stehen. Muss man einmal nachdenken. Das macht das Ganze auch etwas unangenehm. Wenn man es ausprogrammiert. Muss ständig prüfen, ob irgendwas nicht bei Null ist. Wenn hier vor dem z eine Zahl nicht bei Null steht. Sollte ich nicht nach z auflösen.

Aber im Allgemeinen wird es hinhauen. Und wenn es nicht hinhaut. Sehen Sie es ziemlich deutlich. Dass es nicht hinhaut. Und was für ein Problem Sie haben. Das ist im Prinzip diese Zweischrittigkeit. Von den gauschen Eliminationsverfahren. Ich sorge dafür, dass unter der Diagonalen alles Null wird.

Jetzt kann ich das mal ordentlich einmalen. Unter der Diagonalen soll alles Null werden. Das hier ist verbotenes Gebiet. Durch Umformen der Gleichungen. Und dann fange ich an die Gleichungen von unten zu lösen. Und wenn das so wie hier ist. Dass ich mehr Unbekannte als Gleichungen habe.

Werde ich einig Unbekannte frei wählen dürfen. Hier würde ich zum Beispiel das W dann nachher frei wählen. Und daraus das Z bestimmen. Wie gesagt. Mit dem Körnchen Salz. Man muss gucken, ob da nicht irgendwelche Nullen stehen. Die einem das Spiel vermiesen.

Ok. Das Auflösen. Das ist einzig spannend. Quatsch. Das Auflösen ist ziemlich geschenkt. Das Umformen in die Dreiecksform ist das Spannende. Wie komme ich von der normalen Form. Wo hier alles satt gefüllt ist im Rechteck. Zu einer oberen Dreiecksmatrix.

Der Gedanke ist. Von oben Gleichungen zu nehmen. Und bestimmte Vielfacher. Die passenden Vielfachern. Auf die unteren Gleichungen zu addieren. Also nochmal der erste Schritt im Detail.

Wenn man faul ist. Schreibt man nur die Zahlen hin. Ich möchte nachher. Das so und so Vielfache der ersten Gleichung auf die zweite addieren. Das heißt ja einfach. Ich nehme so und so viel mal zwei dazu. So und so viel mal vier dazu. So und so viel mal sieben dazu. Ich schreibe einfach nur die Zahlen hin.

Was soll ich mit den ganzen anderen Krämpeln. Nur die Zahlen hingeschrieben. Zwei, vier. Minus drei. Vier, sieben. Drei, zwei. Minus eins war es. Minus eins. Sechs. Minus drei. Und minus fünf.

Zwei, minus drei. Fünf. Einfach alle diese Zahlen. Nackt hingeschrieben. Das ist die Koeffizientenmatrix. Und die Inhomogenität rechts noch da dran. Das hier wäre die Koeffizientenmatrix. Und da schreibe ich einfach die Inhomogenität noch rechts dran.

Das ist mein Startpunkt. Und nun überlege ich mir was ich dem hier antun kann. Um da Müll zu erzeugen. Das wäre der erste Schritt von dem Verfahren. Die Elimination.

Ich will da die Dreiweg haben. Dann werde ich. Das ist schon Nummer drei. Dann werde ich von der ersten Gleichung. Das minus dreihalbe auf die zweite Gleichung nehmen. Das werde ich rechnen. Die erste mal minus dreihalbe. Auf die zweite.

Das muss ich jetzt nicht glorios hinschreiben. Mit zwei x und vier y. Ich nehme einfach nur die Zahlen die davor stehen. Nur die Koeffizienten. Und hier die Komponenten der Inhomogenität. Alle mal minus dreihalbe. Auf die zweite Gleichung. Dann ist der da vorne weg. Diese drei wird dann wegsamen.

Das Gleichungssystem ist nichts anderes als folgendes. Die erste Zeile bleibt. Nun die zweite Zeile. Wird spannend. Zwei mal minus dreihalbe. Macht minus drei. Auf die drei addiert gibt null. Wie geplant.

Da vorne wollte ich den null haben. Jetzt kommt die vier. Die muss damit der zwei verschmolzen werden. Vier mal minus dreihalbe. Vier mal minus dreihalbe. Vier kürzen gegen die zwei. Macht zwei mal minus drei. Sind minus sechs. Von hier kommen minus sechs. Auf die zwei sind minus vier.

Hab ich zuhause auch rausgekriegt. Wunderbar. Die minus drei. Minus drei mal minus dreihalbe sind neun halbe. Minus eins brauche ich also. Minus eins plus neun halbe. Minus eins sind minus zwei halbe. Sind plus sieben halbe.

Was bin ich froh, dass man sowas dann einfach an den Computer überlassen kann. Und was haben wir hier? Vier mal. Die gab es da vorne schon. Vier mal minus dreihalbe waren minus sechs. Minus sechs plus diese sechs gibt null. Und hier haben wir sieben.

Das wird ganz ungemütlich. 21 minus 21 halbe. Sieben mal minus dreihalbe. Minus 21 halbe. Und dann kommen wir jetzt noch. Minus drei. Das sind minus. Sechs halbe macht zusammen minus 27 halbe. Das will echt keiner zu Fuß rechnen.

Ein Vielfaches der ersten Gleichung auf die zweite Gleichung. So dass hier vorne eine Null steht. Vergessen Sie die ganzen Kopfrechengeschichten. Das Spannende ist nur da vorne eine Null zu erzeugen. Passend zu diesem Schema.

Im nächsten Schritt hätte ich gerne an den ersten beiden Stellen. Hier in der dritten Zeile an den ersten beiden Stellen eine Null. Das kriege ich auf Anhieb nicht hin. Ich kriege aber da vorne eine Null hin. In die erste Spalte der dritten Zeile. Wie kriege ich in die erste Spalte der dritten Zeile eine Null?

Das ist der Trick. Sie nehmen die erste Mal fünf halbe auf die letzte. Die erste Zeile mal fünf halbe auf die letzte. Das war einmal die erste Gleichung. Die erste Gleichung mal fünf halbe auf die letzte Gleichung addieren. Zweimal fünf halbe macht fünf.

Minus diese fünf macht die Null. Da steht die Null, die da stehen soll. Dann geht es weiter. Diese vier mal fünf halbe sind zwei mal fünf sind zehn. Und die fünf dazu sind fünfzehn.

Dann die minus drei. Das sind minus fünfzehn halbe. Dann muss ich doch wieder rechnen. Minus fünfzehn halbe. Minus drei mal fünf halbe plus zwei. Zwei sind vier halbe. Minus elf halbe. Also minus elf halbe.

Und dann kommt die vier mal fünf halbe. Das waren zehn. Zehn minus drei sind sieben. Und hier hinten. Was habe ich mir für Zahlen ausgedacht? 35 halbe. 35 halbe. Und dann kommt hier noch plus zehn halbe dazusehen.

45 halbe. Hier entsteht 45 halbe. Egal, das soll nachher der Computer für uns machen. Wichtig ist, die Idee zu kriegen, was denn überhaupt passiert. Was denn der Computer nachher für uns macht. Es gibt natürlich keinen, der das ernsthaft zu Fuß rechnet. Und wer die da geschlagen gehört.

Ich habe jetzt geschafft hier unten Nullen hinzukriegen. Drei Gleichungen. Vier Unbekannte. Wenn Sie das Ausbuch stabilieren wollen. Zwei x plus vier y. Minus drei z plus vier w ist gleich sieben. Minus vier y. Und so weiter. Drei Gleichungen mit vier Unbekannten.

Und das x taucht in den beiden unteren Gleichungen nicht mehr auf. Ich bin auch nicht ganz da. Den muss ich noch erledigen hier. Ich möchte in der dritten Gleichung kein y.

Wie kriegen wir den weg? Wie kriegen wir das y aus der dritten Gleichung weg? Also wichtig ist, dass ich jetzt nur noch die Gleichung nehme, die vorne auch das Null haben. Wenn ich nämlich jetzt von der zweiten Gleichung das passende Vielfache auf die dritte addiere. Macht mir die Null da vorne nichts mehr kaputt. So viel mal Null auf diese Null addieren.

Es wird nichts passieren. Dann nehmen wir ein Vielfaches der zweiten auf die dritte. Nämlich mal 15 Viertel. Das rechne ich jetzt echt nicht mehr vor. Lohnt sich auch nicht. Wenn Sie jetzt die zweite Gleichung mal 15 Viertel nehmen.

Auf die dritte drauf. 15 Viertel mal Null auf die Null drauf. Das schreibe ich nochmal so weit hin, wie wir es billig haben dürfen. Die erste Gleichung bleibt. Die zweite Gleichung bleibt. Die Null mal 15 Viertel. Auf die Null bleibt eine Null.

Das ist das Nette. Also ich benutze die zweite Gleichung, um in der dritten Gleichung das y anders zu werden. Dann kommt minus 4 mal 15 Viertel. Macht minus 15 plus die 15 ist Null. Was ich genau haben wollte. Deshalb diese 15 Viertel.

Und dann wird es fürchterlich. Es wird irgendwie weitergehen. Aber ich bin bei dieser oberen Dreiecksform. Das ist der erste Schritt des gaussischen Eliminationsverfahrens.

Ich werde die Unbekannten unter der Hauptdiagonalen los. Das hier. Jetzt aber nochmal. Das war die Hauptdiagonale. x, x, y, y, z, z. Ich werde die Unbekannten unter der Hauptdiagonalen los. Dann fange ich an von unten aufzulösen. Das Auflösen ist typischerweise gradlinig.

Mit einmal die Kopfanschalten, wenn da irgendwelche Nullen stehen. Leider gibt es die Situation schon beim Eliminieren, dass an der falschen Stelle Nullen stehen können. Typischerweise geht das so durch.

Aber wenn die Zahlen blöd gewürfelt sind, haben sie ein Problem. Es steht gedruckt im Skript. Das muss ich nicht abschreiben. Gegebenenfalls könnte dieses Problem auftauchen. Dass ich die ersten beiden Schritte beim Eliminieren durchführe.

Hier steht eine Null, da steht eine Null. Ich führe die ersten beiden Schritte durch. Und nun könnte mir Folgendes passieren. Hier nirgends vor Besonderheiten. Es könnte mir passieren, dass hier spontan zufällig eine Null steht.

Stellen Sie sich vor, Sie machen diese ersten Schritte. Die erste Zeile mal so und so viel, dass die Null am Anfang der zweiten Zeile steht. Die erste Zeile mal so und so viel, dass die Null am Anfang der dritten Zeile steht. Dann könnte es passieren, dass hier in der zweiten Zeile spontan ohne Ankündigung eine Null auftaucht.

Da könnte eine Null stehen. Warum würde mich das nerven, dass da eine Null steht? Jetzt kann ich mich auf den Kopf stellen. Egal womit ich die zweite Zeile multipliziere.

Ich kann mit der zweiten Zeile hier unten nicht die Minus 2 wegkriegen. Wenn ich das 98-fache der zweiten Zeile nehme und auf die dritte Zeile addiere, bleibt da die Minus 2 stehen. Der Trick, mit dem ich da die Null erzeugt habe, funktioniert nicht. Andererseits ist das aber kein Problem. Warum ist das auf den ersten Blick blöd und unangenehm, wenn man es ausprogrammiert?

Aber warum ist es doch kein Problem, wenn man genauer hinguckt? Also hier gibt es eine ganz bittige Lösung. Sie tauschen die beiden. Das sind ja zwei Gleichungen. Einfach zwei Gleichungen. Die Reihenfolge der Gleichungen ist egal. Ich tausche die zweite und die dritte Gleichung, dann steht die Minus 2 da und die Null da. Und ich freue mich, weil dann habe ich sofort die obere Dreiecksform, ohne irgendwas gerechnet zu haben.

Also wenn die Null hier auftritt, ist das kein Problem. Wie gesagt, wenn Nullen auftreten an unerwarteten Stellen, einfach einmal das Gehirn anschalten, sollte kein Problem sein. Hier kann ich durch Vertauschen der Zeilen raus. Wenn hier jetzt auch noch eine Null stünde, dann wäre es ja auch lustig.

Dann hätte ich nämlich nur noch zwei unbekannte Z und W. Zwei Gleichungen mit zwei unbekannten. Also es kann sein, dass es sich spontan vereinfacht, wenn zu viele Nullen da auftauchen. Denken Sie einfach mit an der Stelle. Gucken Sie, wo die Nullen da stehen.

Das ist, wenn man es programmieren will, etwas unangenehme Aufgabe. Weil der Rechner muss die ganzen Regeln, mit denen man dann agiert, wenn da eine Null steht, natürlich als Rezept jetzt so klein vorserviert bekommen. Aber ich denke, das kriegen Sie aus dem Stehgreif hin, wenn Ihnen das passiert. Typischerweise passiert es nicht.

Typischerweise geht das einfach so durch. Das ist das Eliminationsverfahren.