Ein Beispiel aus der Chemie, genauer der Stöchiometrie: Bei der Eisenreduktion im Hochofen reagieren Kohlenstoff () und Eisenoxid () zu Eisen () und Kohlenstoffdioxid ().
Also gilt die Reaktionsgleichung mit unbekannten Koeffizienten , , und . Diese sollen nun bestimmt werden. Dabei gilt, dass die Atomanzahl für jedes beteiligte chemische Element auf der linken Seite (Reaktanten) und der rechten Seite (Reaktionsprodukte) übereinstimmen muss.
Damit erhalten wir folgende Gleichungen:
Kohlenstoff liefert: ,
Eisen liefert: ,
Sauerstoff liefert: .
Das sind Gleichungen für Unbekannte.
Als zusätzliche Bedingung, die wir aber erst einmal ignorieren, sollen , , und positive natürliche Zahlen, und zwar so kleine wie möglich, sein.
Zum Beispiel durch Ausprobieren kommt man dann auf eine (durch die Zusatzbedingung eindeutige) Lösung: , , und .
Wir werden in diesem Kapitel prüfen, ob das nicht systematisch besser gelöst werden kann als durch stupides Herumprobieren.
Definition: Lineares Gleichungssystem und Lösungsmenge
Ein System aus Gleichungen und Unbekannten der Form
mit Koeffizienten und heißt ein lineares Gleichungssystem (LGS) in Variablen mit Gleichungen.
Wir nennen einen Vektor eine Lösung des linearen Gleichungssystems , wenn die Aussage
wahr ist.
Die Menge aller Lösungen unseres LGS nennen wir die Lösungsmenge, formal: ist eine Lösung des LGS (*).
Ist , so nennen wir das LGS homogen, ansonsten inhomogen.
Das lineare Gleichungssystem und hat als einzige Lösung , also .
Das lineare Gleichungssystem und hat keine Lösung, also .
Das lineare Gleichungssystem und hat alle Paare für jedes beliebige als Lösung, also .
Anhand der Beispiele sehen wir, dass lineare Gleichungssysteme nicht immer Lösungen besitzen und dass die Anzahl der Lösungen stark variieren kann. Wir fragen uns “Wann gibt es (mindestens) eine Lösung?” und “Wenn es eine Lösung gibt, wie viele Lösungen gibt es insgesamt?” Eine ganz andere aber wichtige Frage ist auch: “Wie finden wir Lösungen?”
Um diese Fragen zu beantworten, übersetzen wir das LGS in Matrizenschreibweise:
Ist ein vorgegebener Vektor sowie ein Vektor aus Unbekannten mit Einträgen und eine -Matrix, so wird durch die Gleichung das lineare Gleichungssystem definiert.
Ist umgekehrt ein lineares Gleichungssystem in Variablen mit Gleichungen. Damit wird das obige lineare Gleichungssystem durch die Gleichung bestimmt, wobei ein Vektor, ein Vektor mit Einträgen und die -Matrix ist, die aus den Einträgen des linearen Gleichungssystems besteht.
Ist ein Vektor sowie ein Vektor mit Einträgen und eine -Matrix, so wird das durch die Gleichung bestimmte lineare Gleichungssystem durch die Matrix eindeutig bestimmt. Wir nennen die Matrix die Koeffizientenmatrix und die Matrix die erweiterte Koeffizientenmatrix des LGS.
Lemma: Bild einer Linearen Abbildung und Lösung eines LGS
Es sei ein homogenes lineares Gleichungssystem mit einer -Matrix. Dann ist der Nullvektor stets eine Lösung des LGS. Insbesondere ist jedes homogene lineare Gleichungssystem lösbar. Aber der Nullvektor ist möglicherweise nicht die einzige Lösung des homogenen LGS.
Es sei ein lineares Gleichungssystem. Ferner sei .
Die folgenden elementaren Zeilenumformungen verändern die Lösungsmenge des Gleichungssystems nicht.
Das Vertauschen zweier Gleichungen bzw. Zeilen der erweiterten Koeffizientenmatrix:
Das Multiplizieren einer Gleichung bzw. Zeile der erw. Koeff.-matrix mit (Wichtig: Es ist , ansonsten ist dieser Schritt verboten, da beim Multiplizieren einer Zeile mit alle Informationen dieser Zeile eliminiert werden!):
Das Ersetzen einer Gleichung bzw. Zeile der erw. Koeff.-matrix durch die Summe der Zeile mit dem -Fachen einer anderen Zeile.
Eine -Matrix hat Zeilenstufenform (ZSF), wenn der (von links gelesen) erste von verschiedene Eintrag einer Zeile von immer weiter rechts steht, je weiter unten sich die Zeile befindet. Zeilen, die ausschließlich -Einträge besitzen, dürfen sich dabei nur ganz unten in der Matrix befinden.
Ein LGS hat Zeilenstufenform, wenn die Matrix Zeilenstufenform hat.
Es sei ein lineares Gleichungssystem mit einer -Matrix .
Zuerst stellen wir die erweiterte Koeffizientenmatrix auf.
Beim Gauß-Algorithmus überführen wir dann die erweiterte Koeffizientenmatrix durch elementare Umformungen in Zeilenstufenform und erhalten eine erweiterte Koeffizientenmatrix . Wichtig ist dabei, dass wir jede Umformung, die wir an vornehmen, auch an durchführen. Nach Definition und Satz [elZ] hat das LGS dieselbe Lösungsmenge wie das LGS .
Das lineare Gleichungssystem , das in Zeilenstufenform vorliegt, kann leicht gelöst werden, indem man die Gleichungen (von unten beginnend) auflöst und das Ergebnis in die nächsthöhere Gleichung einsetzt (Rückwärtssubstitution).
Eventuell können in der Lösung einige Variablen frei gewählt werden oder es entsteht irgendwo ein Widerspruch. Im ersten Fall hat das LGS unendlich viele Lösungen, im zweiten Fall besitzt es keine Lösung und die Lösungsmenge ist leer. Tritt keiner dieser beiden Fälle ein, hat das LGS genau eine Lösung.
Ist das zu lösende lineare Gleichungssystem mit einem (oder mehreren) Parametern gegeben, so ist der Gauß-Algorithmus immer noch anwendbar. Es ist allerdings bei jeder elementaren Zeilenumformung darauf zu achten, dass keine Zeile mit multipliziert wird und dass niemals durch geteilt wird. Die Fälle, in denen dies geschehen würde, müssen ausgeschlossen und später gesondert betrachtet werden. Auch bei der Lösung des in Zeilenstufenform vorliegenden LGS muss auf Sonderfälle geachtet werden.
Jetzt noch ein (schweres) Beispiel für ein solches LGS mit Parametern:
gegeben, wobei ein beliebiger aber fest gewählter Wert (d. h. ein Parameter) sei. Zuerst stellen wir die erweiterte Koeffizientenmatrix zum LGS auf: Nun stellen wir fest, dass das ein fieses Beispiel ist, denn um die Matrix, so wie sie nun hier steht, auf ZSF zu bringen, könnten wir das -Fache der ersten Zeile von der zweiten und von der dritten Zeile abziehen. Das kann man machen, ist aber schrecklich, weil man den Fall, dass ist, dann getrennt behandeln muss, da man in diesem Fall nicht bilden kann. Geschickter ist es, hier zuerst einmal die Zeilen zu tauschen. Wir tauschen die erste und die dritte Zeile und erhalten
Und jetzt können wir den Gauß-Algorithmus anwenden, ohne eine Fallunterscheidung vornehmen zu müssen (die kommt dann erst später):
Die Matrix ist nun in ZSF überführt und wir können weiterrechnen: Die dritte Zeile liefert . Achtung! Jetzt einfach durch dividieren dürfen wir nicht, da der Ausdruck gleich sein kann. Es ist (nachrechnen!), der Ausdruck nimmt also genau für und für den Wert an. Wir müssen nun Fälle unterscheiden:
1. Fall: Sei . Dann liefert die dritte Zeile , d. h. ist frei wählbar. Einsetzen in die zweite Zeile liefert: , also ist auch frei wählbar. Die erste Zeile liefert dann .
In diesem Fall erhalten wir als Lösungsmenge .
2. Fall: Sei . Die dritte Zeile liefert dann , das ist aber für kein erfüllt, also gibt es keine Lösung und wir erhalten .
3. Fall: Sei . Dann ist und wir erhalten aus der dritten Zeile .
Einsetzen in die zweite Zeile ergibt , also .
Und zuletzt setzen wir in die erste Zeile ein und erhalten