G3 Lineare Gleichungen und Gleichungssysteme
Allgemeine Linearen Gleichungssysteme
Die bisherigen Beispiele waren immer so konstruiert, dass sie eine eindeutige Lösung hatten. Tatsächlich gibt es aber drei Fälle, die eintreten können: Ein Lineares Gleichungssystem (LGS) kann keine Lösung, genau eine Lösung oder aber unendlich viele Lösungen haben. Außerdem ging es bis hier immer um LGS, die genauso viele Zeilen wie Spalten (m=n) zuzüglich einer rechten Seite haben. Das ist nicht erforderlich und in der Praxis auch nicht immer der Fall, es besteht aber ein Zusammenhang mit der Lösbarkeit. Der Schlüssel zur Beantwortung der Frage nach der Lösbarkeit ist die lineare Abhängigkeit bzw. Unabhängigkeit von Gleichungen. Diese steht in einem engen Zusammenhang mit der lineare Abhängigkeit und Unabhängigkeit von Vektoren.
Lineare Abhängigkeit und Unabhängigkeit von Gleichungen
Jede Gleichung kann Informationen enthalten, die zu Bestimmung einer Variablen genutzt werden können. Es ist aber auch möglich, dass eine Gleichung keine Informationen enthält, die nicht schon anderweitig im LGS enthalten sind.
Beispiel
1 kg Äpfel und 1 kg Birnen kosten 5€,
2 kg Äpfel und 1 kg Birnen kosten 7€.
Der Kilopreis von Äpfeln und Birnen lässt sich ermitteln, denn jede Gleichung enthält neue Informationen. Mit anderen Worten, die Gleichungen sind linear unabhängig.
Mit folgenden Informationen lässt sich die Frage nach dem Kilopreis hingegen nicht beantworten:
1 kg Mehl und 1 kg Zucker kosten 1€.
5 kg Mehl und 5 kg Zucker kosten 5€.
Die zweite Gleichung ist das Fünffache der ersten Gleichung und enthält keine neuen Informationen die geeignet sind, um die Einzelpreise zu ermitteln.
Eine Gleichung enthält dann keine neuen Informationen, wenn sie die Summe eines Vielfachen der anderen Gleichungen ist. Um den Bezug zu Vektoren herzustellen: Denkt man sich jede Zeile als Vektor, kann eine abhängige Zeile als Linearkombination der anderen Zeilen dargestellt werden.
Beispiel (ohne rechte Seite)
Da im Allgemeinen nicht ohne weiteres zu erkennen ist, ob Abhängigkeiten vorliegen, stellt sich die Frage, wie man Abhängigkeiten aufdecken kann. Die beruhigende Antwort lautet, dass bei Anwendung des Gauß-Algorithmus Abhängigkeiten automatisch aufgedeckt werden. Das geeignete Vorgehen ist deswegen einfach zu versuchen, das LGS mit dem Gauß-Algorithmus zu lösen: Erklärung anhand eines Beispiels, zunächst noch ohne rechte Seite:
Ist eine Zeile linear abhängig, erscheint beim Lösen eine Nullzeile.
Lösbarkeit
Für die Lösbarkeit ist entscheidend, ob auch die rechte Seite als Linearkombination mit den gleichen Faktoren dargestellt werden kann (links) oder nicht (rechts):
Lösen mit dem Gauß-Algorithmus führt zu folgenden Zeilen im letzten Tableau:
In Gleichungsschreibweise
0·x1+0·x2+0·x3=0
0=0
Eine wahre aber nutzlose Aussage.
Die Zeile kann gestrichen werden.
0·x1+0·x2+0·x3=4
0=4
Eine falsche Aussage.
Die Zeile und damit das gesamte LGS sind widersprüchlich und das LGS hat keine Lösung.
Ist ein LGS frei von Widersprüchen, hat es eine oder unendlich viele Lösungen.
Anzahl der Zeilen und Spalten
Ob eine widerspruchsfreies LGS nun eine oder unendlich viele Lösungen hat, hängt davon ab, wie viele Spalten die Koeffizientenmatrix hat und wie viele Zeilen, die keine Nullzeile sind, vorhanden sind. Für eine eindeutige Bestimmung wird pro Spalte eine Nicht-Nullzeile benötigt. Oder, anders ausgedrückt, die Anzahl der Variablen muss mit der Anzahl der linear unabhängigen Gleichungen übereinstimmen. Sind es weniger Gleichungen, hat das LGS unendlich viele Lösungen.
unterbestimmtes Gleichungssystem
Die möglichen Konstellationen bei einem widerspruchsfreien (!) Gleichungssystem:
Weniger Zeilen als Spalten (m<n)
Das LGS hat unendlich viele Lösungen. Bei Anwendung des Gauß-Algorithmus können zudem noch Nullzeilen aufgedeckt werden. Ein LGS mit weniger Zeilen und Spalten wird auch als unterbestimmtes Gleichungssystem bezeichnet.
Gleich viele Zeilen und Spalten (m=n)
Ist die Zeilen- und Spaltenzahl gleich, spricht man auch von einem bestimmten, exakt bestimmten oder quadratischem Gleichungssystem. Enthält das LGS keine Nullzeilen, ist es eindeutig lösbar. Enthält es Nullzeilen, hat es unendlich viele Lösungen.
Mehr Zeilen als Spalten (m>n)
Ein LGS mit mehr Zeilen als Spalten wird auch als überbestimmtes Gleichungssystem bezeichnet. Bei Anwendung des Gauß-Algorithmus werden mit Sicherheit Nullzeilen aufgedeckt. Ein LGS kann auf keinen Fall mehr Nicht-Nullzeilen als Spalten enthalten, es gibt immer m-n Nullzeilen. Sind es genau m-n Nullzeilen, ist das LGS eindeutig lösbar. Es ist aber möglich, dass weitere Nullzeilen aufgedeckt werden. In diesen Fällen hat das LGS unendlich viele Lösungen.
Leider ist zu Beginn nicht klar, welche Zeilen Nullzeilen sein werden, sodass der Gauß-Algorithmus auf das vollständige LGS angewendet werden muss.
Zusammenfassung
- Zur Klärung der Anzahl der Lösungen eines LGS wird der Gauß-Algorithmus angewendet.
- Wird bei einem Zwischenschritt eine widersprüchliche Zeile aufgedeckt, kann die Rechnung abgebrochen werden. Das LGS hat dann keine Lösung.
- Ansonsten wird der Gauß-Algorithmus bis zum Ende der Eliminationsphase ausgeführt. Diese ist dann zu Ende, wenn es keine zulässigen Pivotelemente mehr gibt.
- Sind am Ende weniger Nicht-Nullzeilen vorhanden als Spalten, hat das LGS unendlich viele Lösungen, ansonsten kann die eindeutige Lösung abgelesen werden.
