Einführung
Ein lineares Gleichungssystem besteht aus mehreren linearen Gleichungen, die alle zugleich erfüllt sein sollen. In diesen Gleichungen treten eine oder mehrere Unbekannte auf. Ein einfaches Beispiel ist das folgende Gleichungssystem mit den Unbekannten $x$ und $y$:
\[\begin{align} 3x + y &= 23 \\ -2x - y &= -16 \end{align}\]Die typische Fragestellung besteht darin, das lineare Gleichungssystem zu lösen. Das bedeutet, Werte für die Unbekannten zu bestimmen, sodass alle Gleichungen des Systems gleichzeitig erfüllt sind. Im vorliegenden Beispiel sind also die Werte von $x$ und $y$ zu berechnen, die beide Gleichungen zugleich korrekt machen.
Lineare Gleichungssysteme finden weitreichend Anwendungen:
- PageRank-Algorithmus – zur Berechnung der Bedeutung von Webseiten im Google-Suchranking.
- Stromnetzberechnung – zur Bestimmung von Strömen und Spannungen in elektrischen Netzwerken.
- Gleichgewichtsanalysen in der Ökonomie – zur Ermittlung von Preisen und Produktionsmengen in Märkten mit mehreren Gütern.
- Bildverarbeitung – zur Rekonstruktion oder Filterung von Bildern, etwa bei Rauschunterdrückung.
- Physikalische Modelle – z. B. bei Kräften im statischen Gleichgewicht oder bei der Berechnung von Schnittpunkten von Ebenen.
- Computergraphik – zur Berechnung von Transformationen, Projektionen oder Beleuchtungseffekten in 3D-Szenen.
- Chemische Reaktionsgleichungen – zur Bestimmung der stöchiometrischen Koeffizienten bei der Reaktionsbilanzierung.
Lösungsverfahren
Wir sehen, dass im obigen Beispiel $x$ und $y$ nicht direkt berechnet werden können, da in jeder Gleichung zwei Unbekannte auftreten. Um ein solches lineares Gleichungssystem nun nach $x$ und $y$ auflösen zu können, gibt es verschiedene Verfahren. Die Grundidee ist immer, die Gleichungen so zu kombinieren, dass nur noch eine Unbekannte in einer Gleichung auftritt. Diese Unbekannte kann dann bestimmt werden, und in der Folge auch die übrigen Unbekannten.
Gleichsetzungsverfahren
Einsetzungsverfahren
Additionsverfahren
1. Info
Lösen linearer Gleichungssysteme mit 2 Gleichungen und 2 Unbekannten
- Gleichsetzungsverfahren: Beide Gleichungen nach der gleichen Unbekannten auflösen und gleichsetzen
- Einsetzungsverfahren: Eine Gleichung nach einer Unbekannten auflösen und diese Lösung in die andere Gleichung einsetzen
- Additionsverfahren: Durch geschicktes Addieren der beiden Gleichungen eine Unbekannte eliminieren
Gauß-Algorithmus
Der Gauß-Algorithmus ist im Grunde eine systematische Erweiterung des Additionsverfahrens. Durch geschickte Umformungen der Gleichungen wird das System schrittweise vereinfacht, bis sich die Lösungen direkt berechnen lassen.
Die Stärke des Gauß-Algorithmus liegt darin, dass er grundsätzlich für beliebig viele Gleichungen und Unbekannte anwendbar ist. Der Einfachheit halber verzichten wir dabei meist auf die Bezeichnung der Unbekannten und stellen das Gleichungssystem stattdessen in einer übersichtlichen Matrixform dar.
Wir betrachten dazu das folgende lineare Gleichungssystem:
\[\begin{align*} x_1 + x_2 + x_3 &= 3 \\ 4x_1 + 2x_2 + x_3 &= 14 \\ 16x_1 - 4x_2 + x_3 &= 8 \end{align*}\]Die Matrixform erhalten wir, indem die Unbekannten und Rechenoperationen ausgelassen werden, die Koeffizienten müssen dabei konsequent untereinander geschrieben werden.
Darstellung in Matrixform
Diese Matrix wird mit Hilfe des Additionsverfahrens in eine obere Dreiecksform überführt, das heißt in eine Matrix, bei der alle Elemente unterhalb der Diagonalen gleich null sind.
Umformen in obere Dreiecksform
Nun verwenden wir wieder die ausführliche Schreibweise, um angefangen von der letzten Gleichung alle Unbekannten nacheinander zu bestimmen.
Sukzessives Auflösen nach den Unbekannten
Der Gauß-Algorithmus bezeichnet konkret das Verfahren, mit dem wir eine obere Dreiecksmatrix erhalten. Dabei verwenden wir die sogenannten elementaren Zeilenumformungen:
- Vertauschen zweier Zeilen
- Multiplizieren einer Zeile mit einem von null verschiedenen Faktor
- Addieren oder Subtrahieren eines Vielfachen einer Zeile zu einer anderen Zeile
Das folgende Video zeigt ein Beispiel, in dem ein Zeilentausch notwendig ist, um in der linken oberen Ecke eine Zahl ungleich Null zu erhalten.
2. Info
Lösen linearer Gleichungssysteme mit 3 Gleichungen und 3 Unbekannten
- Darstellung in Matrixform
- Umformen in obere Dreiecksform
- Sukzessives Auflösen nach den Unbekannten
3. Info
Lösen linearer Gleichungssysteme mit 4 Gleichungen und 4 Unbekannten
- Darstellung in Matrixform
- Umformen in obere Dreiecksform
- Sukzessives Auflösen nach den Unbekannten
Lösungsarten
Bisher haben wir nur lineare Gleichungssysteme mit genau einer Lösung betrachtet. Es gibt aber auch den Fall, dass keine oder unendliche viele Lösungen vorliegen. Dazu betrachten wir die folgenden drei Beispiele, in denen die linearen Gleichungssysteme bereits in Matrixform vorliegen.
Beispiel 1: Eine eindeutige Lösung
\[\begin{pmatrix} 1 & 0 & 3 & | & 9\\ 2 & 2 & 1 & | & 10\\ 3 & 4 & 3 &| & 19 \end{pmatrix} \quad \begin{matrix} \\ II-2\cdot I\\ III-3\cdot I \end{matrix}\] \[\begin{pmatrix} 1 & 0 & 3 & | & 9\\ 0 & 2 & -5 & | & -8\\ 0 & 4 & -6 &| & -8 \end{pmatrix} \quad \begin{matrix} \\ \\ III-2\cdot II \end{matrix}\] \[\begin{pmatrix} 1 & 0 & 3 & | & 9\\ 0 & 2 & -5 & | & -8\\ 0 & 0 & 4 &| & 8 \end{pmatrix} \quad \begin{matrix} \\ \\ \quad\quad\quad\quad\quad \end{matrix}\]Ausgeschrieben erhalten wir:
\[\begin{align*} III:\quad & 4x_3=8 \Rightarrow x_3=2\\ II:\quad & 2x_2-5\cdot 2=-8 \Rightarrow x_2=1\\ I:\quad & x_1+0\cdot 1+3\cdot 2 = 9 \Rightarrow x_1=3\\ \end{align*}\]Das lineare Gleichungssystem hat also die eindeutige Lösung $x_1=3$, $x_2=1$ und $x_3=2$.
Beispiel 2: Keine Lösung
\[\begin{pmatrix} 1 & 2 & 1 & | & 3\\ 2 & 3 & 1 & | & 2\\ 5 & 8 & 3 &| & 4 \end{pmatrix} \quad \begin{matrix} \\ II-2\cdot I\\ III-5\cdot I \end{matrix}\] \[\begin{pmatrix} 1 & 2 & 1 & | & 3\\ 0 & -1 & -1 & | & -4\\ 0 & -2 & -2 &| & -11 \end{pmatrix} \quad \begin{matrix} \\ \\ III-2\cdot II \end{matrix}\] \[\begin{pmatrix} 1 & 2 & 1 & | & 3\\ 0 & -1 & -1 & | & -4\\ 0 & 0 & 0 &| & -3 \end{pmatrix} \quad \begin{matrix} \\ \\ \quad\quad\quad\quad\quad \end{matrix}\]Ausgeschrieben erhalten wir:
\[\begin{align*} III:\quad & 0=-3 \Rightarrow \text{falsche Aussage}\\ \end{align*}\]Das lineare Gleichungssystem hat also keine Lösung.
Beispiel 3: Unendlich viele Lösungen
\[\begin{pmatrix} 1 & 2 & 1 & | & 3\\ 2 & 3 & 1 & | & 2\\ 5 & 8 & 3 &| & 7 \end{pmatrix} \quad \begin{matrix} \\ II-2\cdot I\\ III-5\cdot I \end{matrix}\] \[\begin{pmatrix} 1 & 2 & 1 & | & 3\\ 0 & -1 & -1 & | & -4\\ 0 & -2 & -2 &| & -8 \end{pmatrix} \quad \begin{matrix} \\ \\ III-2\cdot II \end{matrix}\] \[\begin{pmatrix} 1 & 2 & 1 & | & 3\\ 0 & -1 & -1 & | & -4\\ 0 & 0 & 0 &| & 0 \end{pmatrix} \quad \begin{matrix} \\ \\ \quad\quad\quad\quad\quad \end{matrix}\]Ausgeschrieben erhalten wir:
\[\begin{align*} III:\quad & 0\cdot x_3=0 \\ & \text{Wir sehen, dass jede beliebige reelle Zahl eine Lösung für $x_3$ ist. Formal schreiben wir dafür $x_3=t$ mit $t\in\mathbb{R}$.}\\ II:\quad & -x_2-t=-4 \Rightarrow -x_2=t-4 \Rightarrow x_2=4-t\\ I:\quad & x_1+2(4-t)+t=3 \Rightarrow x_1+8-2t+t=3 \Rightarrow x_1=t-5 \end{align*}\]Das lineare Gleichungssystem hat also die unendlich vielen Lösungen $x_1=t-5$, $x_2=4-t$ und $x_3=t$, wobei $t$ eine beliebige reelle Zahl ist.
Statt $x_3$ hätten wir hier auch $x_1$ oder $x_2$ gleich $t$ setzen können. Die Gestalt der Lösung sähe dann anders aus, die Menge der Lösungen ist aber stets gleich.
Zusammenfassung
Lineare Gleichungssysteme können die drei folgenden Arten von Lösungen haben:
- Eine eindeutige Lösung
- Keine Lösung
- Unendlich viele Lösungen
Allgemeine Systeme
Im Allgemeinen muss in einem linearern Gleichungssystem die Anzahl der Unbekannten nicht mit der Anzahl der Gleichungen übereinstimmen. Auch in diesen Fällen lässt sich das System systematisch mit dem Gauß-Algorithmus lösen. Statt von einer oberen Dreiecksform sprechen wir hier allgemeiner von einer Zeilenstufenform. Diese liegt vor, wenn in jeder Zeile das erste von Null verschiedene Element weiter rechts liegt als in der darüberliegenden Zeile und wenn alle Einträge unterhalb dieser führenden Elemente jeweils Null sind.
Beispiel: Mehr Unbekannte als Gleichungen
\[\begin{align*} x_1 + 4x_2 + 3x_3 &= 2 \\ 2x_1 + 6x_2 + 8x_3 &= 3 \\ \end{align*}\]Darstellung in Zeilenstufenform
Ausgeschrieben erhalten wir:
\[\begin{align*} II:\quad & -2\cdot x_2 + 2x_3=-1 \\ & \text{Wir sehen, dass wir für $x_3$ jede beliebige reelle Zahl vorgeben können, und dann diese Gleichung nach $x_2$ auflösen können.}\\ &x_3=t\text{ mit }t\in\mathbb{R}.\\ &-2\cdot x_2+2\cdot t =-1 \Rightarrow x_2=0,5+t\\ I:\quad & x_1+4(0,5+t)+3t=2 \Rightarrow x_1+2+4t+3t=5 \Rightarrow x_1=3-7t \end{align*}\] \[\begin{align*} x_1 + 2x_2 &= 4 \\ 3x_1 + 4x_2 &= 3 \\ 2x_1 + 1x_2 &= 5 \\ \end{align*}\] \[\begin{pmatrix} 1 & 2 & | & 4\\ 3 & 4 & | & 3\\ 2 & 1 &| & 5 \end{pmatrix}\]