Kurs:Grundkurs Mathematik (Osnabrück 2016-2017)/Teil II/Vorlesung 32

Aus Wikiversity
Zur Navigation springen Zur Suche springen
„Verwandle große Schwierigkeiten in kleine und kleine in gar keine“
Chinesische Weisheit



Das Lösen von linearen Gleichungssystemen

Lineare Gleichungssysteme werden mit dem Eliminationsverfahren gelöst, bei dem nach und nach Variablen eliminiert werden und schließlich ein besonders einfaches äquivalentes Gleichungssystem entsteht, das direkt gelöst werden kann (bzw. von dem gezeigt werden kann, dass es keine Lösung besitzt). Systeme mit zwei Gleichungen in zwei Variablen haben wir schon in der letzten Vorlesung behandelt. Wir fahren mit einem typischen Beispiel fort.


Beispiel  

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[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.



Definition  

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.



Lemma  

Es sei ein Körper und

ein inhomogenes lineares Gleichungssystem über .

Dann führen die folgenden Manipulationen an diesem Gleichungssystem zu einem äquivalenten Gleichungssystem.

  1. Das Vertauschen von zwei Gleichungen.
  2. Die Multiplikation einer Gleichung mit einem Skalar .
  3. Das einfache Weglassen einer Gleichung, die doppelt vorkommt.
  4. Das Verdoppeln einer Gleichung (im Sinne von eine Gleichung zweimal hinschreiben).
  5. Das Weglassen oder Hinzufügen einer Nullzeile (einer Nullgleichung).
  6. Das Ersetzen einer Gleichung durch diejenige Gleichung, die entsteht, wenn man zu eine andere Gleichung des Systems addiert.

Beweis  

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.



Lemma  

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.

Beweis  

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.



Satz  

Jedes (inhomogene) lineare Gleichungssystem über einem Körper

lässt sich durch die in Lemma 32.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 .

Beweis  

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 zwei Gleichungen mit 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.

Bemerkung  

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 36.11.


Bemerkung  

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.


Bemerkung  

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.


Bemerkung  

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



Satz  

Es sei ein inhomogenes lineares Gleichungssystem über einem Körper in Dreiecksgestalt

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.

Beweis  

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. Ein beliebiges lineares Gleichungssystem formt man mit Hilfe des Eliminationslemmas in ein äquivalentes lineares Gleichungssystem in Stufengestalt um. Dann stellt man fest, dass es entweder keine Lösung besitzt oder aber man kann aus der Stufengestalt eine Beschreibung der Lösungsmenge erhalten.



Fußnoten
  1. 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.
  2. 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.


<< | Kurs:Grundkurs Mathematik (Osnabrück 2016-2017)/Teil II | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)