Kurs:Mathematik fuer Anwender/Lineare Gleichungssysteme

Lineare Gleichungssysteme

Bearbeiten

Beispiel: Lineares Gleichungssystem

Bearbeiten

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

Bearbeiten
  1. Ein System aus   Gleichungen und   Unbekannten   der Form  

    mit Koeffizienten     und     heißt ein lineares Gleichungssystem (LGS) in   Variablen mit   Gleichungen.

  2. Wir nennen einen Vektor   eine Lösung des linearen Gleichungssystems  , wenn die Aussage

     

    wahr ist.

  3. 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.

Beispiel: Lösungsmenge Linearer Gleichungssysteme

Bearbeiten
  • 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:

Satz: Zusammenhang LGS und Matrix

Bearbeiten
  1. Ist   ein vorgegebener Vektor sowie   ein Vektor aus Unbekannten mit   Einträgen und   eine  -Matrix, so wird durch die Gleichung   das lineare Gleichungssystem   definiert.


  1. 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.

Bemerkung: Koeffizientenmatrix

Bearbeiten

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

Bearbeiten

Es sei   ein lineares Gleichungssystem mit einer  -Matrix  .

Genau dann hat das LGS   eine Lösung, wenn   im Bild der linearen Abbildung   mit   liegt.

Satz: Lösungsmenge eines homogenen LGS

Bearbeiten

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.

Definition: Elementare Zeilenumformungen

Bearbeiten

Es sei   ein lineares Gleichungssystem. Ferner sei  .
Die folgenden elementaren Zeilenumformungen verändern die Lösungsmenge des Gleichungssystems nicht.

  1. Das Vertauschen zweier Gleichungen bzw. Zeilen der erweiterten Koeffizientenmatrix:

     

  2. 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!):

     

  3. Das Ersetzen einer Gleichung bzw. Zeile der erw. Koeff.-matrix durch die Summe der Zeile mit dem  -Fachen einer anderen Zeile.

     

Definition: Zeilenstufenform (ZSF)

Bearbeiten

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.

Beispiel: Zeilenstufenform (ZSF)

Bearbeiten
  • Die Matrix   ist in Zeilenstufenform.
  • Die Matrix   ist in Zeilenstufenform.
  • Die Matrix   ist nicht in Zeilenstufenform.
  • Die Matrix   ist nicht in Zeilenstufenform.

Satz: Elementare Zeilenumformungen und Zeilenstufenform

Bearbeiten

Jede  -Matrix   lässt sich durch endlich viele elementare Zeilenumformungen in eine Matrix in Zeilenstufenform überführen.

Damit erhalten wir einen Algorithmus zur Lösung linearer Gleichungsssysteme:

Der Gauß-Algorithmus

Bearbeiten

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.

Beispiel: Gauß-Algorithmus

Bearbeiten
  1. Wir betrachten das durch   definierte lineare Gleichungssystem.

    Dann berechnen wir   Hieraus ergibt sich  , also  , und  , also  . Das lineare Gleichungssystem hat somit genau eine Lösung und Lösungsmenge  

  2. Wir betrachten das durch   definierte lineare Gleichungssystem.

    Dann berechnen wir   Hieraus ergibt sich   und  , also
     .
    Das Gleichungssystem hat also unendlich viele Lösungen mit Lösungsmenge  

  3. Wir betrachten das durch   definierte lineare Gleichungssystem.

    Dann berechnen wir   Hieraus ergibt sich  . Das lineare Gleichungssystem hat somit keine Lösung, also ist  

Lemma: Gauß-Algorithmus und LGS mit Parametern

Bearbeiten

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:

Beispiel: LGS mit Parametern

Bearbeiten

Sei das LGS

 

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

 

Das liefert uns die (einelementige) Lösungsmenge