Lineare Gleichungssysteme und das Gauß-Verfahren
Lesen anpassen
Nach dieser Lektion kannst du
ein lineares Gleichungssystem als und als erweiterte Koeffizientenmatrix schreiben,
begründen, warum elementare Zeilenumformungen die Lösungsmenge nicht ändern,
eine Matrix mit dem Gauß-Verfahren auf Zeilenstufenform bringen und die Lösungsmenge ablesen,
erkennen, ob ein System keine, genau eine oder unendlich viele Lösungen hat, und die Lösungen mit freien Parametern angeben,
die Lösungsmenge als spezielle Lösung plus Kern beschreiben und das beweisen.
Vorausgesetzt: Matrizenmultiplikation, Kern und Bild, Die Dimensionsformel
In der Schule löst man drei Gleichungen mit drei Unbekannten mit dem Additionsverfahren: Man zieht Vielfache einer Gleichung von einer anderen ab, bis die Unbekannten nacheinander wegfallen. Zum Beispiel:
| Nr. | Gleichung |
|---|---|
| I | |
| II | |
| III |
Das funktioniert, aber es lässt Fragen offen. Warum darf man so umformen, ohne Lösungen zu verlieren oder neue dazuzubekommen? Wie geht man bei fünf Gleichungen mit sieben Unbekannten vor, ohne sich zu verirren? Woran sieht man, dass es keine Lösung gibt oder unendlich viele, und wie schreibt man unendlich viele Lösungen auf?
Mit Matrizen lassen sich alle diese Fragen beantworten. Links steht nämlich ein Matrix-Vektor-Produkt: Das System lautet . Lösen heißt also, alle Vektoren zu finden, die von der linearen Abbildung auf abgebildet werden. Was wir über Kern und Bild wissen, sagt dann viel über die Lösungen. Wie in den vorigen Lektionen ist ein Körper.
Ein homogenes System, also eines mit rechter Seite , hat zwei Gleichungen und drei Unbekannte über , zum Beispiel und . Wie viele Lösungen hat ein solches System?
Lineares Gleichungssystem
Ein lineares Gleichungssystem (LGS) mit Gleichungen und Unbekannten über hat die Form
für ,
mit gegebenen . Die Koeffizientenmatrix ist , die rechte Seite . Nach der Zeilenformel für ist das System genau die Gleichung . Es heißt homogen, wenn ist, sonst inhomogen.
Die Lösungsmenge ist . Insbesondere ist ; wir schreiben dafür kurz .
Die erweiterte Koeffizientenmatrix entsteht, indem man als zusätzliche Spalte rechts an anhängt. Sie enthält alle Informationen des Systems, ohne die Namen der Unbekannten.
Gegenbeispiel: oder sind keine linearen Gleichungen, denn die Unbekannten werden miteinander multipliziert oder potenziert. Solche Gleichungen lassen sich nicht als schreiben.
Das Eingangssystem in Matrixform
Das Eingangssystem in Matrixform
Für das System aus der Einleitung ist
Jede Zeile der erweiterten Matrix ist eine Gleichung, jede Spalte links vom Strich gehört zu einer Unbekannten. Fehlt eine Unbekannte in einer Gleichung, steht an ihrer Stelle eine . Der Strich erinnert daran, dass die letzte Spalte die rechte Seite ist.
Elementare Zeilenumformungen
Auf eine Matrix (zum Beispiel ) wendet man drei Arten von elementaren Zeilenumformungen an:
- Typ I: zwei Zeilen vertauschen.
- Typ II: eine Zeile mit einem Skalar multiplizieren.
- Typ III: das -fache einer Zeile zu einer anderen Zeile addieren ( beliebig).
Für Gleichungen heißt das: Gleichungen umsortieren, eine Gleichung mit einer Zahl ungleich multiplizieren, ein Vielfaches einer Gleichung zu einer anderen addieren. Man notiert die Umformung neben der Zeile, etwa .
Gegenbeispiele: Eine Zeile mit multiplizieren ist keine elementare Umformung, und auch nicht, Zeile durch Zeile plus mal Zeile zu ersetzen. Beides löscht eine Gleichung.
Zeilenumformungen ändern die Lösungsmenge nicht
Entsteht aus durch eine elementare Zeilenumformung, dann ist . Dasselbe gilt für endlich viele Umformungen nacheinander.
Beweisidee: Jede neue Gleichung folgt aus den alten, und jede Umformung lässt sich durch eine Umformung desselben Typs rückgängig machen.
. Sei eine Lösung aller alten Gleichungen. Bei Typ I sind die neuen Gleichungen dieselben in anderer Reihenfolge. Bei Typ II ist die neue Gleichung das -fache der alten; multipliziert man die wahre Aussage mit , bleibt sie wahr. Bei Typ III lautet die neue Gleichung : . Die linke Seite ist , weil die alten Gleichungen und erfüllt. Alle übrigen Gleichungen bleiben unverändert.
. Die Umformung lässt sich umkehren: Typ I durch nochmaliges Vertauschen derselben Zeilen; Typ II durch Multiplikation derselben Zeile mit , das es gibt, weil und ein Körper ist; Typ III durch Addition des -fachen von Zeile zu Zeile , wobei Zeile wegen unverändert geblieben ist. Die Umkehrung ist wieder elementar, also gilt nach dem ersten Teil auch diese Inklusion.
Für mehrere Umformungen wendet man das Ergebnis Schritt für Schritt an.
Welche Umformung kann die Lösungsmenge eines Systems mit drei Gleichungen verändern?
Zwei Zeilen gleichzeitig mit der jeweils anderen umformen
Zwei Zeilen gleichzeitig mit der jeweils anderen umformen
Im System , (einzige Lösung ) ersetzt man in einem Zug I durch I II und II durch II I. Es entstehen und . Dieses neue System wird von jedem erfüllt; die Lösungsmenge ist größer geworden.
Der zweite Schritt benutzt die alte Zeile I, die es nach dem ersten Schritt nicht mehr gibt; zusammen sind die beiden Ersetzungen keine Folge elementarer Umformungen und nicht umkehrbar. Erlaubt ist, in einem Schritt Vielfache einer Zeile zu mehreren anderen Zeilen zu addieren, solange diese eine Zeile dabei selbst unverändert bleibt. Genau das tut das Gauß-Verfahren.
Zeilenstufenform
In einer Zeile, die nicht nur Nullen enthält, heißt der erste Eintrag ungleich (von links) ihr Pivot. Eine Matrix ist in Zeilenstufenform, wenn
- alle Nullzeilen unter allen anderen Zeilen stehen, und
- der Pivot jeder Zeile echt weiter rechts steht als der Pivot der Zeile darüber.
Unter jedem Pivot stehen dann nur Nullen, und die Einträge ungleich bilden eine Treppe. Ist in Zeilenstufenform, heißen die Unbekannten, in deren Spalte ein Pivot steht, gebunden, die übrigen frei.
Gauß-Verfahren
Jede Matrix lässt sich durch endlich viele elementare Zeilenumformungen der Typen I und III in Zeilenstufenform bringen.
Induktion über die Zeilenzahl . Eine Matrix mit einer Zeile ist in Zeilenstufenform. Sei nun . Ist , sind wir fertig. Sonst sei die erste Spalte, die einen Eintrag ungleich enthält.
Schritt 1 (Pivot nach oben). Wähle eine Zeile mit und vertausche sie mit Zeile (Typ I). Danach ist , und die Spalten bis sind ganz .
Schritt 2 (darunter ausräumen). Addiere für jedes das -fache von Zeile zu Zeile (Typ III; die Division ist möglich, weil ein Körper ist). Danach steht in Spalte unter überall , und Zeile ist unverändert.
Schritt 3 (Rest). Die Zeilen bis bilden eine Matrix mit Zeilen, deren erste Spalten null sind. Nach Induktionsvoraussetzung lässt sie sich mit Umformungen der Typen I und III in Zeilenstufenform bringen. Diese Umformungen betreffen Zeile nicht, und weil sie nur Zeilen mit Nullen in den Spalten bis kombinieren, bleiben diese Nullen erhalten. Alle Pivots der unteren Zeilen liegen also rechts von Spalte , und die ganze Matrix ist in Zeilenstufenform.
Die erweiterte Matrix eines Systems in den Unbekannten ist in Zeilenstufenform. Wie viele freie Unbekannte gibt es?
Beispiel 1: genau eine Lösung
Beispiel 1: genau eine Lösung
Wir lösen das System aus der Einleitung. Ausgangspunkt ist .
Die erste Spalte hat oben den Pivot . Wir räumen darunter aus: und .
Beispiel 2: unendlich viele Lösungen
Beispiel 2: unendlich viele Lösungen
Gesucht sind alle Lösungen von , , über .
und :
Beispiel 3: keine Lösung
Beispiel 3: keine Lösung
Wir ändern in Beispiel 2 nur die letzte rechte Seite von auf . Dieselben Umformungen , und danach ergeben
Die letzte Zeile bedeutet , also . Kein erfüllt das, und weil die Umformungen die Lösungsmenge nicht ändern, hat auch das Ausgangssystem keine Lösung: . In der Sprache der Abbildungen: liegt nicht im Bild von . Die rechte Seite aus Beispiel 2 dagegen schon.
Spezielle Lösung plus Kern
Sei , , und sei eine Lösung von (eine spezielle Lösung). Dann ist
: Für ist , weil linear ist.
: Sei . Dann ist , also , und .
Was der Satz über die Beispiele sagt
Was der Satz über die Beispiele sagt
In Beispiel 2 ist eine spezielle Lösung (der Wert ), und durchläuft den Kern. Probe: . Die Lösungsmenge ist der Kern, eine Gerade durch , verschoben um .
Beispiel 3 hat dieselbe Matrix und damit denselben Kern, aber keine spezielle Lösung. Der Satz sagt nichts über die Existenz einer Lösung; er beschreibt nur, wie alle Lösungen aussehen, sobald man eine hat.
Folgerungen: Ist lösbar, dann ist die Lösung genau dann eindeutig, wenn ist. Ist und unendlich (etwa , , ), gibt es unendlich viele Lösungen, denn mit im Kern sind die für verschiedene verschieden. Über einem endlichen Körper wie gilt das nicht: Dort hat ein eindimensionaler Kern nur zwei Elemente. Hat das System mehr Unbekannte als Gleichungen (), ist nach der Dimensionsformel ; so wie in der Vorhersage am Anfang.
Ein lineares Gleichungssystem über hat die Lösungen und . Welche Aussage folgt daraus sicher?
- 1Lineares Gleichungssystem
Ein lineares Gleichungssystem mit 3 Gleichungen und 3 Unbekannten (, , ). Lösen mit dem Gauß-Verfahren: Man schreibt nur die Zahlen vor den Unbekannten und die rechten Seiten in eine erweiterte Matrix und formt die Zeilen so um, dass die Unbekannten nach und nach wegfallen. Das ist dasselbe wie das Additionsverfahren aus der Schule, nur übersichtlicher aufgeschrieben.
- 2Erweiterte Matrix
Die erweiterte Matrix: links die Koeffizienten, rechts vom Strich die rechten Seiten.
- 3Zeilenumformung
In der ersten Spalte alle anderen Einträge zu 0 machen: Von jeder anderen Zeile wird das passende Vielfache der 1. Zeile abgezogen.
- 4Zeile skalieren
Zeile 2 durch teilen, damit an der Pivotstelle eine 1 steht.
- 5Zeilenumformung
In der zweiten Spalte alle anderen Einträge zu 0 machen: Von jeder anderen Zeile wird das passende Vielfache der 2. Zeile abgezogen.
- 6Zeile skalieren
Zeile 3 durch teilen, damit an der Pivotstelle eine 1 steht.
- 7Zeilenumformung
In der dritten Spalte alle anderen Einträge zu 0 machen: Von jeder anderen Zeile wird das passende Vielfache der 3. Zeile abgezogen.
- 8Lösung
Links steht die Einheitsmatrix, rechts kann man die Lösung direkt ablesen. Probe: Einsetzen in alle Gleichungen stimmt.
Ergebnis
Probier es aus
Zusammenfassung
Ein lineares Gleichungssystem ist eine Gleichung mit ; man rechnet mit der erweiterten Koeffizientenmatrix .
Elementare Zeilenumformungen (vertauschen, mit multiplizieren, Vielfaches einer anderen Zeile addieren) ändern die Lösungsmenge nicht, weil jede neue Gleichung aus den alten folgt und jede Umformung umkehrbar ist.
Das Gauß-Verfahren bringt jede Matrix in Zeilenstufenform: Pivot nach oben, darunter ausräumen, mit den restlichen Zeilen weitermachen.
Eine Zeile mit heißt: keine Lösung. Sonst sind die Unbekannten ohne Pivot frei wählbar, und die übrigen folgen durch Rückwärtseinsetzen.
Ist eine Lösung, dann ist . Eindeutig lösbar heißt lösbar und .
Lösbar ist genau dann, wenn im Bild von liegt. Bei mehr Unbekannten als Gleichungen ist der Kern nie .
Nie zwei Zeilen gleichzeitig mit der jeweils anderen umformen: Das ist nicht umkehrbar und kann Lösungen hinzufügen.
Übungen
Welche erweiterte Koeffizientenmatrix gehört zum System , in den Unbekannten ?
Löse , , mit dem Gauß-Verfahren. Wie groß ist ?
Welche Matrix ist in Zeilenstufenform?
Für welche reelle Zahl hat das System , keine Lösung?
Wie viele freie Unbekannte hat das homogene System mit , nachdem man auf Zeilenstufenform gebracht hat?
Bestimme alle reellen Lösungen von , und schreibe die Lösungsmenge in der Form .
Sei und . Beweise: Die Lösungsmenge ist genau dann ein Untervektorraum von , wenn ist.