Mathematik für Wirtschaftswissenschaftler: Lineare Gleichungssysteme

Nehmen wir uns noch einmal das Beispiel mit dem Tante-Emma-Laden in der Einführung vor:

1\cdot x_{1}+2\cdot x_{2}=8,

4\cdot x_{1}+5\cdot x_{2}=23.

Es sollen beide Gleichungen zugleich gelten, also schreibt man eigentlich korrekt

1\cdot x_{1}+2\cdot x_{2}=8

\qquad \quad \land

4\cdot x_{1}+5\cdot x_{2}=23

.

Sind Missverständnisse ausgeschlossen, können die „und“ weggelassen werden.

In Matrizenschreibweise kann man das System darstellen als

{\begin{bmatrix}1&2\\4&5\end{bmatrix}}\cdot {\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}={\begin{bmatrix}8\\23\end{bmatrix}}

,

allgemein

{\underline {A}}\ {\underline {x}}={\underline {b}}

mit der Koeffizientenmatrix ${\underline {A}}={\begin{bmatrix}1&2\\4&5\end{bmatrix}}$ , dem Variablenvektor ${\underline {x}}={\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}$ und dem Lösungsvektor ${\underline {b}}={\begin{bmatrix}8\\23\end{bmatrix}}$ .

Lösung linearer Gleichungssysteme

Gaußscher Algorithmus

In der Matrizenrechnung wird aus praktischen Gründen das Eliminationsverfahren verwendet.

Wie löst man idealerweise ein lineares Gleichungssystem (kurz: LGS)?

Betrachten wir ein Beispiel:

{\begin{array}{rr}1x_{1}-3x_{2}+1x_{3}+3x_{4}&=12;\\-3x_{2}-1x_{3}-5x_{4}&=11;\\-3x_{3}+2x_{4}&=4;\\-3x_{4}&=6;\end{array}}

in Matrizenschreibweise

{\underline {A}}\cdot {\underline {x}}={\underline {b}}

, bzw.

{\begin{bmatrix}1&-3&1&3\\0&-3&-1&-5\\0&0&-3&2\\0&0&0&-3\end{bmatrix}}\cdot {\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\end{bmatrix}}={\begin{bmatrix}12\\11\\4\\6\end{bmatrix}}

,

Wie lösen wir dieses Gleichungssystem? Am besten rekursiv von unten nach oben. Rekursiv heißt, dass man die Informationen der vorherigen Schritte für den nächsten Lösungsschritt verwendet.

{\begin{array}{rr}1x_{1}-3x_{2}+1x_{3}+3x_{4}&=12;\\-3x_{2}-1x_{3}-5x_{4}&=11;\\-3x_{3}+2x_{4}&=4;\\-3x_{4}&=6.\end{array}}

Wir beginnen mit Zeile 4:

-3x_{4}=6

Wir erhalten

x_{4}={\frac {6}{-3}}=-2

.

Wir nehmen uns nun die dritte Gleichung vor und berechnen $x_{3}$ :

x_{3}+2x_{4}=4\Rightarrow x_{3}+\overbrace {2\cdot (-2)} ^{-4}=4\Rightarrow x_{3}=4+4=8

.

Für die zweite Gleichung ergibt sich

-3x_{2}-1x_{3}-5x_{4}=11\Rightarrow -3x_{2}-1\cdot 8-5\cdot (-2)=11\Rightarrow -3x_{2}-8+10=11\Rightarrow -3x_{2}=11-2=9\Rightarrow x_{2}=-3

.

Schließlich bestimmen wir $x_{4}$ :

1x_{1}-3x_{2}+1x_{3}+3x_{4}=12\Rightarrow x_{1}-3\cdot (-3)+8+3\cdot (-2)=12\Rightarrow x_{1}+9+8-6=12\Rightarrow x_{1}+11=12\Rightarrow x_{1}=1.

Unser Ergebnis ist also

x_{1}=1;\ x_{2}=-3;\ x_{3}=8;\ x_{4}=-2

.

Dieses Gleichungssystem war einfach zu lösen, denn die Gleichungen bauten aufeinander auf und ermöglichten ein rekursives Lösungsverfahren. Wir können die Rekursivität unmittelbar der Koeffizientenmatrix entnehmen, denn sie ist eine Dreiecksmatrix.

Wie sieht es nun beispielsweise aus mit der Lösung des Gleichungssystems

3x+2y-z=13;

2x-y+3z=-1;

5x-4y+4z=3;

in Matrizenschreibweise

{\underline {A}}\cdot {\underline {x}}={\underline {b}}

bzw.

{\begin{bmatrix}3&2&-1\\2&-1&3\\5&-4&4\end{bmatrix}}\cdot {\begin{bmatrix}x\\y\\z\end{bmatrix}}={\begin{bmatrix}13\\-1\\3\end{bmatrix}}

?

Nett wäre es, wenn man auch hier ${\underline {A}}$ auf Dreiecksgestalt wie oben in der Form ${\begin{bmatrix}x&x&x\\0&x&x\\0&0&x\end{bmatrix}}$ bringen könnte. Das kann man mit dem Eliminationsverfahren erreichen. Man wendet nun so genannte Zeilenoperationen an. Zulässige Zeilenoperationen sind:

Multiplikation einer Zeile mit einer Konstanten.
Addition zweier Zeilen.
Vertauschen zweier Zeilen.

Für die manuelle Durchführung der Zeilenoperationen fasst man alle Zahlen zweckmäßigerweise in einem so genannten Tableau zusammen, d.h. man trägt die Koeffizienten und die Lösungen in einer Tabelle zusammen.

Bemerkung: Wenn man nun Klammern darumsetzte, hätte man eine erweiterte Koeffizientenmatrix, was uns inhaltlich aber nicht weiter bringt. Das hervorgehobene "manuell" deutet an, dass es hier vor allem darum geht, die Funktionsweise des Lösungsverfahren zu erfassen. Normale Menschen verwenden spezielle Programme für die Lösungen. Studierende werden aber gequält. Sie müssen sich ja das Examen verdienen.

Tableau:

{\begin{array}{lrrr|r}&x_{1}&x_{2}&x_{3}&b\\\hline {\text{I:  }}&3&2&-1&13\\{\text{II:  }}&2&-1&3&-1\\{\text{III:  }}&5&-4&4&3\end{array}}

Die Spalten des Tableaus werden nun von links nach rechts abgearbeitet:

Die 1.Spalte soll sein ${\begin{bmatrix}3\\0\\0\end{bmatrix}}$ .

Ein Vielfaches der 1. Zeile wird von einem Vielfachen der 2. Zeile subtrahiert:

{\begin{array}{c|rrrr}3\cdot \mathrm {II} &6&-3&9&-3\\-(2\cdot \mathrm {I} )&6&4&-2&26\\\hline \mathrm {II} _{\mathrm {neu} }&0&-7&11&-29\end{array}}

Ein Vielfaches der 1. Zeile wird von einem Vielfachen der 3. Zeile subtrahiert:

{\begin{array}{c|rrrr}3\cdot \mathrm {III} &15&-12&12&9\\-(5\cdot \mathrm {I} )&15&10&-5&65\\\hline \mathrm {III} _{\mathrm {neu} }&0&-22&17&-56\\\end{array}}

Die erste Spalte ist fertig und wir wollen nun ein neues Tableau als Zwischenergebnis festhalten.

{\begin{array}{lrrr|r}{\text{I:}}&3&2&-1&-13\\{\text{II:}}&0&-7&11&-29\\{\text{III:}}&0&-22&17&-56\end{array}}

Nun wird die zweite Spalte transformiert. Die 2.Spalte soll sein ${\begin{bmatrix}2\\-7\\0\end{bmatrix}}$ .

Ein Vielfaches der 2. Zeile wird von einem Vielfachen der 3. Zeile subtrahiert:

{\begin{array}{c|rrrr}7\cdot \mathrm {III} &0&-154&119&-392\\-(22\cdot \mathrm {I} )&0&-154&242&-638\\\hline \mathrm {III} _{\mathrm {neu} }&0&0&-123&246\\\end{array}}

Wir speichern Berechnungen als Tableau ab und sehen, dass wir mit den Zeilentransformationen fertig sind, denn unsere Koeffizientenmatrix hat Dreiecksgestalt.

{\begin{array}{rrr|r}3&2&-1&-13\\0&-7&11&-29\\0&0&17&-123\end{array}}

Das entspricht dem Gleichungssystem

{\begin{matrix}3x&+&2y&-&z&=&13,\\&-&7y&+&11z&=&-29,\\&&&&-123z&=&246,\end{matrix}}

das nun rekursiv von unten nach oben gelöst werden kann:

z={\frac {246}{-123}}=-2\Rightarrow

-7y-2\cdot 11=-7y-22=-29\Rightarrow -7y=-7\Rightarrow y=1\Rightarrow

3x+2\cdot 1+(-2)(-z)=3x+2+2=13\Rightarrow 3x+4=13\Rightarrow x=3.

Wir erhalten den Lösungsvektor ${\underline {x}}={\begin{bmatrix}3\\1\\-2\end{bmatrix}}$ bzw. etwas platzsparender ${\underline {x}}^{T}={\begin{bmatrix}3&1&-2\end{bmatrix}}$ .

Man nennt dieses Verfahren, nämlich das Gleichungssystem in Dreiecksgestalt umzuwandeln,

Gaußschen Algorithmus,
Gaußsches Iterationsverfahren,
Gaußsches (teilweises) Eliminationsverfahren.

Bemerkung:

Oftmals sind in der Koeffizientenmatrix ${\underline {A}}$ Nullen enthalten, die bei geschickter Platzierung das Eliminationsverfahren erleichtern. Hier können bei Bedarf die Spalten von ${\underline {A}}$ vertauscht werden. Allerdings muß auf die Reihenfolge der Variablen geachtet werden, z.B.

{\begin{array}{ccc|c}x_{1}&x_{2}&x_{3}&b\\\hline 1&1&1&1\\1&0&1&2\\2&0&0&3\end{array}}

\longrightarrow

{\begin{array}{ccc|c}x_{2}&x_{3}&x_{1}&b\\\hline 1&1&1&1\\0&1&1&2\\0&0&2&3\end{array}}

Vollständiges Eliminationsverfahren

Das Gaußsche Eliminationsverfahren ermöglicht eine rekursive Berechnung der Variablen von unten nach oben. Das lineare Gleichungssystem kann aber weiter umgeformt werden, so dass z.B. ein Tableau der Form

{\begin{array}{ccc|c}x_{1}&x_{2}&x_{3}&a\\\hline 1&0&0&a\\0&1&0&b\\0&0&1&c\end{array}}

entsteht. Hier kann die Lösung direkt abgelesen werden:

x_{1}=a

,

x_{2}=b

,

x_{3}=c

.

Man nennt dieses Verfahren vollständiges Gaußsches Eliminationsverfahren. Das Verfahren ist zwar aufwendiger, wird aber aus verschiedenen praktischen Gründen häufig angewendet, vor allem im EDV-Einsatz. Beispiel:

Gegeben ist das Tableau

{\begin{array}{lccc|c}{\text{I:  }}&2&0&1&2\\{\text{II:  }}&1&2&3&1\\{\text{III:  }}&0&1&1&3\end{array}}

das mit Hilfe der vollständigen Elimination umgeformt werden soll. Man geht spaltenweise von links nach rechts vor, zeilenweise von oben nach unten.

Die 1.Spalte soll sein ${\begin{bmatrix}1\\0\\0\end{bmatrix}}$ .

Man nennt die Zeile, in der schließlich 1 stehen soll, Pivotzeile.

1. Zeile (Pivotzeile):

{\begin{array}{lrrrr}{\text{I}}_{\text{neu}}={\text{I}}/2:&1&0&{\frac {1}{2}}&1\\\end{array}}

2. Zeile:

{\begin{array}{lrrrr}{\text{II:}}&1&2&3&1\\-({\text{I}}_{\text{neu}}):&1&0&{\frac {1}{2}}&1\\\hline {\text{II}}_{\text{neu}}:&0&2&{\frac {5}{2}}&0\end{array}}

3. Zeile: Ist schon o.k.

Neues Tableau als Zwischenergebnis:

{\begin{array}{lccc|c}{\text{I:  }}&1&0&{\frac {1}{2}}&1\\{\text{II:  }}&0&2&{\frac {5}{2}}&0\\{\text{III:  }}&0&1&1&3\end{array}}

Die 2.Spalte soll sein ${\begin{bmatrix}0\\1\\0\end{bmatrix}}$ . Pivotzeile ist also nun Zeile 2.

{\begin{array}{lrrrr}{\text{II}}_{\text{neu}}={\text{II}}/2:&0&1&{\frac {5}{4}}&0\\\end{array}}

1. Zeile ist schon o.k.

3. Zeile:

{\begin{array}{lrrrr}{\text{III:}}&0&1&1&3\\-({\text{II}}_{\text{neu}}):&0&1&{\frac {5}{4}}&0\\\hline {\text{III}}_{\text{neu}}:&0&0&-{\frac {1}{4}}&3\end{array}}

Neues Tableau als Zwischenergebnis:

{\begin{array}{lccc|c}{\text{I:  }}&1&0&{\frac {1}{2}}&1\\{\text{II:  }}&0&1&{\frac {5}{4}}&0\\{\text{III:  }}&0&0&-{\frac {1}{4}}&3\end{array}}

Die 3.Spalte soll sein ${\begin{bmatrix}0\\0\\1\end{bmatrix}}$ . Pivotzeile ist nun Zeile 3.

{\begin{array}{lrrrr}{\text{III}}_{\text{neu}}={\text{III}}\cdot (-4):&0&0&1&-12\\\end{array}}

1. Zeile:

{\begin{array}{lrrrr}{\text{I:}}&1&0&{\frac {1}{2}}&1\\-({\frac {1}{2}}{\text{III}}_{\text{neu}}):&0&0&{\frac {1}{2}}&-6\\\hline {\text{II}}_{\text{neu}}:&1&0&0&7\end{array}}

2. Zeile:

{\begin{array}{lrrrr}{\text{II:}}&0&1&{\frac {5}{4}}&0\\-({\frac {5}{4}}{\text{III}}_{\text{neu}}):&0&0&{\frac {5}{4}}&-15\\\hline {\text{II}}_{\text{neu}}:&0&1&0&15\end{array}}

Neues Tableau als Ergebnis:

{\begin{array}{lccc|c}{\text{I:  }}&1&0&0&7\\{\text{II:  }}&0&1&0&15\\{\text{III:  }}&0&0&1&-12\end{array}}

Wir erhalten die Lösungen

$x_{1}=7$ , $x_{2}=15$ , $x_{3}=-12$ bzw. den Lösungsvektor ${\begin{bmatrix}7\\15\\-12\end{bmatrix}}$ . Für unsere Zwecke dieses Mathekurses genügt i.a. das teilweise Gaußsche Eliminationsverfahren.

Lösbarkeit linearer Gleichungssysteme

Aus den bisherigen Ausführungen wurde ersichtlich, daß z.B. für die Bestimmung von 3 Unbekannten i.a. drei Gleichungen benötigt werden, d.h. für die Bestimmung von $n$ Unbekannten braucht man möglicherweise $n$ Gleichungen.

Fragen: Genügen immer $n$ Gleichungen? Was ist, wenn mehr als $n$ Gleichungen vorhanden sind? Ist das System dann noch lösbar?

Wir bemühen das Beispiel mit Lisa und Familie Meier und werden damit die Lösbarkeit von Gleichungssystemen erkunden.

Im Juni haben wir die Konstellation

{\begin{array}{lccc}&{\text{Schoki}}&{\text{Chips}}&{\text{Euronen}}\\\hline {\text{Lisa}}&1&2&8\\{\text{Meier}}&4&5&23\end{array}}

als Gleichungssystem

{\begin{array}{ll}{\text{I:}}&1\cdot x_{1}+2\cdot x_{2}=8,\\{\text{II:}}&4\cdot x_{1}+5\cdot x_{2}=23.\end{array}}

Wir haben also zwei Gleichungen und zwei Unbekannte und lösen nun das LGS wie gewohnt. Wir gehen aus vom Tableau

{\begin{array}{lcc|c}{\text{I:  }}&1&2&8\\{\text{II:  }}&4&5&23\\\end{array}}

und wollen die Koeffizientenmatrix zur Dreiecksmatrix umwandeln:

{\begin{array}{lrrrr}{\text{II:}}&4&5&23\\-(4\cdot {\text{I}}):&4&8&32\\\hline {\text{II}}_{\text{neu}}:&0&-3&-9\end{array}}

Tableau:

{\begin{array}{lcc|c}&x_{1}&x_{2}\\\hline {\text{I:  }}&1&2&8\\{\text{II:  }}&0&-3&-9\\\end{array}}

\longrightarrow \qquad x_{2}=3;x_{1}=8-2\cdot x_{2}=8-2\cdot 3=2.

Ein Schokoriegel kostet also 2€ und eine Tüte Chips 3€. Es gibt nur eine Lösung für $x_{1}$ und $x_{2}$ . Dieses Gleichungssystem ist eindeutig lösbar.

Im Juli kauft Lisa wie gewohnt einen Schokoriegel und zwei Tüten Chips und zahlt 8 Euro. Familie Meier kauft vier Schokoriegel und acht Tüten Chips und zahlt 32 Euro. Wir interessieren uns wieder für die Preise der Artikel.

Wir gehen aus vom Tableau

{\begin{array}{lcc|c}{\text{I:  }}&1&2&8\\{\text{II:  }}&4&8&32\\\end{array}}

und wollen die Koeffizientenmatrix umwandeln:

{\begin{array}{lrrrr}{\text{II:}}&4&20&32\\-(4\cdot {\text{I}}):&4&8&32\\\hline {\text{II}}_{\text{neu}}:&0&0&0\end{array}}

Hmmm...

Das neue Tableau wird nicht besser:

{\begin{array}{lcc|c}&x_{1}&x_{2}\\\hline {\text{I:  }}&1&2&8\\{\text{II:  }}&0&0&0\\\end{array}}

Wenn wir unser Gleichungssystem genauer betrachten, sehen wir, dass in diesem Fall die zweite Gleichung eigentlich nur das Vierfache der ersten Gleichung ist. In II ist keine neue Information enthalten, so dass wir im Grunde nur eine Gleichung haben. Genau das verrät uns das neue Tableau.

Wir erhalten $2x_{2}=8-x_{1}$ bzw. $x_{2}=4-{\frac {x_{1}}{2}}$ . Mehr Infos sind nicht zu bekommen. Wir haben hier letztlich zwei Unbekannte, aber nur eine Gleichung. Wir können allerdings für $x_{1}$ einen Wert festlegen und dann $x_{2}$ entsprechend berechnen: $x_{1}=3\Longrightarrow x_{2}=8-{\frac {3}{2}}=6,5$ oder $x_{1}=2;\,x_{2}=7$ usw. Es gibt theoretisch unendlich viele Lösungen, je nach Wert von $x_{1}$ . Dieses System ist also mehrdeutig lösbar. Eine spezielle Lösung ist die so genannte Basislösung, also die Lösung für $x_{1}=0$ : $x_{2}=8$ .

Meistens finden die Leute eine eindeutige Lösung schicker als eine mehrdeutige. Allerdings hat man bei einer mehrdeutigen mehr Spielraum, etwa bei der Produktionsplanung.

Im August haben wir die Konstellation

{\begin{array}{lccc}&{\text{Schoki}}&{\text{Chips}}&{\text{Euronen}}\\\hline {\text{Lisa}}&1&2&8\\{\text{Meier}}&4&20&30\end{array}}

als Gleichungssystem

{\begin{array}{ll}{\text{I:}}&1\cdot x_{1}+2\cdot x_{2}=8,\\{\text{II:}}&4\cdot x_{1}+20\cdot x_{2}=30.\end{array}}

als Tableau

{\begin{array}{lcc|c}{\text{I:  }}&1&2&8\\{\text{II:  }}&4&8&30\\\end{array}}

Wir erhalten durch Zeilentransformation

{\begin{array}{lrrrr}{\text{II:}}&4&20&30\\-(4\cdot {\text{I}}):&4&8&32\\\hline {\text{II}}_{\text{neu}}:&0&0&-2\end{array}}

{\begin{array}{lcc|c}&x_{1}&x_{2}\\\hline {\text{I:  }}&1&2&8\\{\text{II:  }}&0&0&-2\\\end{array}}

Wir haben hier die Situation, dass $0\cdot x_{2}=-2$ ist. Sogar einem Meerschweinchen würde auffallen, dass wir hier eine inkonsistente Gleichung haben, dass also keine Lösung möglich ist.

Es sind bei einem Linearen Gleichungssystem folgende Lösungsmöglichkeiten denkbar:

1. Eine (einzige) eindeutige Lösung

2. Unendlich viele Lösungen

3. Keine Lösung

Es gibt verschiedene Methoden, herauszufinden, inwieweit eine Lösung existiert. Das Gaußsche Eliminationsverfahren ist beispielsweise geeignet: Man bringt die erweiterte Koeffizientenmatrix, also ${\underline {A}}$ zusammen mit ${\underline {b}}$ bzw. das entsprechende Tableau auf Trapezgestalt, d.h. man formt ${\underline {A}}$ so weit wie möglich auf Dreiecksgestalt um. Schließlich ergeben sich Konstellationen wie oben erläutert.