Lineares Gleichungssystem

Das Lineare Gleichungssysteme ist ein Begriff aus dem mathematischen Teilgebiet der linearen Algebra. Man bezeichnet damit ein System aus linearen Gleichungen, die mehrere unbekannte Größen (Variablen, Unbekannte) enthalten.

Ein entsprechendes System für drei Unbekannte $x_{1}$ , $x_{2}$ , $x_{3}$ sieht beispielsweise wie folgt aus:

{\begin{matrix}3x_{1}&+&2x_{2}&-&x_{3}&=&1\\2x_{1}&-&2x_{2}&+&4x_{3}&=&-2\\-x_{1}&+&{1 \over 2}x_{2}&-&x_{3}&=&0\end{matrix}}

Allgemein lässt sich ein lineares Gleichungssystem mit $m$ Gleichungen und $n$ Unbekannten immer in die folgende Form bringen:

{\begin{matrix}a_{11}x_{1}+a_{12}x_{2}&\cdots &a_{1n}x_{n}&=&b_{1}\\a_{21}x_{1}+a_{22}x_{2}&\cdots &a_{2n}x_{n}&=&b_{2}\\&&&\vdots &\\a_{m1}x_{1}+a_{m2}x_{2}&\cdots &a_{mn}x_{n}&=&b_{m}\\\end{matrix}}

Man spricht von einem homogenen Gleichungssystem, wenn alle $b_{i}$ gleich 0 sind. Ansonsten nennt man das Gleichungssystem inhomogen.

Das Standardproblem besteht nun darin, für die Unbekannten Werte zu finden, so dass alle Gleichungen des Gleichungssystems erfüllt sind.

Beispiel

Aufgabe

Ein Vater und ein Sohn sind zusammen 62 Jahre alt. Vor sechs Jahren war der Vater viermal so alt wie der Sohn. Wie alt ist jeder?

Lösung

Gesetzt das Alter des Vater sei x und das Alter des Sohnes y. So gilt

(1) x + y = 62
(2) x - 6 = 4 * (y -6)

Es ergibt sich also ein lineares Gleichungssystem mit zwei Unbekannten.

Formt man (1) durch Subtraktion von x zu

(1') y = 62 - x

um und setzt dies in (2) ein, so folgt

x - 6 = 4 * (62 - x - 6) | Faktoren in der Klammer zusammenfassen
x - 6 = 4 * (56 - x)     | Klammer ausmultiplizieren
x - 6 = 224 - 4x         | + 4x + 6
5x    = 230              | : 5
x     = 46

setzt man dieses Ergebnis in (1') ein so folgt dann

y = 62 - 46
y = 16

Also ist der Vater 46 Jahre und der Sohn 16 Jahre alt, zusammen also 62 Jahre. Vor sechs Jahren waren der Vater 40 Jahre und der Sohn 10 Jahre alt, der Vater also viermal so alt wie der Sohn.

Matrixdarstellung

Die Koeffizienten $a_{ij}\,$ können zu einer Matrix $A\,$ ,

die Unbekannten $x_{i}\,$ zu einem Vektor $x\,$ und

die rechte Seite, bestehend aus $b_{j}\,$ , zu einem Vektor $b\,$

zusammengefasst werden:

A={\begin{pmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}\end{pmatrix}};\qquad x={\begin{pmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{pmatrix}};\qquad b={\begin{pmatrix}b_{1}\\b_{2}\\\vdots \\b_{m}\end{pmatrix}}

Damit ergibt sich die allgemeine Form des linearen Gleichungssystems in Matrixdarstellung:

A\cdot x=b

mit

A\in \mathbb {K} ^{{m}\times {n}}

,

b\in \mathbb {K} ^{m}

und

x\in \mathbb {K} ^{n}

Dabei ist $\mathbb {K}$ eine Menge, die Körperstruktur besitzt, was vor allem bedeutet, dass die Addition und die Multiplikation definiert sind. ( $\mathbb {K} ^{m}$ ist die Kurzschreibweise von $\mathbb {K} ^{{m}\times {1}}$ und damit ist $\mathbb {K} ^{{1}\times {1}}=\mathbb {K}$ )

Lösbarkeit

$A\cdot x=b$ mit $A\in \mathbb {K} ^{{m}\times {n}}$ , $b\in \mathbb {K} ^{m}$ und $x\in \mathbb {K} ^{n}$ ist abhängig von $m$ , $n$ , den Koeffizienten $A$ und der rechten Seite $b$ nicht immer lösbar oder hat eine eindeutige Lösung. Im Prinzip ist jede der $m$ Gleichungen eine Information über die $n$ Unbekannten. Sind zu wenig Informationen vorhanden, sind mehrere Lösungen möglich - man spricht hierbei von einem unterbestimmten Gleichungssystem. Auf der anderen Seite kann manchmal keine Lösung vorhanden sein, wenn Informationen vorhanden sind, die sich widersprechen. Dies ist oft bei überbestimmten Gleichungssystemen, bei denen es mehr Gleichungen als Unbekannte gibt, der Fall.

Beispielsweise hat $x_{1}+x_{2}=1$ unendlich viele Lösungen, nämlich abhängig von $x_{1}$ löst jedes $x_{2}=1-x_{1}$ diese Gleichung. Das Gleichungssystem aus den beiden Gleichungen $x_{1}=1$ und $x_{1}=2$ hat hingegen keine Lösung, da $x_{1}$ nicht gleichzeitig beide Gleichungen erfüllen kann - es kann ja nur entweder $1$ oder $2$ sein.

Das Gleichungssystem $A\cdot x=b$ ist genau dann lösbar, wenn der Rang der Matrix $A$ gleich dem Rang der erweiterten Matrix $(A|b)$ ist.

Dabei ist die erweiterte Matrix $(A|b):={\begin{pmatrix}a_{11}&a_{12}&\cdots &a_{1n}&b_{1}\\a_{21}&a_{22}&\cdots &a_{2n}&b_{2}\\\vdots &\vdots &\ddots &\vdots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}&b_{m}\end{pmatrix}}$ .

Eindeutig lösbar ist $A\cdot x=b$ , wenn die Anzahl der Unbekannten $n$ gleich dem Rang der erweiterten Matrix ist.

Nachdem Zeilenrang gleich Spaltenrang bei einer Matrix gilt, ist ein überbestimmtes, lineares Gleichungssystem also trotzdem lösbar, wenn durch Hinzunahme der rechten Seite in die Matrix $A$ zu $(A|b)$ keine Vergrößerung des Ranges stattfindet. In diesem Fall sind die Gleichungen linear abhängig und die Information der Gleichungen also redundant. Wenn die Anzahl linear unabhängiger Gleichungen, der Rang der erweiterten Matrix oder auch die Anzahl der unabhängigen Informationen gleich der Anzahl Unbekannter ist, existiert also genau eine Lösung. Gibt es weniger Unbekannte, so sind diese nicht eindeutig bestimmbar; das System ist unterbestimmt.

Bei Anwendungen (z.B. Geodäsie) sind oft überbestimmte Gleichungssysteme zu lösen. Um den Messfehler von Messungen zu verringern, wird auf verschiedene Arten gemessen und es existieren mehr Messergebnisse als Unbekannte. In der Regel widersprechen sich die Gleichungen, wenn mehr Gleichungen als Unbekannte vorhanden sind. Als Lösungsmethode hat es sich bewährt, zu dem Konstantenvektor b einen geeigneten (zunächst fast beliebigigen) sogenannten Residuenvektor zu addieren um das Gleichungssystem widerspruchsfrei zu machen. Als weitere Bedingung wird dann fast immer gestellt, dass der Residuenvektor minimal wird. Was unter minimal zu verstehen ist, kann durchaus von der Aufgabe abhängen. In der Regel wird gefordert, dass die Gaußsche Norm des Residuenvektors (die Addition der einzelnen Komponentenquadrate des Residuenvektors) zum Minimum wird. Das entspricht dem Gesetz der zufälligen Messabweichungen.

Ob ein Gleichungssystem eindeutig lösbar ist kann man mit Hilfe der Determinante überprüfen. Ist der Wert der Koeffizientendeterminante ungleich Null, ist das Gleichungssystem eindeutig lösbar.

Lösungsmenge

Die Lösungen eines homogenen linearen Gleichungssystem bilden einen Vektorraum, d.h. mit Lösungen $x_{i}\in \mathbb {K} ^{n}$ und beliebigen Koeffizienten $\alpha _{i}\in \mathbb {K}$ gilt: $\sum \alpha _{i}\,x_{i}$ ist eine Lösung. Man nennt diesen Raum den Kern der Matrix . Ist ein homogenes System eindeutig lösbar, ist nur der Nullvektor Lösung ("triviale Lösung").

Die Lösungsmenge eines inhomogenen linearen Gleichungssystem ist eine lineare Mannigfaltigkeit bzw. ein affiner Raum.

Determinante

Eine Determinante ist eine Funktion, die jeder quadratischen Matrix, auch den Matrizen von linearen Gleichungssystemen, eine Zahl zuordnet. Ein zweireihiges Gleichungssystem hat die Koeffizientendeterminante

\det(A)={\begin{vmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{vmatrix}}=a_{11}*a_{22}-a_{21}*a_{12}

.

Die Koeffizientendeterminante, also die Determinante der Zahlen auf der linken Seite des Gleichungssystems, gibt Informationen über die Lösbarkeit des Systems. Ist der Wert der Koeffizientendeterminante ungleich Null, hat das lineare Gleichungssystem eine eindeutige Lösung. Ist der Wert der Koeffizientendeterminante gleich Null hängt die Lösbarkeit von den Werten der Nebendeterminanten ab. Bei diesen wird jeweils eine Spalte der Koeffizientendeterminante durch die Spalte der rechten Seite (den Vektor b) ersetzt. Haben alle Nebendeterminanten den Wert Null hat das System unendlich viele Lösungen, ist der Wert einer Nebendeterminante ungleich Null ist das Gleichungssystem unlösbar. Nach der Cramerschen Regel kann durch die Determinanten auch die Lösung des Gleichungssystems berechnet werden. Die Berechnung größerer Determinanten erfordert einen großen Rechenaufwand, ist aber vor allem für theoretische Überlegungen nützlich.

Formen von Gleichungssystemen

Lineare Gleichungssysteme können in Formen vorliegen, in denen sie leicht gelöst werden können. In der Stufenform (auch Stufengestalt oder Staffelgestalt) verringert sich in jeder Zeile die Zahl der Unbekannten um mindestens eine, die dann auch in den darauffolgenden Zeilen nicht mehr vorkommt. Die Dreiecksform ist ein Sonderfall der Stufenform, in ihr hat jede Zeile genau eine Unbekannte weniger als die Vorhergehende. Das Gaußsche Eliminationsverfahren bringt Gleichungssysteme in eine dieser beiden Formen.

Liegt ein Gleichungssystem in Stufen- oder Dreieckform vor, kann es durch Rücksubstitution leicht gelöst werden. Das heißt man berechnet die Unbekannte der letzten Zeile und setzt diese in die darüberliegende Zeile ein um die nächste Unbekannte zu berechnen. Die Koeffizientendeterminante kann bei der Dreiecksform berechnet werden, indem man die ersten Koeffizienten jeder Zeile miteinander multipliziert. Ist einer der Koeffizienten der Diagonal Null, das heißt das System ist in Stufen- aber nicht in Dreiecksform, ist die Koeffizientendeterminante Null und das System nicht eindeutig lösbar.

Beispiele (die Koeffizienten von ausgelassenen Elementen sind Null):

Stufenform

{\begin{matrix}a_{11}x_{1}+a_{12}x_{2}+a_{13}x_{3}&=&b_{1}\\\qquad \qquad \qquad \quad a_{23}x_{3}&=&b_{2}\\\end{matrix}}

Dreiecksform:

{\begin{matrix}a_{11}x_{1}+a_{12}x_{2}+a_{13}x_{3}&=&b_{1}\\\qquad \qquad a_{22}x_{2}+a_{23}x_{3}&=&b_{2}\\\qquad \qquad \qquad \quad a_{33}x_{3}&=&b_{3}\\\end{matrix}}

Die reduzierte Stufenform ist wiederum ein Sonderfall der Stufenform, in ihr treten die jeweils ersten Unbekannten jeder Zeile nur ein einziges Mal auf und haben den Wert Eins. Der Gauß-Jordan-Algorithmus bringt Gleichungssysteme in diese Form, in der die Ergebnisse direkt abgelesen werden können. Ist ein Gleichungssystem nicht überbestimmt sind Systeme in der reduzierten Stufenform gleichzeitig in der Diagonalform, das heißt jede Unbekannte tritt nur einmal, auf der Hauptdiagonale liegend, auf. Die Koeffizientendeterminante hat bei dieser Form den Wert eins.

reduzierte Stufenform

{\begin{matrix}x_{1}\qquad +a_{14}x_{4}&=&b_{1}\\\quad x_{2}\quad +a_{24}x_{4}&=&b_{2}\\\qquad \ x_{3}+a_{34}x_{4}&=&b_{3}\\\end{matrix}}

Diagonalform

{\begin{matrix}x_{1}\qquad \qquad &=&b_{1}\\\quad x_{2}\qquad &=&b_{2}\\\qquad \ x_{3}&=&b_{3}\\\end{matrix}}

erlaubte Umformungen

Bei linearen Gleichungssystemen gibt es drei elementare Zeilenumformungen:

Das Vertauschen von zwei (kompletten) Zeilen
Das Multiplizieren einer Zeile mit einer von Null verschiedenen Zahl
Das Addieren einer Zeile oder des Vielfachen einer Zeile zu einer anderen

Bei diesen Umformungen handelt es sich um Äquivalenzumformungen, das heißt durch diese Umformungen ändert sich die Lösungsmenge eines Gleichungssystems nicht.

Lösungsverfahren

Die Methoden zur Lösung von linearen Gleichungssystemen unterteilt man in iterative und direkte Verfahren. Beispiele für direkte Verfahren sind das Einsetzungsverfahren, das Gleichsetzungsverfahren und das Additionsverfahren für einfache Gleichungssystemen, das auf dem Additionsverfahren basierende Gaußsche Eliminationsverfahren, das ein Gleichungssystem auf Stufenform bringt, und die Cramersche Regel, die mit Determinanten arbeitet. Eine Variante des Gauß-Verfahrens ist die Cholesky-Zerlegung, die nur für symmetrische, positiv definite Matrizen funktioniert.

Iterative Verfahren sind beispielsweise die zur Klasse der Splitting-Verfahren gehörenden Gauß-Seidel- und Jacobi-Verfahren. Diese konvergieren nicht für jede Matrix und sind für viele praktische Probleme sehr langsam. Modernere Verfahren sind vorkonditionierte Krylow-Unterraum-Verfahren, die insbesondere für große dünnbesetzte Matrizen sehr schnell sind.

Siehe auch

Weblinks

Applet zum Lösen linearer Gleichungssysteme Benutzerfreundliches Applet, das beliebige lineare Gleichungssysteme anschaulich schrittweise erklärend mit Hilfe von Gauß-Elimination und Gauß-Jordanverfahren löst.
Arndt Brünner Scripts Der Online-Rechner zum Lösen linearer Gleichungssysteme.
Online-Löser für lineare Gleichungssysteme (englisch)
Gleichsetzungsverfahren für Schüler
Einsetzungsverfahren für Schüler
Additionsverfahren für Schüler
Wann welches Verfahren?