Wissen: Gauß-Jordan-Algorithmus

Autor: André Dalwigk

1. Einführung Gauß-Jordan-Algorithmus

In diesem Artikel werden wir die Lösungsmenge eines linearen Gleichungssystems mit Hilfe des Gauß-Jordan-Algorithmus Schritt-für-Schritt konstruieren. Der Gauß-Jordan-Algorithmus gehört zum Bereich der linearen Algebra und stellt eine Erweiterung des gaußschen Eliminationsverfahrens dar. Zudem findet der Gauß-Jordan-Algorithmus Anwendung beim Berechnen der Inversen einer Matrix.

2. Notationen

Die folgende Tabelle listet die im Beispiel verwendeten Operationen und ihre Notation auf:

\(\begin{array}{|l|l|} \hline \text{Notation} &\text{Bedeutung} \\\hline D_i(k) & \text{Multiplizieren Sie Zeile } i \text{ mit } k \\\hline T_{i,j}(k) & \text{Addieren Sie das
}k-\text{Fache der }j-\text{ten Zeile zur }i-\text{ten Zeile} \\\hline P_{i,j} &\text{Tauschen Sie die }i-\text{te und }j-\text{te Zeile} \\\hline \end{array}\)

3. Das Problem: LGS in Matrixnotation

Gegeben sei ein lineares Gleichungssystem in Matrixnotation \(Ax=b\) mit \(A\in\mathbb{R}^{4\times 7}\), \(x\in\mathbb{R}^7\) und \(b\in\mathbb{R}^4\) durch $$\underbrace{ \left( \begin{matrix} 1 & 1 & 2 & 1 & -1 & 0 & 1\\ 0 & -2 & -2 & -2 & -2 & 2 & 0\\ 0 & -1 & -1 & -1 & -1 & 1 & 0\\ -1 & 0 & -4 & 1 &-4 & 1 & 1\\ \end{matrix} \right) }_{A} \cdot \underbrace{ \left( \begin{matrix} x_1\\ x_2\\ x_3\\ x_4\\ x_5\\ x_6\\ x_7\\ \end{matrix} \right) }_{x} = \underbrace{ \left( \begin{matrix} 2\\ 4\\ 2\\ 0\\ \end{matrix} \right) }_{b} $$ Gesucht ist der Lösungsraum (die Lösungsmenge) dieses linearen Gleichungssystems.

4. Ausführliche Lösung des LGS

Der Lösungsraum \(\mathbb{L}\) setzt sich aus der partikulären Lösung \(x_p\in\mathbb{L}_p\) und den Vektoren im Nullraum \(x_{h,1},x_{h,2},...,x_{h,k}\in N(A)\) mit \(|N(A)|=k\in\mathbb{N}_0\) wie folgt zusammen: $$\mathbb{L}=\left\{x_p + c_1\cdot x_{h,1}+c_2\cdot x_{h,2}+...+c_k\cdot x_{h,k}\mid c_1,c_2,...,c_k\in\mathbb{R}\right\}$$ Wir verwenden bei der Berechnung den Gauß-Algorithmus und bilden hierzu die erweitere Koeffizientenmatrix \((A\mid b)\): $$\underbrace{ \left( \begin{matrix} 1 & 1 & 2 & 1 & -1 & 0 & 1 & \mid & 2\\ 0 & -2 & -2 & -2 & -2 & 2 & 0 & \mid & 4\\ 0 & -1 & -1 & -1 & -1 & 1 & 0 & \mid & 2\\ -1 & 0 & -4 & 1 & -4 & 1 & 1 & \mid & 0\\ \end{matrix} \right) }_{(A\mid b)} $$ Diese formen wir mit den Operationen \(D_i(k)\), \(T_{i,j}(k)\) und \(P_{i,j}\) so lange um, bis \(A\) in Treppennormalform ist:

\(\begin{array}{|l|l|} \hline \text{Matrix} & \text{Umformungsoperationen} \\\hline \left( \begin{matrix} 1 & 1 & 2 & 1 & -1 & 0 & 1 & \mid & 2\\ 0 & -2 & -2
& -2 & -2 & 2 & 0 & \mid & 4\\ 0 & -1 & -1 & -1 & -1 & 1 & 0 & \mid & 2\\ -1 & 0 & -4 & 1 & -4 & 1 & 1 & \mid &
0\\ \end{matrix} \right) & T_{4,1}(1) \\\hline \left( \begin{matrix} 1 & 1 & 2 & 1 & -1 & 0 & 1 & \mid & 2\\ 0 & -2 & -2 & -2 & -2 & 2 & 0
& \mid & 4\\ 0 & -1 & -1 & -1 & -1 & 1 & 0 & \mid & 2\\ 0 & 1 & -2 & 2 & -5 & 1 & 2 & \mid & 2\\ \end{matrix} \right) &
D_{2}(-0.5)\\\hline \left( \begin{matrix} 1 & 1 & 2 & 1 & -1 & 0 & 1 & \mid & 2\\ 0 & 1 & 1 & 1 & 1 & -1 & 0 & \mid & -2\\ 0 & -1
& -1 & -1 & -1 & 1 & 0 & \mid & 2\\ 0 & 1 & -2 & 2 & -5 & 1 & 2 & \mid & 2\\ \end{matrix} \right) &
T_{1,2}(-1),T_{3,2}(1),T_{4,2}(-1)\\\hline \left( \begin{matrix} 1 & 0 & 1 & 0 & -2 & 1 & 1 & \mid & 4\\ 0 & 1 & 1 & 1 & 1 & -1 & 0 & \mid
& -2\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \mid & 0\\ 0 & 0 & -3 & 1 & -6 & 2 & 2 & \mid & 4\\ \end{matrix} \right) &
D_{4}\left(\frac{1}{3}\right)\\\hline \left( \begin{matrix} 1 & 0 & 1 & 0 & -2 & 1 & 1 & \mid & 4\\ 0 & 1 & 1 & 1 & 1 & -1 & 0 & \mid &
-2\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \mid & 0\\ 0 & 0 & 1 & -\frac{1}{3} & 2 & -\frac{2}{3} & -\frac{2}{3} & \mid & -\frac{4}{3}\\
\end{matrix} \right) & T_{2,4}(-1),T_{1,4}(-1)\\\hline \left( \begin{matrix} 1 & 0 & 0 & \frac{1}{3} & -4 & \frac{5}{3} & \frac{5}{3} & \mid & \frac{16}{3}\\ 0
& 1 & 0 & \frac{4}{3} & -1 & -\frac{1}{3} & \frac{2}{3} & \mid & -\frac{2}{3}\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \mid & 0\\ 0 & 0 &
1 & -\frac{1}{3} & 2 & -\frac{2}{3} & -\frac{2}{3} & \mid & -\frac{4}{3}\\ \end{matrix} \right) & \\\hline \end{array}\)

Das Gleichungssystem ist offensichtlich unterbestimmt (mehr Variablen als Gleichungen). Um den Lösungsraum des homogenen Gleichungssystems \(Ax=0\) zu bestimmen, ergänzen wir zunächst so viele Nullzeilen, bis die \((4\times 7)-\)Matrix quadratisch ist. Dafür benötigen wir \(7-4=3\) Nullzeilen:

$$ \left( \begin{matrix} 1 & 0 & 0 & \frac{1}{3} & -4 & \frac{5}{3} & \frac{5}{3} & \mid & \frac{16}{3}\\ 0 & 1 & 0 & \frac{4}{3} & -1 &-\frac{1}{3} & \frac{2}{3} & \mid & -\frac{2}{3}\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \mid & 0\\ 0 & 0 & 1 & -\frac{1}{3} & 2 & -\frac{2}{3}& -\frac{2}{3} & \mid & -\frac{4}{3}\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \mid & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \mid & 0\\ 0& 0 & 0 & 0 & 0 & 0 & 0 & \mid & 0\\ \end{matrix} \right) $$ Wir wenden nun so lange die Zeilentausch-Operation \(P_{i,j}\) an, bis sich auf der Hauptdiagonalen die maximale Anzahl an Einsen befindet. Dazu genügt bereits \(P_{34}\): $$ \left( \begin{matrix} 1 & 0 & 0 & \frac{1}{3} & -4 & \frac{5}{3} & \frac{5}{3} & \mid & \frac{16}{3}\\ 0 & 1 & 0 & \frac{4}{3} & -1 & -\frac{1}{3} & \frac{2}{3} & \mid & -\frac{2}{3}\\ 0 & 0 & 1 & -\frac{1}{3} & 2 & -\frac{2}{3} & -\frac{2}{3} & \mid & -\frac{4}{3}\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \mid & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \mid & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \mid & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \mid & 0\\ \end{matrix} \right) $$ Die partikuläre Lösung \(x_p\in\mathbb{L}_p\) können wir nun rechts des Strichs in der erweiterten Koeffizientenmatrix in Treppennormalform ablesen: $$ x_p = \left( \begin{matrix} \frac{16}{3}\\ -\frac{2}{3}\\ -\frac{4}{3}\\ 0\\ 0\\ 0\\ 0\\ \end{matrix} \right) $$ Wir ergänzen nun auf der Hauptdiagonalen der um die Nullzeilen erweiterten Matrix in Treppennormalform an jeder Stelle \(a_{i,i}=0\) eine \(-1\): $$ \left( \begin{matrix} 1 & 0 & 0 & \frac{1}{3} & -4 & \frac{5}{3} & \frac{5}{3}\\ 0 & 1 & 0 & \frac{4}{3} & -1 & -\frac{1}{3} & \frac{2}{3}\\ 0 & 0 & 1 & -\frac{1}{3} & 2 & -\frac{2}{3} & -\frac{2}{3} \\ 0 & 0 & 0 & -1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & -1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & -1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & -1\\ \end{matrix} \right) $$ Hieraus lesen wir die Basis des Nullraums von \(A\) (also die Vektoren zur Konstruktion von Lösungen des homogenen Gleichungssystems \(Ax=0\)) ab. Die Basisvektoren sind die Spalten, in denen wir die \(-1\) ergänzt haben: $$ \left\{ \left( \begin{matrix} \frac{1}{3}\\ \frac{4}{3}\\ -\frac{1}{3}\\ -1\\ 0\\ 0\\ 0\\ \end{matrix} \right), \left( \begin{matrix} -4\\ -1\\ 2\\ 0\\ -1\\ 0\\ 0\\ \end{matrix} \right), \left( \begin{matrix} \frac{5}{3}\\ -\frac{1}{3}\\ -\frac{2}{3}\\ 0\\ 0\\ -1\\ 0\\ \end{matrix} \right), \left( \begin{matrix} \frac{5}{3}\\ \frac{2}{3}\\ -\frac{2}{3}\\ 0\\ 0\\ 0\\ -1\\ \end{matrix} \right) \right\} \text{bzw.} \left\{ \left( \begin{matrix} -\frac{1}{3}\\ -\frac{4}{3}\\ \frac{1}{3}\\ 1\\ 0\\ 0\\ 0\\ \end{matrix} \right), \left( \begin{matrix} 4\\ 1\\ -2\\ 0\\ 1\\ 0\\ 0\\ \end{matrix} \right), \left( \begin{matrix} -\frac{5}{3}\\ \frac{1}{3}\\ \frac{2}{3}\\ 0\\ 0\\ 1\\ 0\\ \end{matrix} \right), \left( \begin{matrix} -\frac{5}{3}\\ -\frac{2}{3}\\ \frac{2}{3}\\ 0\\ 0\\ 0\\ 1\\ \end{matrix} \right) \right\} $$ Aus diesen Vektoren konstruieren wir nun den Lösungsraum des Ausgangsgleichungssystems wie folgt: $$ \mathbb{L}= \left\{ \underbrace{ \left( \begin{matrix} \frac{16}{3}\\ -\frac{2}{3}\\ -\frac{4}{3}\\ 0\\ 0\\ 0\\ 0\\ \end{matrix} \right) }_{x_p} + \underbrace{ c_1\cdot \left( \begin{matrix} \frac{1}{3}\\ \frac{4}{3}\\ -\frac{1}{3}\\ -1\\ 0\\ 0\\ 0\\ \end{matrix} \right) + c_2\cdot \left( \begin{matrix} -4\\ -1\\ 2\\ 0\\ -1\\ 0\\ 0\\ \end{matrix} \right) + c_3\cdot \left( \begin{matrix} \frac{5}{3}\\ -\frac{1}{3}\\ -\frac{2}{3}\\ 0\\ 0\\ -1\\ 0\\ \end{matrix} \right) +c_4\cdot \left( \begin{matrix} \frac{5}{3}\\ \frac{2}{3}\\ -\frac{2}{3}\\ 0\\ 0\\ 0\\ -1\\ \end{matrix} \right) }_{\text{ Nullraumbasis}} \mid c_1,c_2,c_3,c_4\in\mathbb{R} \right\} $$

  Schreib uns deine Hinweise