Kurs:Lineare Algebra (Osnabrück 2017-2018)/Teil I/Vorlesung 5
- Das Lösen von linearen Gleichungssystemen
Es ist von vornherein gar nicht so klar, was man unter dem Lösen eines (linearen) Gleichungssystems verstehen soll. Jedenfalls geht es um eine möglichst gute Beschreibung der Lösungsmenge. Wenn es nur eine Lösung gibt, so geht es darum, diese Lösung zu finden und anzugeben. Wenn es überhaupt keine Lösung gibt, geht es darum, dies festzustellen und zu begründen. Im Allgemeinen ist aber die Lösungsmenge eines Gleichungssystems groß. Dann versteht man unter der Lösung eines Systems, freie Variablen zu identifizieren, die beliebige Werte annehmen dürfen, und explizit zu beschreiben, wie die anderen (abhängigen) Variablen von diesen freien Variablen abhängen. Man spricht auch von einer expliziten Beschreibung der Lösungsmenge.
Lineare Gleichungssysteme können systematisch mit dem Eliminationsverfahren gelöst werden, bei dem nach und nach Variablen eliminiert werden und schließlich ein besonders einfaches äquivalentes Gleichungssystem (in Dreiecksgestalt) entsteht, das direkt gelöst werden kann (bzw. von dem gezeigt werden kann, dass es keine Lösung besitzt). Wir betrachten ein typisches Beispiel mit vielen Variablen.
Wir wollen das inhomogene lineare Gleichungssystem
über (oder ) lösen. Wir eliminieren zuerst , indem wir die erste Zeile beibehalten, die zweite Zeile durch und die dritte Zeile durch ersetzen. Das ergibt
Wir könnten jetzt aus der (neuen) dritten Zeile mit Hilfe der zweiten Zeile eliminieren. Wegen der Brüche eliminieren wir aber lieber (dies eliminiert gleichzeitig ). Wir belassen also die erste und zweite Zeile und ersetzen die dritte Zeile durch . Dies ergibt, wobei wir das System in einer neuen Reihenfolge der Variablen[1] aufschreiben, das System
Wir können uns nun beliebig (oder „frei“) vorgeben. Die dritte Zeile legt dann eindeutig fest, es muss nämlich
gelten. In der zweiten Gleichung können wir wieder beliebig vorgeben, was dann eindeutig festlegt, nämlich
Die erste Zeile legt dann fest, nämlich
Daher kann man die Gesamtlösungsmenge als
schreiben. Eine besonders einfache Lösung ergibt sich, wenn man die freien Variablen und gleich setzt. Dies führt auf die spezielle Lösung
In der allgemeinen Lösung kann man und als Koeffizienten rausziehen und dann die Lösungsmenge auch als
schreiben. Dabei ist
eine Beschreibung der allgemeinen Lösung des zugehörigen homogenen linearen Gleichungssystems.
Es sei ein Körper und seien zwei (inhomogene) lineare Gleichungssysteme zur gleichen Variablenmenge gegeben. Die Systeme heißen äquivalent, wenn ihre Lösungsmengen übereinstimmen.
Es sei ein Körper und
ein inhomogenes lineares Gleichungssystem über .
Dann führen die folgenden Manipulationen an diesem Gleichungssystem zu einem äquivalenten Gleichungssystem.
- Das Vertauschen von zwei Gleichungen.
- Die Multiplikation einer Gleichung mit einem Skalar .
- Das einfache Weglassen einer Gleichung, die doppelt vorkommt.
- Das Verdoppeln einer Gleichung (im Sinne von eine Gleichung zweimal hinschreiben).
- Das Weglassen oder Hinzufügen einer Nullzeile (einer Nullgleichung).
- Das Ersetzen einer Gleichung durch diejenige Gleichung, die entsteht, wenn man zu eine andere Gleichung des Systems addiert.
Die meisten Aussagen sind direkt klar. (2) ergibt sich einfach daraus, dass wenn
gilt, dass dann auch
für jedes gilt. Bei kann man diesen Übergang durch Multiplikation mit rückgängig machen.
(6). Es sei die Gleichung
und die Gleichung
Wenn ein Tupel die beiden Gleichungen erfüllt, so erfüllt es auch die Gleichung . Und wenn das Tupel die beiden Gleichungen und erfüllt, so auch die Gleichung und .
Für die praktische Lösung eines linearen Gleichungssystems sind die beiden Manipulationen (2) und (6) am wichtigsten, wobei man in aller Regel diese beiden Schritte kombiniert und eine Gleichung durch eine Gleichung der Form
(mit )
ersetzt. Dabei wird
so gewählt, dass die neue Gleichung eine Variable weniger besitzt als die alte. Man spricht von Elimination einer Variablen. Diese Elimination wird nicht nur für eine Zeile durchgeführt, sondern für alle Zeilen mit Ausnahme von einer
(geeignet gewählten)
„Arbeitszeile“ und mit einer fixierten „Arbeitsvariablen“. Das folgende Eliminationslemma beschreibt diesen Rechenschritt.
Es sei ein Körper und ein (inhomogenes) lineares Gleichungssystem über in den Variablen . Es sei eine Variable, die in mindestens einer Gleichung mit einem von verschiedenen Koeffizienten vorkommt.
Dann lässt sich jede von verschiedene[2] Gleichung durch eine Gleichung ersetzen, in der nicht mehr vorkommt, und zwar so, dass das neue Gleichungssystem , das aus und den Gleichungen besteht, äquivalent zum Ausgangssystem ist.
Durch Umnummerieren kann man erreichen. Es sei die Gleichung
(mit ) und die Gleichung
Dann hat die Gleichung
die Gestalt
in der nicht mehr vorkommt. Wegen sind die Gleichungssysteme äquivalent.
Das praktische Verfahren, bei dem man sukzessive das Verfahren im Beweis des vorstehenden Lemmas anwendet, um auf Dreiecksgestalt bzw. Stufengestalt zu kommen, nennt man Gaußsches Eliminationsverfahren
(oder Additionsverfahren).
Es werden also Variablen eliminiert, indem man geeignete Vielfache von Gleichungen zu anderen Gleichungen hinzuaddiert.
Jedes (inhomogene) lineare Gleichungssystem über einem Körper
lässt sich durch die in Lemma 5.3 beschriebenen elementaren Umformungen und durch das Weglassen von überflüssigen Gleichungen in ein äquivalentes lineares Gleichungssystem der Stufenform
überführen, bei dem alle Startkoeffizienten von verschieden sind.
Dabei ist (bei ) die letzte Zeile überflüssig oder aber (bei ) das System besitzt keine Lösung.
Durch Variablenumbenennungen erhält man ein äquivalentes System der Form
mit Diagonalelementen .
Dies folgt direkt aus dem Eliminationslemma, mit dem man sukzessive Variablen eliminiert. Man wendet es auf die erste (in der gegebenen Reihenfolge) Variable (diese sei ) an, die in mindestens einer Gleichung mit einem von verschiedenen Koeffizienten auftaucht. Diese Eliminationsschritte wendet man solange an, solange das im Eliminationsschritt entstehende variablenreduzierte Gleichungssystem (also ohne die vorhergehenden Arbeitsgleichungen) noch mindestens eine Gleichung mit einem von verschiedenen Koeffizienten erhält. Wenn dabei Gleichungen in der Form der letzten Gleichung übrig bleiben, und diese nicht alle die Nullgleichung sind, so besitzt das System keine Lösung. Wenn wir setzen und die anderen Variablen mit benennen, so erhält man das angegebene System in Dreiecksgestalt.
Es kann sein, dass die Variable gar nicht in dem System mit einem von verschiedenen Koeffizienten vorkommt, und, dass in einer Variablenelimination gleichzeitig mehrere Variablen eliminiert werden. Dann erhält man wie beschrieben ein Gleichungssystem in Stufenform, das erst durch Variablenvertauschungen in die Dreiecksform gebracht werden kann.
Ein lineares Gleichungssystem kann man kurz als
mit einer -Matrix und einem -Tupel schreiben. Die Manipulationen an den Gleichungen, die man im Gaußschen Eliminationsverfahren durchführt, kann man direkt an der Matrix durchführen oder aber an der erweiterten Matrix, die entsteht, wenn man um die Spalte ergänzt. Im Wesentlichen ersetzt man eine Zeile durch die Summe der Zeile mit einem Vielfachen einer anderen Zeile. Dies hat den Vorteil, dass man die Variablen nicht mitschleppen muss. Dann sollte man allerdings keine Variablenvertauschung durchführen. Zum Schluss muss man die entstandene Matrix in Stufenform wieder als lineares Gleichungssystem interpretieren.
Gelegentlich möchte man ein simultanes lineares Gleichungssystem der Form
lösen. Es sollen also für verschiedene Störvektoren Lösungen des zugehörigen inhomogenen Gleichungssystems berechnet werden. Grundsätzlich könnte man dies als voneinander unabhängige Gleichungssysteme betrachten, es ist aber geschickter, die Umwandlungen, die man auf der linken Seite macht, um Dreiecksgestalt zu erreichen, simultan auf der rechten Seiten mit allen Störvektoren durchzuführen. Ein wichtiger Spezialfall bei liegt vor, wenn die Störvektoren die Standardvektoren durchlaufen, siehe Verfahren 12.11.
Wir besprechen noch kurz weitere Verfahren, ein lineares Gleichungssystem zu lösen.
Ein weiteres Verfahren, ein lineares Gleichungssystem zu lösen, ist das Einsetzungsverfahren. Dabei werden ebenfalls Variablen sukzessive eliminiert, allerdings in einer anderen Weise. Wenn man mit diesem Verfahren die Variable eliminieren möchte, so löst man eine Gleichung, sagen wir , in der mit einem von verschiedenen Koeffizienten vorkommt, nach auf, und erhält eine neue Gleichung der Form
wobei in die Variable nicht vorkommt. In allen weiteren Gleichungen ersetzt man die Variable durch und erhält (nach Umformungen) ein Gleichungssystem ohne die Variable , das zusammen mit äquivalent zum Ausgangssystem ist.
Ein anderes Verfahren, ein lineares Gleichungssystem zu lösen, ist das Gleichsetzungsverfahren. Dabei werden ebenfalls Variablen sukzessive eliminiert, allerdings in anderer Weise. Bei diesem Verfahren löst man die Gleichungen , , nach einer festen Variablen, sagen wir auf. Es seien (nach Umordnung) die Gleichungen, in denen die Variable mit einem von verschiedenen Koeffizienten vorkommt. Diese Gleichungen bringt man in die Form
wobei in die Variable nicht vorkommt. Das Gleichungssystem bestehend aus
ist zum gegebenen System äquivalent. Mit diesem System ohne fährt man fort.
Die in Satz 5.5, Bemerkung 5.8 und Bemerkung 5.9 beschriebenen Verfahren zur Lösung eines linearen Gleichungssystems unterscheiden sich hinsichtlich Schnelligkeit, strategischer Konzeption, Systematik, Fehleranfälligkeit. Beim Eliminationsverfahren tritt die systematische Reduzierung der Variablenanzahl (Dimensionsreduktion) besonders deutlich hervor und man kann mit ihm eigentlich keine Fehler (außer Rechenfehler) machen und weiß immer, wie es weiter geht. Allerdings treten diese Vorteile erst ab zumindest drei Variablen hervor. Bei zwei Variablen ist es nahezu egal, welchen Weg man wählt. Die Bewertung der Verfahren hängt auch wesentlich von konkreten Besonderheiten des vorliegenden Systems ab. Solche Besonderheiten muss man berücksichtigen, um „Abkürzungen“ auf dem Weg zur Lösung zu sehen. Die bewusste Wahl eines für das konkrete Problem angemessenen Lösungsweges nennt man Adaptivität (ein Begriff, der im didaktischen Kontext mit unterschiedlichen Bedeutungen verwendet wird). Wenn beispielsweise eine Zeile des Systems die Form besitzt, so sollte man erkennen, dass daraus unmittelbar ein Teil der Lösung ablesbar ist, und nicht zu dieser Zeile andere Zeilen hinzuaddieren und dadurch viele Variablen reinkriegen. Hier sollte man stattdessen in den anderen Zeilen das durch die ersetzen und dann weiter machen. Oder: Wenn es vier Gleichungen gibt, wobei in zwei Gleichungen nur die Variablen und und in den beiden anderen Gleichungen nur die Variablen und vorkommen, so sollte man erkennen, dass im Prinzip zwei entkoppelte lineare Systeme mit je zwei Variablen vorliegen und diese getrennt lösen. Oder: Es kann sein, dass ein kleines Teilsystem des Gleichungssystems bereits sicherstellt, dass es gar keine Lösung gibt. Dann muss man nur dies herausarbeiten und die anderen Gleichungen gar nicht berücksichtigen. Und: die genaue Fragestellung beachten! Wenn gefragt ist, ob ein bestimmtes Tupel eine Lösung ist, so muss man das Tupel nur in die Gleichungen einsetzen, Manipulationen an den Gleichungen sind nicht nötig.
Unter einem linearen Ungleichungssystem über den rationalen Zahlen oder den reellen Zahlen versteht man ein System der Form
wobei gleich oder ist. Die Lösungsmenge ist deutlich schwieriger zu beschreiben als im Gleichungsfall. Eine Eliminierung von Variablen ist im Allgemeinen nicht möglich.
- Lineare Gleichungssysteme in Dreiecksgestalt
Es sei ein inhomogenes lineares Gleichungssystem über einem Körper in Dreiecksgestalt
mit gegeben, wobei vorne die Diagonalelemente alle ungleich seien.
Dann stehen die Lösungen in Bijektion zu den Tupeln . D.h. die hinteren Einträge sind frei wählbar und legen eine eindeutige Lösung fest, und jede Lösung wird dabei erfasst.
Dies ist klar, da bei gegebenem die Zeilen von unten nach oben sukzessive die anderen Variablen eindeutig festlegen.
Bei
gibt es keine freien Variablen und es ist
und das Gleichungssystem besitzt genau eine Lösung.
- Das Superpositionsprinzip für lineare Gleichungssysteme
Es sei eine Matrix über einem Körper . Es seien und zwei -Tupel und es sei eine Lösung des linearen Gleichungssystems
und eine Lösung des Systems
Dann ist eine Lösung des Systems
Beweis
Es sei ein Körper und
ein inhomogenes lineares Gleichungssystem über und es sei
das zugehörige homogene Gleichungssystem. Wenn eine Lösung des inhomogenen Systems und eine Lösung des homogenen Systems ist,
so ist eine Lösung des inhomogenen Systems.
Dies folgt unmittelbar aus Satz 5.13.
Dies bedeutet insbesondere, dass wenn der Lösungsraum des homogenen Gleichungssystems ist und wenn eine Lösung des inhomogenen Gleichungssystems ist, dass dann die Abbildung
eine Bijektion zwischen und der Lösungsmenge der inhomogenen Gleichungssystems ist.
- Fußnoten
- ↑ Eine solche Umstellung ist ungefährlich, wenn man den Namen der Variablen mitschleppt. Wenn man dagegen das System in Matrizenschreibweise aufführt, also die Variablennamen einfach weglässt, so muss man sich diese Spaltenvertauschungen merken.
- ↑ Mit verschieden ist hier gemeint, dass die beiden Gleichungen einen unterschiedlichen Index im System haben. Es ist also sogar der Fall erlaubt, dass und dieselbe, aber doppelt aufgeführte Gleichung ist.
- Explizite Beschreibung (MSW)
- Eliminationsverfahren (MSW)
- Elimination einer Variablen (MSW)
- Eliminationslemma (MSW)
- Gaußsches Eliminationsverfahren (MSW)
- Additionsverfahren (MSW)
- Simultanes lineares Gleichungssystem (MSW)
- Einsetzungsverfahren (MSW)
- Gleichsetzungsverfahren (MSW)
- Adaptivität (MSW)
- Lineares Ungleichungssystem (MSW)
- Kurs:Lineare Algebra (Osnabrück 2017-2018)/Teil I/Vorlesungen