08 - Lineare Gleichungssysteme

Sei $\textbf{A}$ eine $(m \times n)$-Matrix und $\textbf{b}\in\mathbb{R}^m$. Gesucht werde ein Vektor $\textbf{x}\in\mathbb{R}^n$, sodass $$\textbf{Ax}=\textbf{b}.$$ Dies wird als Lineares Gleichungssystem (LGS) mit $m$ Gleichungen und $n$ Unbekannten bezeichnet. Hierbei sind:

$$ \textbf{A} = \left( \begin{array}{ccc} a_{11} & \cdots & a_{1n} \\ \vdots & & \vdots \\ a_{m1} & \cdots & a_{mn} \end{array} \right), \qquad \textbf{x} = \left( \begin{array}{c} x_1 \\ \vdots \\ x_n \end{array} \right), \qquad \textbf{b} = \left( \begin{array}{c} b_1 \\ \vdots \\ b_m \end{array} \right) $$

Das LGS lautet in ausführlicher Form:

$$ \begin{array}{c} a_{11} x_1 + \cdots + a_{1n} x_n = b_1 \\ \vdots \\ a_{m1} x_1 + \cdots + a_{mn} = b_m \end{array} $$

Das LGS ist genau lösbar, wenn die rechte Seite $ \textbf{b} $ durch die Spalten der Koeffizientenmatrix $ \textbf{A} $ kombiniert werden kann. Die Koeffizienten der Linearkombinationen sind dann eine Lösung. D.h.: Das LGS ist genau dann lösbar, wenn die rechte Seite im Spaltenraum von $ \textbf{A} $ liegt.
Das LGS $\textbf{Ax}=\textbf{b}$ besitzt genau dann eine Lösung, wenn $\text{rg}(\textbf{A})=\text{rg}(\textbf{A|b})$.
Ist $\textbf{A}$ eine $(n \times n)$-Matrix, dann hat das LGS $\textbf{Ax}=\textbf{b}$ genau dann eine Lösung, wenn $\text{det}(\textbf{A})\neq0$.
Ist $ \textbf{A} $ eine reguläre (d.h. invertierbare) Matrix und ist die inverse Matrix $ \textbf{A}^{-1} $ bekannt, so ist der eindeutig Lösungsvektor durch $$ \textbf{x} = \textbf{A}^{-1} \textbf{b} $$ gegeben.

Gauß-Verfahren

Bringe die erweiterte Koeffizientenmatrix $(\textbf{A|b})$ durch (ggf. mehrmaliges)

Vertauschen von Zeilen,
Addition eines Vielfachen einer Zeile mit einer anderen Zeile,
Multiplikation einer Zeile mit einer Zahl $c\neq0$

in die Gestalt $$\left(\begin{array}\textbf{T} & \textbf{d} \\ \textbf{0} & \textbf{e}\end{array}\right),$$ wobei $\textbf{T}\in\mathbb{R}^{k \times n}$ in Treppenform ist. Wenn $\textbf{e}$ nicht der Nullvektor ist, dann besitzt das LGS keine Lösung. Der Rang der Matrix ist $k$.

$\textbf{T}$ habe in den Spalten mit Indizes $s_1,\ldots,s_k$ Stufen, dann können diese Gleichungen nach den Variablen $x_{s_1},\ldots,x_{s_k}$ aufgelöst werden.

Die übrigen Variablen $x_j$ mit $j\notin\{s_1,\ldots,s_k\}$ sind freie Parameter. Löse die $k$-te Zeile des obigen Schemas nach $x_{s_k}$ auf: $$x_{s_k}=\frac{d_k}{t_{k,s_k}} - \frac{t_{k,s_{k+1}}}{t_{k,s_k}}x_{s_{k+1}} - \cdots - \frac{d_k}{t_{k,s_k}}x_n.$$ Dann ist $x_{s_k}$ eine Funktion der freien Variablen $x_{s_{k+1}},\ldots,x_n$, die beliebig gewählt werden können. Löse dann schrittweise nach den Variablen $x_{s_k},\ldots,x_{s_1}$ auf.

Gauß-Verfahren für mehrere rechte Seiten

Sind mehrere lineare Gleichungssysteme zu lösen, bei denen sich jeweils nur die rechte Seite unterscheidet, die Koeffizientenmatrix jedoch stets dieselbe ist, so geht man folgendermaßen vor:

Ergänze $ \textbf{A} $ um die rechten Seiten $ \textbf{b}_1, \dots, \textbf{b}_r $.
Führe das Gauß-Verfahren wie gewohnt durch, bis Treppengestalt erreicht ist bzw. links die Einheitsmatrix erscheint.
Berechne die $ r $ Lösungen durch Rückwärtseinsetzen bzw. lese die Lösung nun ab.

$$ ( \textbf{A} | \textbf{b}_1 \dots \textbf{b}_r ) \to ( \textbf{I} | \textbf{x}_1 \cdots \textbf{x}_r ) $$

Berechnung der inversen Matrix

Die inverse Matrix einer regulären $ n \times n $-Matrix $ \textbf{A} $ kann mit dem Gauß-Verfahren so berechnet werden:

Ergänze $ \textbf{A} $ um die Einheitsmatrix $ \textbf{I} $, also die rechten Seiten $ \textbf{e}_1, \dots, \textbf{e}_n $.
Führe das Gauß-Verfahren durch, bis links die Einheitsmatrix erscheint.
Rechts steht nun die inverse Matrix $ \textbf{A}^{-1} $.

$$ ( \textbf{A} | \textbf{e}_1 \dots \textbf{e}_n ) = ( \textbf{A} | \textbf{I} ) \to ( \textbf{I} | \textbf{A}^{-1} ) $$

Cramersche Regel

Wenn $\textbf{A}$ invertierbar ist, dann ist die $i$-te Koordinate der eindeutigen Lösung $\textbf{x}$ des LGS $\textbf{Ax}=\textbf{b}$ gegeben durch $$x_i=\frac{\text{det}(\textbf{a}^{(1)},\ldots,\textbf{a}^{(i-1)},\textbf{b},\textbf{a}^{(i+1)},\ldots,\textbf{a}^{(n)})}{\text{det}({\textbf{A}})}.$$ Hierbei bezeichnet $$(\textbf{a}^{(1)},\ldots,\textbf{a}^{(i-1)},\textbf{b},\textbf{a}^{(i+1)},\ldots,\textbf{a}^{(n)})$$ diejenige Matrix, die man durch Ersetzen der $i$-ten Spalte von $A$ durch die Spalte $b$ erhält.