de
Seitenbanner
Menu
A-Z
Nachlesen

Gaußsches Eliminationsverfahren

Beim gaußschen Eliminationsverfahren (auch Gauß-Verfahren oder Gauß-Algorithmus) handelt es sich um einen Algorithmus aus den Bereichen der linearen Algebra und der Numerik, der zum Lösen von linearen Gleichungssystemen verwendet werden kann.

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

Inhalt

Beschreibung des Verfahrens

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 Lösungsvektor dar.

In expliziter Form lautet das Gleichungssystem wie folgt:

\begin{align*} \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} \end{align*}

Zur vereinfachten Darstellung bietet es sich an, anstelle der expliziten Form des linearen Gleichungssystems die erweiterte Koeffizientenmatrix \(\lbrack A \mid b \rbrack\) zu verwenden, die man erhält, wenn man die Koeffizientenmatrix \(A\) um den Lösungsvektor \(b\) erweitert. Jede Zeile repräsentiert dabei eine der ursprünglichen Gleichungen. Jede Spalte der Koeffizientenmatrix repräsentiert eine der Variablen.

\[ \bigl\lbrack A \mid b \bigr\rbrack = \left\lbrack\begin{array}{cccc|c} a_{11} & a_{21} & \ldots & a_{1n} & b_1 \\[0.5em] a_{21} & a_{22} & \ldots & a_{2n} & b_2 \\[0.5em] \vdots & \vdots & \ddots & \vdots & \vdots \\[0.5em] a_{m1} & a_{m1} & \ldots & a_{mn} & b_m \end{array}\right\rbrack \]

Vorwärtselimination

Im ersten Schritt wird die erweiterte Koeffizientenmatrix 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.

Überführt man die Matrix mit dem optionalen nachfolgenden Schritt zusätzlich in reduzierte Zeilenstufenform, so erhält man den Gauß-Jordan-Algorithmus.

  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 \(\lbrack A^\star \mid b^\star \rbrack\) liegt nun in Zeilenstufenform vor.

\[ \bigl\lbrack A^\star \mid b^\star \bigr\rbrack = \left\lbrack\begin{array}{cccc|c} a_{11}^\star & a_{21}^\star & \ldots & a_{1n}^\star & b_1^\star \\[0.5em] 0 & a_{22}^\star & \ldots & a_{2n}^\star & b_2^\star \\[0.5em] \vdots & \vdots & \ddots & \vdots & \vdots \\[0.5em] 0 & 0 & \ldots & a_{mn}^\star & b_m^\star \end{array}\right\rbrack \]

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

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

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: 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 nach der jeweils einzigen verbleibenden Variable umgestellt und aufgelöst werden können.

Abhängig von dem zu lösenden linearen Gleichungssystem kann es vorkommen, dass die Matrix \(\lbrack A^\star \mid b^\star \rbrack\) 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 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.

Beispiele

Beispiel 1

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

\begin{align*} \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} \end{align*}

Zunächst wird die erweiterte Koeffizientenmatrix aufgestellt.

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

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{align*} \begin{alignedat}{4} x_1 &\ - &\ x_2 &\ - &\ 2x_3 &\ = &\ 1 \\[0.5em] &\ &\ x_2 &\ + &\ 2x_3 &\ = &\ 2 \\[0.5em] &\ &\ &\ &\ x_3 &\ = &\ 3 \end{alignedat} \end{align*}

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\lbrack\begin{array}{r} x_1 \\[0.25em] x_2 \\[0.25em] x_3 \end{array}\right\rbrack = \left\lbrack\begin{array}{r} 3 \\[0.25em] -4 \\[0.25em] 3 \end{array}\right\rbrack. \]

Beispiel 2

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

\begin{align*} \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} \end{align*}

Zunächst wird die erweiterte Koeffizientenmatrix aufgestellt.

\[ \left\lbrack \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\rbrack \]

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{align*} \begin{alignedat}{5} x_1 &\ - &\ 3x_2 &\ - &\ x_3 &\ + &\ 3x_4 &\ = &\ 0 \\[0.5em] &\ &\ &\ &\ x_3 &\ + &\ x_4 &\ = &\ 3 \end{alignedat} \end{align*}

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\lbrack\begin{array}{r} x_1 \\[0.25em] x_2 \\[0.25em] x_3 \\[0.25em] x_4 \end{array}\right\rbrack = \left\lbrack\begin{array}{c} 3+3s-4t \\[0.25em] s \\[0.25em] 3-t \\[0.25em] t \end{array}\right\rbrack = \left\lbrack\begin{array}{r} 3 \\[0.25em] 0 \\[0.25em] 3 \\[0.25em] 0 \end{array}\right\rbrack + s \cdot \left\lbrack\begin{array}{r} 3 \\[0.25em] 1 \\[0.25em] 0 \\[0.25em] 0 \end{array}\right\rbrack + t \cdot \left\lbrack\begin{array}{r} 4 \\[0.25em] 0 \\[0.25em] -1 \\[0.25em] 1 \end{array}\right\rbrack. \]

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\lbrack \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\rbrack \quad\overset{Z_1 \leftrightarrow Z_2}{\longrightarrow}\quad \left\lbrack \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\rbrack \]

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\lbrack \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\rbrack \quad\overset{S_1 \leftrightarrow S_3}{\longrightarrow}\quad \left\lbrack \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\rbrack \]

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\lbrack \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\rbrack \quad\overset{\begin{array}{c} Z_1 \leftrightarrow Z_3 \\ S_1 \leftrightarrow S_2 \end{array}}{\longrightarrow}\quad \left\lbrack \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\rbrack \]

Weitere Anwendungsfälle

Bestimmen der Basis des Zeilen- oder Spaltenraums einer Matrix

Hauptartikel: Basis

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

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 hat

  • keine Lösung, falls \(\rang(A) \neq \rang(A \mid b)\) gilt;
  • eine Lösung, falls \(\rang(A) = \rang(A \mid b) = n\) gilt;
  • unendlich viele Lösungen, falls \(\rang(A) = \rang(A \mid b) \lt n\) gilt.

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.