de
Seitenbanner
Menu
A-Z
Nachlesen

Gaußsches Eliminationsverfahren

Beim gaußschen Eliminationsverfahren (auch Gauß-Verfahren, Gauß-Algorithmus oder kurz Gauß-Elimination genannt) handelt es sich um einen Algorithmus aus den Bereichen der linearen Algebra und der Numerik, der eine Matrix in Zeilenstufenform überführt. Er wird häufig zum Lösen von linearen Gleichungssystemen und zum Bestimmen des Rang oder der Determinante einer Matrix verwendet. Beim Gauß-Algorithmus handelt es sich um eine Vorstufe des Gauß-Jordan-Algorithmus.

Das Gauß-Verfahren geht auf den deutschen Mathematiker Carl Friedrich Gauß zurück.

Hinweis zur Terminologie: Der Gauß-Algorithmus beschreibt allgemein das Verfahren, wie eine Matrix in Zeilenstufenform überführt wird. Er ist nicht an einen speziellen Kontext gebunden, obgleich er oftmals – wie auch in diesem Artikel – als Lösungsverfahren für lineare Gleichungssysteme eingeführt und definiert wird. Für das Überführen einer beliebigen Matrix in Zeilenstufenform ist ausschließlich die nachfolgend beschriebene Vorwärtselimination relevant.

Beschreibung des Verfahrens

Erweiterte Koeffizientenmatrix

Gegeben sei ein lineares Gleichungssystem $Ax=b$. Hierin repräsentiert die Matrix $A \in \mathcal{K}^{m \times n}$ die Koeffizientenmatrix mit Einträgen aus einem Körper $\mathcal{K}$, der Vektor $x = (x_1, \ldots, x_n) \in \mathcal{K}^n$ steht für die $n$ Unbekannten (bzw. die Variablen) $x_1,\ldots,x_n$ und der Vektor $b = (b_1,\ldots,b_m) \in \mathcal{K}^m$ stellt den Ergebnisvektor dar.

In expliziter Form lautet das Gleichungssystem wie folgt:

\begin{alignedat}{4} a_{11}x_1 &\ + &\ a_{12}x_2 &\ + &\ \ldots &\ + &\ a_{1n}x_n &\ = &\ b_1 \\[0.5em] a_{21}x_1 &\ + &\ a_{22}x_2 &\ + &\ \ldots &\ + &\ a_{2n}x_n &\ = &\ b_2 \\[0.5em] \vdots\quad &\ &\ \vdots\quad &\ &\ \ddots &\ &\ \vdots\quad &\ & \vdots\ \, \\[0.5em] a_{m1}x_1 &\ + &\ a_{m2}x_2 &\ + &\ \ldots &\ + &\ a_{mn}x_n &\ = &\ b_m \end{alignedat}

Zur vereinfachten Darstellung bietet es sich an, anstelle der expliziten Form des linearen Gleichungssystems die erweiterte Koeffizientenmatrix $[A \mid b]$ zu verwenden, die entsteht, wenn die Koeffizientenmatrix $A$ um den Ergebnisvektor $b$ erweitert wird. Jede Zeile repräsentiert dabei eine der ursprünglichen Gleichungen. Jede Spalte der Koeffizientenmatrix repräsentiert eine der Variablen.

\[ \bigl[ A \mid b \bigr] = \left[\begin{array}{cccc|c} a_{11} & a_{12} & \cdots & a_{1n} & b_1 \\[0.5em] a_{21} & a_{22} & \cdots & a_{2n} & b_2 \\[0.5em] \vdots & \vdots & \ddots & \vdots &\, \vdots \\[0.5em] a_{m1} & a_{m2} & \cdots & a_{mn} & b_m \end{array}\right] \]
Darstellung einer erweiterten Koeffizientenmatrix

Vorwärtselimination

Im ersten Schritt wird die erweiterte Koeffizientenmatrix durch Vorwärtselimination zunächst in Zeilenstufenform überführt; dabei werden die Zeilen der erweiterten Koeffizientenmatrix und somit auch die repräsentierten Gleichungen transformiert – nicht jedoch die Lösungsmenge des linearen Gleichungssystems. Die Zeilenstufenform hat die sehr nützliche Eigenschaft, dass in jeder Nichtnullzeile der Matrix mindestens eine Variable weniger auftritt als in der darüberliegenden Zeile, dass also pro Zeile mindestens eine Variable eliminiert wird.

Das Überführen in Zeilenstufenform geschieht mithilfe von elementaren Zeilenumformungen:

  • Vertauschen von zwei Zeilen;
  • Multiplikation einer Zeile mit einer von Null verschiedenen Konstanten;
  • Addition des Vielfachen einer Zeile zu einer anderen Zeile.

Der Algorithmus zum Überführen der Matrix in Zeilenstufenform besteht aus den folgenden Schritten:

  1. Bestimmen der am weitesten links stehenden Spalte, die von Null verschiedene Elemente enthält.
  2. Vertauschen der obersten Zeile mit einer geeigneten, darunterliegenden Zeile, falls der oberste Eintrag der Spalte eine Null ist, um einen von Null verschiedenen obersten Spalteneintrag $a$ zu erhalten. Strategien zur Auswahl der optimalen Zeile werden später unter Pivotisierung beschrieben.
  3. Multiplikation der obersten Zeile mit dem multiplikativen Inversen $a^{-1}$ des ersten Elements $a$, um eine führende Eins zu erhalten, falls das führende Element ungleich Eins ist.
  4. Addition von geeigneten Vielfachen der obersten Zeile zu den darunterliegenden Zeilen, um alle unter der führenden Eins stehenden Elemente zu Null zu machen.
  5. Streichen der Zeile und Spalte des aktuellen führenden Elements und Wiederholen der Schritte 1-4 für die resultierende Matrix, bis die Matrix in Zeilenstufenform vorliegt.

Wird die Matrix mit dem optionalen nachfolgenden Schritt zusätzlich in reduzierte Zeilenstufenform überführt, so handelt es sich um das Gauß-Jordan-Verfahren.

  1. Beginnend mit der untersten Zeile: Addition von geeigneten Vielfachen der unteren Zeilen zu den darüberliegenden Zeilen, um oberhalb der führenden Einsen ebenfalls Nullen zu erhalten.

Die erhaltene Matrix $[A^\star \mid b^\star]$ liegt nun in Zeilenstufenform vor. Für den Fall einer quadratischen Koeffizientenmatrix mit vollem Rang sieht dies exemplarisch wie folgt aus:

\[ \bigl[ A^\star \mid b^\star \bigr] = \left[\begin{array}{cccc|c} 1_\mathcal{K} & a_{12}^\star & \cdots & a_{1n}^\star & b_1^\star \\[0.5em] 0_\mathcal{K} & 1_\mathcal{K} & \cdots & a_{2n}^\star & b_2^\star \\[0.5em] \vdots & \vdots & \ddots & \vdots & \vdots \\[0.5em] 0_\mathcal{K} & 0_\mathcal{K}& \cdots & 1_\mathcal{K} & b_m^\star \end{array}\right] \]
Darstellung einer erweiterten Koeffizientenmatrix in Zeilenstufenform

Zur Erinnerung: Die (transformierte) erweiterte Koeffizientenmatrix in Zeilenstufenform repräsentiert das (transformierte) lineare Gleichungssystem in Stufenform.

\begin{alignedat}{4} x_1 &\ + &\ a_{12}^\star x_2 &\ + &\ \ldots &\ + &\ a_{1n}^\star x_n &\ = &\ b_1^\star \\[0.5em] &\ &\ x_2 &\ + &\ \ldots &\ + &\ a_{2n}^\star x_n &\ = &\ b_2^\star \\[0.5em] &\ &\ &\ &\ \ddots &\ &\ \vdots\quad &\ &\ \vdots\ \ \\[0.5em] &\ &\ &\ &\ &\ &\ x_n &\ = &\ b_m^\star \end{alignedat}

Hinweis: An der Zeilenstufenform kann nun geprüft werden, ob das lineare Gleichungssystem lösbar oder unlösbar ist. Besitzt die erweiterte Koeffizientenmatrix in Zeilenstufenform eine Zeile der Form

\[ \left[\begin{array}{cccc|c} 0_\mathcal{K} & 0_\mathcal{K} & \cdots & 0_\mathcal{K} & b^\star \end{array}\right] \]

für ein $b^\star \neq 0_\mathcal{K}$, so ist das Gleichungssystem unlösbar, da diese Zeile der folgenden, unlösbaren bzw. widersprüchlichen Gleichung entspricht:

\[ \underbrace{0_\mathcal{K} \cdot x_1 + 0_\mathcal{K} \cdot x_2 + \ldots + 0_\mathcal{K} \cdot x_n}_{{} = 0_\mathcal{K}} \overset{\unicode{x21af}}{=} b^\star. \]

Rückwärtseinsetzen

Im zweiten Schritt, dem Rückwärtseinsetzen bzw. der Rückwärtssubstitution, können die Variablen ausgehend von der letzten Zeile der Matrix, die nicht nur Nullen beinhaltet (bzw. ausgehend von der letzten Gleichung), schrittweise berechnet werden. Hierbei treten zwei typische Fälle auf:

  • Fall 1: eindeutige Lösung
    Falls das lineare Gleichungssystem eindeutig lösbar ist, besitzt die umgeformte Koeffizientenmatrix genauso viele Nichtnullzeilen wie Variablen und auf ihrer Hauptdiagonalen stehen nur Einsen. Alle Einträge unterhalb der Hauptdiagonalen sind Null, die Einträge darüber können beliebig sein. Der Wert der einzigen Variable der untersten Gleichung kann unmittelbar abgelesen/ausgerechnet werden; gefundene Lösungen können anschließend in die darüberliegenden Gleichungen eingesetzt werden, so dass diese dann ebenfalls schrittweise nach der jeweils einzigen verbleibenden Variable umgestellt und aufgelöst werden können.
  • Fall 2: unendlich viele Lösungen
    Abhängig von dem zu lösenden linearen Gleichungssystem kann es vorkommen, dass die Matrix $[A^\star \mid b^\star]$ in Zeilenstufenform weniger Nichtnullzeilen als Variablen besitzt. Dies ist beispielsweise dann der Fall, wenn beim Überführen in Zeilenstufenform Nullzeilen entstehen, oder falls das anfängliche Gleichungssystem bereits mehr Variablen als Gleichungen besitzt. In diesem Fall werden die Variablen in führende und freie Variablen unterschieden, abhängig davon, ob in den zu den Variablen gehörenden Spalten der erweiterten Koeffizientenmatrix in Zeilenstufenform eine führende Eins enthalten ist, oder nicht. Jeder freien Variable wird ein Parameter aus dem zugrundeliegenden Körper $\mathcal{K}$ zugewiesen; im Anschluss können die führenden Variablen durch Rückwärtseinsetzen in Abhängigkeit von diesen Parametern bestimmt werden. Das Gleichungssystem besitzt in diesem Fall unendlich viele Lösungen.

Hinweis: Falls das Gleichungssystem überbestimmt ist, falls es also mehr Gleichungen als Variablen besitzt, so gelten die obigen Aussagen in analoger Form, da alle überschüssigen Gleichungen in der erweiterten Koeffizientenmatrix zu Nullzeilen werden, sofern beim Überführen in Zeilenstufenform kein Widerspruch entsteht, der zur Unlösbarkeit des Gleichungssystems führt – wie bereits zuvor beschrieben.

Beispiele

Beispiel 1

In diesem Beispiel wird das nachfolgende, eindeutig lösbare, lineare Gleichungssystem mit drei Gleichungen und drei Variablen betrachtet.

\begin{alignedat}{4} x_1 &\ - &\ x_2 &\ - &\ 2x_3 &\ = &\ 1 \\[0.5em] -x_1 &\ + &\ 2x_2 &\ + &\ 4x_3 &\ = &\ 1 \\[0.5em] -3x_1 &\ + &\ 4x_2 &\ + &\ 11x_3 &\ = &\ 8 \end{alignedat}

Zunächst wird die erweiterte Koeffizientenmatrix aufgestellt.

\[ \left[ \begin{array}{rrr|r} 1 & -1 & -2 & 1 \\[0.25em] -1 & 2 & 4 & 1 \\[0.25em] -3 & 4 & 11 & 8 \end{array} \right] \]

Diese wird anschließend in Zeilenstufenform überführt. Die jeweils durchzuführenden elementaren Zeilenumformungen stehen rechts neben den betroffenen Zeilen der Matrix.

\[ \begin{array}{rrr|r|l} 1 & -1 & -2 & 1 & \\[0.25em] -1 & 2 & 4 & 1 & \text{II} + \text{I} \\[0.25em] -3 & 4 & 11 & 8 & \text{III} + 3 \cdot \text{I} \\[0.25em] \hline 1 & -1 & -2 & 1 & \\[0.25em] 0 & 1 & 2 & 2 & \\[0.25em] 0 & 1 & 5 & 11 & \text{III} - \text{II} \\[0.25em] \hline 1 & -1 & -2 & 1 & \\[0.25em] 0 & 1 & 2 & 2 & \\[0.25em] 0 & 0 & 3 & 9 & \text{III} \cdot \frac{1}{3} \\[0.25em] \hline 1 & -1 & -2 & 1 & \\[0.25em] 0 & 1 & 2 & 2 & \\[0.25em] 0 & 0 & 1 & 3 & \end{array} \]

Das resultierende, transformierte Gleichungssystem kann an der untersten Matrix direkt abgelesen werden.

\begin{alignedat}{4} x_1 &\ - &\ x_2 &\ - &\ 2x_3 &\ = &\ 1 \\[0.5em] &\ &\ x_2 &\ + &\ 2x_3 &\ = &\ 2 \\[0.5em] &\ &\ &\ &\ x_3 &\ = &\ 3 \end{alignedat}

Der Wert der Variable $x_3$ folgt unmittelbar aus der dritten Gleichung.

\[ x_3=3 \]

Anschließend kann die zweite Gleichung nach $x_2$ umgestellt und mit dem zuvor bestimmten Wert $x_3=3$ aufgelöst werden.

\begin{align*} x_2 &= 2 - 2x_3 \\[0.5em] &= 2 - 2 \cdot 3 \\[0.5em] &= -4 \end{align*}

Im letzten Schritt kann nun die erste Gleichung nach $x_1$ umgestellt und mit den bekannten Werten $x_2=-4$ sowie $x_3=3$ aufgelöst werden.

\begin{align*} x_1 &= 1 + x_2 + 2x_3 \\[0.5em] &= 1 + \left(-4\right) + 2 \cdot 3 \\[0.5em] &= 3 \end{align*}

Als Gesamtlösung des linearen Gleichungssystems ergibt sich somit

\[ x = \left[\begin{array}{r} x_1 \\[0.25em] x_2 \\[0.25em] x_3 \end{array}\right] = \left[\begin{array}{r} 3 \\[0.25em] -4 \\[0.25em] 3 \end{array}\right]. \]

Beispiel 2

In diesem Beispiel wird ein lineares Gleichungssystem mit drei Gleichungen und vier Variablen betrachtet, das unendlich viele Lösungen besitzt.

\begin{alignedat}{5} x_1 &\ - &\ 3x_2 &\ - &\ x_3 &\ + &\ 3x_4 &\ = &\ 0 \\[0.5em] 2x_1 &\ - &\ 6x_2 &\ - &\ x_3 &\ + &\ 7x_4 &\ = &\ 3 \\[0.5em] -3x_1 &\ + &\ 9x_2 &\ + &\ 5x_3 &\ - &\ 7x_4 &\ = &\ 6 \end{alignedat}

Zunächst wird die erweiterte Koeffizientenmatrix aufgestellt.

\[ \left[ \begin{array}{rrrr|r} 1 & -3 & -1 & 3 & 0 \\[0.25em] 2 & -6 & -1 & 7 & 3 \\[0.25em] -3 & 9 & 5 & -7 & 6 \end{array} \right] \]

Diese wird anschließend in Zeilenstufenform überführt. Die jeweils durchzuführenden elementaren Zeilenumformungen stehen rechts neben den betroffenen Zeilen der Matrix.

\[ \begin{array}{rrrr|r|l} 1 & -3 & -1 & 3 & 0 & \\[0.25em] 2 & -6 & -1 & 7 & 3 & \text{II} - 2 \cdot \text{I} \\[0.25em] -3 & 9 & 5 & -7 & 6 & \text{III} + 3 \cdot \text{I} \\[0.25em] \hline 1 & -3 & -1 & 3 & 0 & \\[0.25em] 0 & 0 & 1 & 1 & 3 & \\[0.25em] 0 & 0 & 2 & 2 & 6 & \text{III} - 2 \cdot \text{II} \\[0.25em] \hline 1 & -3 & -1 & 3 & 0 & \\[0.25em] 0 & 0 & 1 & 1 & 3 & \\[0.25em] 0 & 0 & 0 & 0 & 0 & \end{array} \]

Das resultierende, transformierte Gleichungssystem kann an der untersten Matrix direkt abgelesen werden.

\begin{alignedat}{5} x_1 &\ - &\ 3x_2 &\ - &\ x_3 &\ + &\ 3x_4 &\ = &\ 0 \\[0.5em] &\ &\ &\ &\ x_3 &\ + &\ x_4 &\ = &\ 3 \end{alignedat}

Bei $x_1$ und $x_3$ handelt es sich um die führenden Variablen, da in ihren Spalten eine führende Eins vorhanden ist; bei $x_2$ und $x_4$ handelt es sich folglich um die freien Variablen.

Zunächst werden Parameter $s,t \in \R$ für die freien Variablen gewählt und es gelte $x_2 = s$ und $x_4 = t$. Anschließend kann die zweite Gleichung nach $x_3$ umgestellt und in Abhängigkeit von dem zuvor festgelegten Parameter $x_4=t$ aufgelöst werden.

\begin{align*} x_3 &= 3 - x_4 \\[0.5em] &= 3 - t \\[0.5em] \end{align*}

Im letzten Schritt kann nun die erste Gleichung nach $x_1$ umgestellt und mit den bekannten Werten für $x_2$, $x_3$ und $x_4$ in Abhängigkeit von den Parametern $s$ und $t$ aufgelöst werden.

\begin{align*} x_1 &= 0 + 3x_2 + x_3 - 3x_4 \\[0.5em] &= 0 + 3s + \left( 3-t \right) - 3t \\[0.5em] &= 3 + 3s - 4t \end{align*}

Die Gesamtlösung des linearen Gleichungssystems kann in Parameterform wie folgt dargestellt werden:

\[ x = \left[\begin{array}{r} x_1 \\[0.25em] x_2 \\[0.25em] x_3 \\[0.25em] x_4 \end{array}\right] = \left[\begin{array}{c} 3+3s-4t \\[0.25em] s \\[0.25em] 3-t \\[0.25em] t \end{array}\right] = \left[\begin{array}{r} 3 \\[0.25em] 0 \\[0.25em] 3 \\[0.25em] 0 \end{array}\right] + s \cdot \left[\begin{array}{r} 3 \\[0.25em] 1 \\[0.25em] 0 \\[0.25em] 0 \end{array}\right] + t \cdot \left[\begin{array}{r} -4 \\[0.25em] 0 \\[0.25em] -1 \\[0.25em] 1 \end{array}\right]. \]

Pivotisierung

Das gaußsche Eliminationsverfahren ist im Allgemeinen nicht ohne das Vertauschen von Zeilen möglich. Ist das oberste Element der ersten Spalte der betrachteten Koeffizientenmatrix eine Null, so ist es nicht möglich, dieses durch Multiplikation zu einer führenden Eins zu machen. In diesem Fall wird ein von Null verschiedenes Element der ersten Spalte – das sogenannte Pivotelement – gewählt und die erste Zeile mit der Pivotzeile vertauscht. Diese Art der Pivotisierung wird Spaltenpivotisierung genannt.

\[ \left[ \begin{array}{ccc|c} {\color{orange}{0}} & {\color{orange}{2}} & {\color{orange}{1}} & {\color{orange}{1}} \\[0.25em] {\color{blue}{1}} & 0 & 3 & 2\\[0.25em] 2 & 5 & 3 & 3 \end{array} \right] \quad\overset{Z_1 \leftrightarrow Z_2}{\longrightarrow}\quad \left[ \begin{array}{ccc|c} {\color{blue}{1}} & 0 & 3 & 2\\[0.25em] {\color{orange}{0}} & {\color{orange}{2}} & {\color{orange}{1}} & {\color{orange}{1}} \\[0.25em] 2 & 5 & 3 & 3 \end{array} \right] \]

Für die Berechnung per Hand ist es oftmals sinnvoll, eine $1$ oder $-1$ als Pivotelement zu wählen, da so im weiteren Verlauf des Verfahrens weniger bzw. keine Brüche entstehen. Für die Berechnung mithilfe eines Computers ist es hingegen empfehlenswert, das betragsgrößte Element als Pivotelement zu wählen, um die numerische Stabilität des Gauß-Algorithmus zu verbessern.

Eine weitere Option ist es, ein Pivotelement aus der aktuellen Zeile zu wählen. In diesem Fall müssen dann die Spalten der Koeffizientenmatrix vertauscht werden. Wichtig: Hierbei wird ebenfalls die Reihenfolge der Variablen verändert, was beim Rückwärtseinsetzen entsprechend berücksichtigt werden muss. Die Wahl des Pivotelement aus der aktuellen Zeile wird Zeilenpivotisierung genannt.

\[ \left[ \begin{array}{ccc|c} {\color{orange}{0}} & 2 & {\color{blue}{1}} & 1 \\[0.25em] {\color{orange}{1}} & 0 & 3 & 2\\[0.25em] {\color{orange}{2}} & 5 & 3 & 3 \end{array} \right] \quad\overset{S_1 \leftrightarrow S_3}{\longrightarrow}\quad \left[ \begin{array}{ccc|c} {\color{blue}{1}} & 2 & {\color{orange}{0}} & 1\\[0.25em] 3 & 0 & {\color{orange}{1}} & 2 \\[0.25em] 3 & 5 & {\color{orange}{2}} & 3 \end{array} \right] \]

Es ist außerdem möglich, das betragsgrößte Element der gesamten betrachteten Koeffizientenmatrix als Pivotelement zu wählen. In diesem Fall sind im Allgemeinen sowohl Zeilen- als auch Spaltenvertauschungen notwendig. Diese Art der Pivotisierung wird vollständige Pivotisierung oder auch Totalpivotisierung genannt.

\[ \left[ \begin{array}{ccc|c} {\color{orange}{0}} & {\color{orange}{2}} & {\color{orange}{1}} & {\color{orange}{1}} \\[0.25em] {\color{orange}{1}} & 0 & 3 & 2\\[0.25em] {\color{orange}{2}} & {\color{blue}{5}} & 3 & 3 \end{array} \right] \quad\overset{\begin{array}{c} Z_1 \leftrightarrow Z_3 \\ S_1 \leftrightarrow S_2 \end{array}}{\longrightarrow}\quad \left[ \begin{array}{ccc|c} {\color{blue}{5}} & {\color{orange}{2}} & 3 & 3 \\[0.25em] 0 & {\color{orange}{1}} & 3 & 2 \\[0.25em] {\color{orange}{2}} & {\color{orange}{0}} & {\color{orange}{1}} & {\color{orange}{1}} \end{array} \right] \]

Simultanes Lösen von linearen Gleichungssystemen

Schematische Darstellung

Der Gauß-Algorithmus kann zum simultanen Lösen von linearen Gleichungssystemen verwendet werden, wenn diese dieselbe Koeffizientenmatrix besitzen und sich lediglich in ihren Ergebnisvektoren unterscheiden – wenn also die folgende Situation vorliegt:

\begin{align*} Ax &= b_1 \\[0.5em] &\ \, \vdots \\[0.5em] Ax &= b_k \end{align*}

Die Schritte, die zum Überführen der erweiterten Koeffizientenmatrix in Zeilenstufenform notwendig sind, hängen grundsätzlich nur von der Koeffizientenmatrix $A$ ab, und nicht von den konkreten Ergebnisvektoren $b_1,\ldots,b_k$ der einzelnen Gleichungssysteme. Für das Lösungsverfahren ergibt sich somit die folgende Überlegung: Anstatt die Koeffizientenmatrix nur um den Ergebnisvektor $b_1$ des ersten Gleichungssystems $Ax=b_1$ zu erweitern, wird dies für alle Gleichungssysteme getan:

\[ \bigl[ A \mid b_1 \mid \ldots \mid b_k \bigr] = \left[ \begin{array}{cccc|c|c|c} a_{11} & a_{12} & \cdots & a_{1n} & b_{11} & \cdots & b_{k1} \\[0.5em] a_{21} & a_{22} & \cdots & a_{2n} & b_{12} & \cdots & b_{k2} \\[0.5em] \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\[0.5em] a_{m1} & a_{m2} & \cdots & a_{mn} & b_{1m} & \cdots & b_{km} \end{array} \right] \]
Darstellung der mehrfach erweiterten Koeffizientenmatrix

Hinweis: Die Schreibweise $b_{ij}$ für die Vektorelemente bezeichnet in der obigen Darstellung den $j$-ten Eintrag des Vektors $b_i$ und entspricht nicht der typischen Indexierung der Elemente einer Matrix.

Der Gauß-Algorithmus überführt nun alle linearen Gleichungssysteme simultan in die Zeilenstufenform. Das anschließende Bestimmen der Lösung durch Rückwärtssubstitution kann (und muss) für jedes System separat durchgeführt werden.

\[ \bigl[ A^\star \mid b_1^\star \mid \ldots \mid b_k^\star \bigr] = \left[ \begin{array}{cccc|c|c|c} 1_\mathcal{K} & a_{12}^\star & \cdots & a_{1n}^\star & b_{11}^\star & \cdots & b_{k1}^\star \\[0.5em] 0_\mathcal{K} & 1_\mathcal{K} & \cdots & a_{2n}^\star & b_{12}^\star & \cdots & b_{k2}^\star \\[0.5em] \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\[0.5em] 0_\mathcal{K} & 0_\mathcal{K} & \cdots & 1_\mathcal{K} & b_{1m}^\star & \cdots & b_{km}^\star \end{array} \right] \]
Darstellung der mehrfach erweiterten Koeffizientenmatrix in reduzierter Zeilenstufenform

Beispiel

In diesem Beispiel wird das simultane Lösen von zwei linearen Gleichungssystemen demonstriert. Gegeben seien die folgenden beiden Gleichungssysteme mit je zwei Gleichungen und zwei Variablen:

\begin{alignedat}{3} x_1 &\ + &\ 2x_2 &\ = &\ 1 \\[0.5em] -x_1 &\ - &\ x_2 &\ = &\ 1 \end{alignedat}

sowie

\begin{alignedat}{3} y_1 &\ + &\ 2y_2 &\ = &\ 3 \\[0.5em] -y_1 &\ - &\ y_2 &\ = &\ 2. \end{alignedat}

Beide Gleichungssysteme besitzen dieselben Koeffizienten und unterscheiden sich lediglich in ihrer rechten Seite. Zunächst wird die erweiterte Koeffizientenmatrix aufgestellt und anschließend mit dem Gauß-Algorithmus in Zeilenstufenform überführt.

\[ \begin{array}{rr|r|r|l} 1 & 2 & 1 & 3 & \\[0.25em] -1 & -1 & 1 & 2 & \text{II} + \text{I} \\[0.25em] \hline 1 & 2 & 1 & 3 & \\[0.25em] 0 & 1 & 2 & 5 & \end{array} \]

Das resultierende, transformierte erste Gleichungssystem kann an der untersten Matrix direkt abgelesen werden.

\begin{alignedat}{4} x_1 &\ + &\ 2x_2 &\ = &\ 1 \\[0.5em] &\ &\ x_2 &\ = &\ 2 \end{alignedat}

Der Wert der Variable $x_2$ folgt unmittelbar aus der zweiten Gleichung.

\[ x_2=2 \]

Anschließend kann die erste Gleichung nach $x_1$ umgestellt und mit dem zuvor bestimmten Wert $x_2=2$ aufgelöst werden.

\begin{align*} x_1 &= 1 - 2x_2 \\[0.5em] &= 1 - 2 \cdot 2 \\[0.5em] &= -3 \end{align*}

Als Gesamtlösung des ersten linearen Gleichungssystems ergibt sich somit

\[ x = \left[\begin{array}{r} x_1 \\[0.25em] x_2 \end{array}\right] = \left[\begin{array}{r} -3 \\[0.25em] 2 \end{array}\right]. \]

Analog ergibt sich für das zweite System:

\[ y = \left[\begin{array}{r} y_1 \\[0.25em] y_2 \end{array}\right] = \left[\begin{array}{r} -7 \\[0.25em] 5 \end{array}\right]. \]

Weitere Anwendungsfälle

Bestimmen der Basis des Zeilen- oder Spaltenraums einer Matrix

Hauptartikel: Basis eines Vektorraums

Zum Bestimmen einer Basis des Zeilenraums einer Matrix wird diese mit dem Gauß-Verfahren zunächst in Zeilenstufenform überführt. Alle Zeilenvektoren, die vom Nullvektor verschieden sind, bilden dann eine Basis des Zeilenraums. Das Bestimmen einer Basis des Spaltenraums kann analog auf das Bestimmen einer Basis des Zeilenraums der transponierten Matrix zurückgeführt werden.

Bestimmen des Rangs einer Matrix

Hauptartikel: Rang einer Matrix

Zum Bestimmen des Rangs einer Matrix wird diese mit dem Gauß-Verfahren zunächst in Zeilenstufenform überführt. Der Rang der Matrix entspricht dann der Anzahl der Zeilenvektoren, die vom Nullvektor verschieden sind.

Aussagen zur Lösbarkeit von linearen Gleichungssystemen

Mithilfe des Rangs der Koeffizientenmatrix $A$ und des Rangs der erweiterten Koeffizientenmatrix $[A \mid b]$ kann eine Aussage darüber getroffen werden, ob das zugehörige lineare Gleichungssystem mit $n$ Variablen keine, eine oder unendlich viele Lösungen besitzt. Das Gleichungssystem besitzt

  • keine Lösung, falls der Rang der Koeffizientenmatrix kleiner als der Rang der erweiterten Koeffizientenmatrix ist, falls also gilt:
    \[ \rang(A) \lt \rang([A \mid b]); \]
  • eine Lösung, falls der Rang der Koeffizientenmatrix mit dem Rang der erweiterten Koeffizientenmatrix übereinstimmt und der Anzahl der Variablen entspricht, falls also gilt:
    \[ \rang(A) = \rang([A \mid b]) = n; \]
  • unendlich viele Lösungen, falls die Ränge der Matrizen übereinstimmen, der Rang aber kleiner als die Anzahl der Variablen ist, falls also gilt:
    \[ \rang(A) = \rang([A \mid b]) \lt n. \]

Bestimmen der Determinante

Hauptartikel: Determinante

Die Determinante einer quadratischen $n \times n $ Matrix $A^\star$ in Zeilenstufenform kann besonders einfach als Produkt der Hauptdiagonalelemente berechnet werden. Es gilt in diesem Fall

\[ \det\left( A^\star \right) = \prod\limits_{i=1}^{n}{a_{ii}}. \]

Zum Berechnen der Determinante einer beliebigen quadratischen Matrix kann diese also zunächst mit dem Gauß-Verfahren in Zeilenstufenform überführt werden. Hierbei ist zu beachten, dass elementare Zeilenumformungen die Determinante verändern können:

  • Vertauschen von zwei Zeilen verändert die Determinante um den Faktor $-1$;
  • Multiplikation einer Zeile mit einer Konstanten multipliziert die Determinante mit derselben Konstanten;
  • Addition von Vielfachen einer Zeile zu einer anderen Zeile verändert die Determinante nicht.

Um die Determinante der Originalmatrix zu erhalten, muss folglich die Determinante der Matrix in Zeilenstufenform, entsprechend der beim Überführen in Zeilenstufenform gemachten elementaren Zeilenumformungen, zurückgerechnet werden.

Bestimmen der inversen Matrix

Hauptartikel: Inverse Matrix

Die inverse Matrix kann mithilfe des Gauß-Jordan-Algorithmus berechnet werden. Hierzu wird die zu invertierende Matrix mithilfe elementarer Zeilenumformungen in die Einheitsmatrix überführt und dieselben Umformungen parallel auf einer Einheitsmatrix durchgeführt, welche bei Existenz der inversen Matrix in diese übergeht.