Lineares Gleichungssystem

Lineare Gleichungssysteme gehören zum Gebiet der linearen Algebra. Sie bestehen aus mehreren linearen Gleichungen, die mehrere unbekannte Größen (Variablen, Unbekannte) enthalten.

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

Inhaltsverzeichnis

1 Definition

2 Beispiel

2.1 Aufgabe
2.2 Lösung

7 Formen von Gleichungssystemen

7.1 erlaubte Umformungen

8 Lösungsverfahren

9 Siehe auch

Definition

Ein lineares Gleichungssystem ist die Zusammenfassung einer Anzahl von linearen Gleichungen. Eine Gleichung ist linear, wenn sie in eine Form gebracht werden kann, in der die Unbekannten ausschließlich linear kombiniert sind. Eine lineare Gleichung mit $n$ Unbekannten muss also - gegebenenfalls nach Umstellen - so aussehen:

$a_1 x_1 + a_2 x_2 +\;\cdots \; + a_n x_n \; =\; b$

Hierbei sind die $x_i\,$ die Unbekannten und die $a_i\,$ konstante Zahlen, die Koeffizienten der Gleichung. Auch $b\,$ ist eine Konstante. Die Konstanten sind meist reelle oder komplexe Zahlen. Hier ein Beispiel für eine lineare Gleichung mit vier Unbekannten:

$3{,}22\,x_1 + 2\, x_2 + x_3 - 5{,}2\, x_4 \; =\; 7{,}28$

Gegeben seien nun die Elemente $a_{ij}\,$ und $b_i\,$ für $1\leq i\leq m$ und $1 \leq j \leq n$ mit den Unbekannten $x_1\,$ bis $x_n\,$ . Ein lineares Gleichungssystem mit $m$ Gleichungen und $n$ Unbekannten kann dann immer in die folgende Form gebracht werden:

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

Sind alle $b_i\,$ gleich 0, heißt das Gleichungssystem homogen, sonst inhomogen.

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, können natürlich nicht alle Lösungen genau bestimmt werden - 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 unbhä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 veringern wird auf verschiedene Arten gemessen und es existieren mehr Meßergebnisse 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 den 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, daß der Residuenvektor minimal wird. Was unter minimal zu verstehen ist, kann durchaus von der Aufgabe abhängen. In der Regel wird gefordert, daß die Gaußsche Norm des Residuenvektors (die Addition der einzelnen Komponentenquadrate des Residuenvektors) zum Minimum wird. Das entspricht dem Gesetz der zufälligen Meßabweichungen.

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.