23.10.2026 - Woche 6

RREF

Als RREF wird die reduzierte Zeilenstufenform bezeichnet. Die Abkürzung RREF kommt vom Englischen “Reduced Row Echelon Form”.

Eine RREF kann die folgende Form haben:

Alle Kästchen, die in in weiss sind müssen zwingend mit einer $0$ gefüllt sein. Kästchen, welche grau hinterlegt sind können jeden beliebigen Wert annehmen, sofern kein Wert eingetragen ist.

In jeder Spalte $j_1,j_2,\dots ,j_r$ steht ein Standardeinheitsvektor. Die Spalten $j_1,j_2,\dots ,j_r$ sind dabei genau die Spalten, bei welchen der graue Bereich eine “Stufe” nach unten macht.

Beispiele

• Der RREF von $I(m\times n)$ ist: RREF($1,2,\dots ,m$)
• Der RREF von $0(m\times n)$ ist RREF()

Link to original

Gauss-Jordan-Elimination

Bei der Gauss-Jordan-Elimination wird wie schon bei der Gauss-Elimination das Gleichungssystem $Ax=b$ in ein anderes schöneres System umgewandelt, welches dann einfach zu lösen ist. Die folgende Umwandlung wird bei der Gauss-Jordan-Elimination durchgeführt:
$Ax=b\to Rx=c$ wobei $R$ in Reduzierter Zeilenstufenform (RREF) geschrieben wird.

Direkte Lösung

Die direkte Lösung von $Rx=c$ ,$R$ in RREF($j_1,j_2,\dots j_r$)
Die Resultate können direkt aus der Matrix $R$ In Zeilenstufenform abgelesen werden. So ist die Lösung einfach das Skalar, mit welchem der Standardeinheitsvektor an der benötigten Spalte multipliziert werden muss, damit man auf den Wert von $c$ gelangt. Alle anderen Einträge von $x$ sind $0$.

Bsp.
Bei $j_1$ muss der Standardeinheitsvektor mit $c_1$ multipliziert werden, damit man auf den gewünschten Wert in $c$ kommt.

Elimination

Wenn $A$ noch nicht in RREF ist, muss die folgende Transformation stattfinden:
$Ax=b\to Rx=c$ Die folgende Illustration zeigt, wie das Durchführen der Gauss-Jordan-Elimination und die Transformation der Matrix $A$ zur Matrix $R$ funktioniert. Alle Schritte müssen auch auf der rechten Seite $b$ durchgeführt werden.

Das Vorgehen ist nun gleich wie bei der Gauss-Elimination (unter dem Element der Diagonalen dürfen in dieser Spalte nur die $0$ stehen). Im Gegensatz zur Gauss-Elimination wird hier aber zuerst das Pivot-Element auf $1$ gebracht.

Bei der Gauss-Elimination würde dieser Fall nun zum Scheitern und Aufgeben führen, da es keine Zeilen mehr gibt, welche für Spalte $2$ $\ne 0$ sind. Bei der Gauss-Jordan-Elimination setzten wird dies aber nicht voraus und akzeptieren auch, dass es eine Spalte gibt, in welcher dort eine $0$ steht.

In Spalte 3 gibt es jetzt einen Eintrag $\ne 0$, er steht aber noch in Zeile 3 und nicht 2 wo er sein müsste. Das ist aber kein Problem, die Zeilen dürfen vertauscht werden. Wie oben gezeigt muss jetzt das Pivot Element auf $1$ gebracht werden, was hier durch Division mit $-2$ erzielt wird.

Bei der Gauss-Elimination musste man sich nur darum kümmern, dass die Einträge unterhalb des Pivot Elements $0$ sind. Hier ist es so, dass alle anderen Elemente in dieser Spalte $0$ sein müssen. Die Zeile $2$ muss also einmal von Zeile $1$ abgezogen werden.

Das wird nun auch noch für Spalte $4$ ausgeführt und es entsteht die folgende Matrix in RREF:

Dies ist nun die aus $A$ gewonnene Matrix $R$, aus welcher wie in Direkte Lösung gezeigt die Lösung der Gleichung $Ax=b$ abgelesen werden kann.

Link to original

Der folgende Algorithmus zeigt auf, wie das ganze programmatisch funktioniert und ausserdem, wie mit der rechten Seite vorgegangen wird:

Gaus-Jordan-Elimination-Algorithmus

Link to original

Die Laufzeit des obigen Algorithmus ($(A,B)\to (R,C)$):

• Es müssen $O(m)$ Zeilenoperationen müssen ausgeführt werden
• Pro Zeilenoperation gibt es $O(m+n)$ Einzelschritte

Die Gesamtlaufzeit beträgt daher: $O(m\cdot r(m+n))$

Im Falle $m=r=n$ läuft das auf $O(m^3)$ hinaus. Somit hat das Gauss-Jordan Verfahren für den Fall, in welchem das Gauss Verfahren angewendet werden kann die gleiche Laufzeit.

$R$ ist die RREF-Standardform von $A$ und gibt uns auch die CR-Zerlegung nach

Theorem 3.18

Sei $A$ eine $m\times n$ Matrix. Es gibt genau eine $m\times n$ Matrix $R$ (die aus Theorem 3.17) mit den folgenden Eigenschaften:

• (i) $R=MA$ mit einer invertierbaren Matrix $M$
• (ii) $R$ ist in RREF

Link to original

.
Genauer: $R$ ist in RREF($j_1,j_2,\dots j_r$), wobei $j_1,j_2,\dots j_r$ die Indizes er unabhängigen Spalten von $A$ sind, und

$$R=\left[\frac{\underset{r\times m}{\underbrace{R^{\prime }}}}{\underset{(m-r)\times m}{\underbrace{\text{0}}}}\right]$$

mit $R^{\prime }$ der eindeutigen Matrix, so dass $A=C{R}^{\prime }$ (Submatrix der unabhängigen Spalten) in Theorem 2.44.

Berechnung der Inversen von $A$ mit Gauss-Jordan($A,I$) $\to (R,M)(R=MA)$ nach Theorem 3.19