Lineares Gleichungssystem

Als lineares Gleichungssystem bezeichnet man in der linearen Algebra 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 nennt das Gleichungssystem homogen, wenn alle $b_{i}$ gleich 0 sind, ansonsten inhomogen. Hat das Gleichungssystem weniger Gleichungen als Unbekannte, so spricht man von einem unterbestimmten Gleichungssystem. Hat es jedoch mehr Gleichungen als Unbekannte nennt man es ein überbestimmtes Gleichungssystem.

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

Matrixform

Für die Behandlung von linearen Gleichungssystemen ist es nützlich, alle Koeffizienten $a_{ij}$ zu einer Matrix $A$, der sogenannten Koeffizientenmatrix zusammenzufassen:

$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}}$

Des Weiteren lassen sich auch alle Unbekannten und die rechte Seite des Gleichungssystems als Vektoren niederschreiben:

$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 schreibt sich ein lineares Gleichungssystem kurz

$Ax=b$

Sowohl die Koeffizienten $a_{ij}$, die Unbekannten $x_{i}$, als auch die rechten Seiten $b_{j}$ entstammen dem selben Körper. Insbesondere gilt

$A\in \mathbb {K} ^{{m}\times {n}}$, $b\in \mathbb {K} ^{m}$ und $x\in \mathbb {K} ^{n}$

Zur Festlegung eines linearen Gleichungssystems ist die Angabe der Unbekannten nicht nötig. Es genügt die Angabe der erweiterten Koeffizientenmatrix, die entsteht wenn an die Koeffizientenmatrix $A$ eine Spalte mit der rechten Seite $b$ des Gleichungssystems angefügt wird:

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

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

${\begin{matrix}(1)&x&+&y&=&62\\(2)&x&-&6&=&4&*&(y-6)\end{matrix}}$

Es ergibt sich also ein lineares Gleichungssystem mit zwei Unbekannten.

Formt man (1) durch Subtraktion von x zu

${\begin{matrix}(1')&y&=&62&-&x\end{matrix}}$

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

${\begin{matrix}(2)&x&-&6&=&4&*&(y-6)\\&x&-&6&=&4&*&(62-x-6)&\\&x&-&6&=&4&*&(56-x)&\\&x&-&6&=&224&-&4x&|&+4x\ +6\\&&&5x&=&230&&&|&\div 5\\&&&x&=&46\end{matrix}}$

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

${\begin{matrix}(1')&y&=&62&-&x\\&y&=&62&-&46\\&y&=&16\end{matrix}}$

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.

Lösbarkeit

Ein Vektor $x$ ist eine Lösung des linearen Gleichungssystems, wenn $A\cdot x=b$ gilt. Ob und wie viele Lösungen ein Gleichungssystem besitzt ist unterschiedlich. Bei linearen Gleichungssystemen treten drei Fälle auf:

• das lineare Gleichungssystem hat keine Lösung.
• das lineare Gleichungssystem hat genau eine Lösung.
• das lineare Gleichungssystem hat unendlich viele Lösungen.

Dabei ist das lineare Gleichungssystem genau dann lösbar, wenn der Rang der Koeffizientenmatrix $A$ gleich dem Rang der erweiterten Koeffizientenmatrix ist. Entspricht der Rang der erweiterten Koeffizientenmatrix auch noch der Anzahl der Unbekannten, so besitzt das Gleichungssystem genau eine Lösung.

Bei einem quadratischen Gleichungssystem gibt die Determinante Auskunft über die Lösbarkeit. Das Gleichungssystem ist genau dann eindeutig lösbar, wenn der Wert der Determinante der Koeffizientenmatrix ungleich Null ist. Ist der Wert jedoch 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. Nur wenn alle Nebendeterminanten den Wert Null haben, hat das System unendlich viele Lösungen, ansonsten ist das Gleichungssystem unlösbar.

Insbesondere überbestimmte Gleichungssysteme besitzen oft keine Lösung. Hier sind dann Gleichungen vorhanden, die im Widerspruch zueinander stehen. Beispielsweise besitzt das folgende Gleichungssystem keine Lösung, da $x_{1}$ nicht beide Gleichungen erfüllen kann:

${\begin{matrix}3x_{1}&=&2\\4x_{1}&=&2\end{matrix}}$

Dass ein lineares Gleichungssystem unendlich viele Lösungen hat, kommt dagegen insbesondere bei unterbestimmten Gleichungssystemen vor. Beispielsweise besitzt das folgende, aus nur einer Gleichung bestehende Gleichungssystem unendlich viele Lösungen, nämlich alle Vektoren mit $x_{2}=1-x_{1}$:

$x_{1}+x_{2}=1$

Lösungsmenge

Die Lösungsmenge eines linearen Gleichungssystems besteht aus allen Vektoren $x$, für die $Ax=b$ erfüllt ist:

$L=\{x|Ax=b\}.$

Liegt ein homogenes lineares Gleichungssystem vor, so bildet dessen Lösungsmenge einen Vektorraum. Damit sind für eine oder mehrere Lösungen $x_{i}\in \mathbb {K} ^{n}$ auch deren Linearkombinationen $\sum \alpha _{i}\,x_{i}$ (mit beliebigen $\alpha _{i}\in \mathbb {K}$) Lösungen des Gleichungssystems. Den so entstandenen Lösungsraum nennt man Kern der Matrix $A$. Das inhomogene Gleichungssystem ist genau dann eindeutig lösbar, wenn der Nullvektor die einzige Lösung („triviale Lösung“) des homogenen Gleichungssystems ist.

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

Die Lösungsmenge eines linearen Gleichungssystems verändert sich nicht, wenn man eine der drei elementaren Zeilenumformungen durchführt

1. Vertauschen zweier (kompletter) Zeilen
2. Multiplizieren einer Zeile mit einer von Null verschiedenen Zahl
3. Addieren einer Zeile oder des Vielfachen einer Zeile zu einer anderen Zeile

Die Lösungsmenge eines quadratischen linearen Gleichungssystems verändert sich sogar nicht, wenn das Gleichungssystem mit einer regulären Matrix multipliziert wird.

Formen von Gleichungssystemen

Lineare Gleichungssysteme können in Formen vorliegen, in denen sie leicht gelöst werden können. Vielfach werden beliebige Gleichungssysteme mittels eines Algorithmus in eine entsprechende Gestalt gebracht, um anschließend eine Lösung zu finden.

Stufenform, Treppenform

In der Stufenform (auch Zeilenstufenform, Stufengestalt, Staffelgestalt oder Treppenform) verringert sich in jeder Zeile die Zahl der Unbekannten um mindestens eine, die dann auch in den darauffolgenden Zeilen nicht mehr vorkommt. Man kann ein beliebiges Gleichungssystem durch Anwendung des gaußschen Eliminationsverfahrens in diese Form bringen.

Beispiel (die Koeffizienten von ausgelassenen Elementen sind $0$):

${\begin{matrix}6x_{1}&+&3x_{2}&+&4x_{3}&=&1\\&&&-&5x_{3}&=&10\end{matrix}}$

Lineare Gleichungssysteme in Stufenform können durch Rückwärtseinsetzen (Rücksubstitution) gelöst werden. Beginnend mit der letzten Zeile berechnet man dabei die Unbekannte und setzt das gewonnene Ergebnis jeweils in die darüberliegende Zeile ein um die nächste Unbekannte zu berechnen.

Lösung des obigen Beispiels:

1. Auflösen der zweiten Zeile nach $x_{3}$:

   $x_{3}={\frac {10}{-5}}=-2$

2. Einsetzen von $x_{3}$ in die erste Zeile:

   $6x_{1}+3x_{2}+4\cdot (-2)=1$

3. Auflösen der ersten Zeile nach $x_{2}$:

   $x_{2}=-2x_{1}+3$

4. Damit sind alle Vektoren der Form ${\begin{pmatrix}t\\-2t+3\\-2\end{pmatrix}}$ Lösungen des Gleichungssystems.

Dreiecksform

Die Dreiecksform ist ein Sonderfall der Stufenform, bei der jede Zeile genau eine Unbekannte weniger als die vorhergehende hat. Das bedeutet, dass alle Koeffizienten $a_{ii}$ der Hauptdiagonale von $0$ verschieden sind. Die Dreiecksform entsteht bei Anwendung des gaußschen Eliminationsverfahrens, wenn das Gleichungssystem genau eine Lösung hat.

Beispiel (die Koeffizienten von ausgelassenen Elementen sind $0$):

${\begin{matrix}6x_{1}&+&3x_{2}&+&4x_{3}&=&1\\&&8x_{2}&+&5x_{3}&=&-1\\&&&-&2x_{3}&=&6\end{matrix}}$

Wie lineare Gleichungssysteme in Stufenform können auch solche in Dreiecksform durch Rückwärtseinsetzen gelöst werden.

Reduzierte Stufenform

Auch die reduzierte Stufenform ist ein Sonderfall der Stufenform. Bei ihr treten die jeweils ersten Unbekannten jeder Zeile nur ein einziges Mal auf und haben den Koeffizienten $1$. Die reduzierte Stufenform eines linearen Gleichungssystems ist eindeutig: es gibt also für jedes lineare Gleichungssystem genau eine reduzierte Stufenform. Man kann ein beliebiges lineares Gleichungssystem durch Anwendung des Gauß-Jordan-Algorithmus in diese Form bringen.

Beispiel (die Koeffizienten von ausgelassenen Elementen sind $0$):

${\begin{matrix}x_{1}&&&&&+&4x_{4}&=&-1\\&&x_{2}&&&-&5x_{4}&=&-9\\&&&&x_{3}&-&7x_{4}&=&10\end{matrix}}$

Die Lösung des linearen Gleichungssystems kann direkt abgelesen werden. Im Fall des obigen Beispiels sind alle Vektoren der Form ${\begin{pmatrix}-4t-1\\5t-9\\7t+10\\t\end{pmatrix}}$ Lösungen.

Diagonalform

Die Diagonalform ist zugleich ein Sonderfall der reduzierten Stufenform und der Dreiecksform. Bei ihr tritt in jeder Zeile jeweils nur eine Unbekannte mit dem Koeffizienten $1$ auf. Die Diagonalform entsteht bei Anwendung des Gauß-Jordan-Algorithmus, wenn das Gleichungssystem genau eine Lösung hat.

Beispiel (die Koeffizienten von ausgelassenen Elementen sind $0$):

${\begin{matrix}x_{1}&&&&&=&3\\&&x_{2}&&&=&-5\\&&&&x_{3}&=&2\end{matrix}}$

Auch bei dieser Form kann die Lösung direkt abgelesen werden.

Lösungsverfahren haha

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.

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 weitere Bedingung wird dann fast immer gestellt, dass die 2-Norm (die Addition der einzelnen Komponentenquadrate) des Residuenvektors minimal wird. Das liefert die Methode der kleinsten Quadrate.

Siehe auch

• Toeplitz-Matrix
• Liste numerischer Verfahren
• Lineare Rekurrenz

Weblinks

• Applet zum Lösen linearer Gleichungssysteme
• 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?