Gaußsches Eliminationsverfahren

Das Gaußsche Eliminationsverfahren (auch Gauß-Algorithmus) ist ein fundamentales algorithmisches Verfahren zur Lösung linearer Gleichungssysteme. Es basiert auf elementaren Zeilenumformungen von Matrizen und ermöglicht Aussagen über die Existenz, Eindeutigkeit und Struktur von Lösungsmengen. Das Verfahren ist eng mit der Theorie der Matrizen verknüpft.

Definition

Das Gaußsche Eliminationsverfahren ist ein Verfahren zur schrittweisen Umformung der erweiterten Koeffizientenmatrix [math]\displaystyle{ (A|b) }[/math] eines linearen Gleichungssystems in eine sogenannte Zeilenstufenform. Wird die erweiterte Koeffizientenmatrix sogar in die reduzierte Zeilenstufenform gebracht (Einsen auf der Hauptdiagonale, ansonsten nur Nullen), sprechen wir vom Gauß-Jordan-Algorithmus.

Zulässige elementare Zeilenumformungen sind:

• Vertauschen zweier Zeilen,
• Multiplikation einer Zeile mit einer von null verschiedenen reellen Zahl,
• Addition (oder Subtraktion) eines Vielfachen einer Zeile zu einer anderen Zeile.

Diese Umformungen verändern die Lösungsmenge des linearen Gleichungssystems nicht. Man nennt die resultierenden Matrizen daher äquivalent.

Ziel des Verfahrens

Ziel ist es, die Matrix so umzuformen, dass

• die Lösungen für die Variablen direkt abgelesen werden können oder
• der Rang der Matrix bestimmt werden kann.

Damit lassen sich die Existenz und die Anzahl der Lösungen (genau eine Lösung, unendlich viele Lösungen, keine Lösung) eindeutig beurteilen.

Zusammenhang mit der Inversen einer Matrix

Für eine quadratische Matrix [math]\displaystyle{ A }[/math] gilt:

• [math]\displaystyle{ A }[/math] ist genau dann invertierbar, wenn für den Rang von [math]\displaystyle{ A }[/math] gilt: [math]\displaystyle{ \operatorname{rang}(A) = n }[/math] (voller Rang).
• Die Inverse [math]\displaystyle{ A^{-1} }[/math] kann mithilfe des Gauß-Jordan-Algorithmus bestimmt werden, indem man die um die Einheitsmatrix erweiterte Matrix [math]\displaystyle{ (A|I) }[/math] durch elementare Zeilenumformungen auf die Form [math]\displaystyle{ (I|A^{-1}) }[/math] umformt.

Lineare Matrizengleichungen

Matrizengleichungen der Form

[math]\displaystyle{ A \cdot X = B }[/math]

können mithilfe der Inversen gelöst werden durch:

[math]\displaystyle{ X = A^{-1} \cdot B }[/math],

sofern [math]\displaystyle{ A }[/math] eine quadratische und invertierbare Matrix ist.

Anwendungen in mehrstufigen Produktionsprozessen

In der Produktionswirtschaft werden Inverse von Matrizen (insbesondere Verflechtungsmatrizen) genutzt, um

• Stücklisten zu rekonstruieren,
• benötigte Rohstoffmengen direkt aus Endproduktanforderungen zu bestimmen,
• mehrstufige Produktionsprozesse auf Effizienz zu analysieren.

Ist beispielsweise eine Herstellungsmatrix invertierbar, lassen sich aus den Zielvorgaben für die Endproduktmengen durch Rückwärtsrechnung direkt die erforderlichen Einsatzmengen berechnen.

Beispiele

Lösung eines linearen Gleichungssystems

Gegeben sei das System:

[math]\displaystyle{ \begin{aligned} x_1 + x_2 &= 5 \\ 2x_1 + 3x_2 &= 13 \end{aligned} }[/math]

Die Matrizengleichung lautet:

[math]\displaystyle{ \begin{pmatrix} 1 & 1 \\ 2 & 3 \\ \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \\ \end{pmatrix} = \begin{pmatrix} 5 \\ 13 \\ \end{pmatrix} }[/math]

Die erweiterte Koeffizientenmatrix lautet entsprechend:

[math]\displaystyle{ \left( \begin{array}{cc|c} 1 & 1 & 5 \\ 2 & 3 & 13 \end{array} \right) }[/math]

Schritt 1: Wir subtrahieren das 2-fache der ersten Zeile von der zweiten Zeile ([math]\displaystyle{ Z_2 \rightarrow Z_2 - 2 \cdot Z_1 }[/math]), um eine Null in der linken unteren Ecke zu erzeugen:

[math]\displaystyle{ \left( \begin{array}{cc|c} 1 & 1 & 5 \\ 0 & 1 & 3 \end{array} \right) }[/math]

(Die Matrix befindet sich nun bereits in Zeilenstufenform. Der reguläre Gauß-Algorithmus wäre hier beendet und man könnte rückwärts einsetzen. Für den Gauß-Jordan-Algorithmus rechnen wir jedoch weiter.)

Schritt 2: Wir subtrahieren die zweite Zeile von der ersten Zeile ([math]\displaystyle{ Z_1 \rightarrow Z_1 - Z_2 }[/math]), um die reduzierte Zeilenstufenform zu erhalten:

[math]\displaystyle{ \left( \begin{array}{cc|c} 1 & 0 & 2 \\ 0 & 1 & 3 \end{array} \right) }[/math]

Nach Anwendung des Verfahrens können wir die Lösung direkt ablesen:

[math]\displaystyle{ x_1 = 2 }[/math] und [math]\displaystyle{ x_2 = 3 }[/math].

Bestimmung der Inversen

Wir berechnen die Inverse [math]\displaystyle{ A^{-1} }[/math] zur folgenden Matrix:

[math]\displaystyle{ A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} }[/math]

Wir notieren die Matrix [math]\displaystyle{ A }[/math] gekoppelt mit der Einheitsmatrix [math]\displaystyle{ I }[/math]:

[math]\displaystyle{ \left( \begin{array}{cc|cc} 1 & 2 & 1 & 0 \\ 3 & 4 & 0 & 1 \end{array} \right) }[/math]

Schritt 1: Wir subtrahieren das 3-fache der ersten Zeile von der zweiten Zeile ([math]\displaystyle{ Z_2 \rightarrow Z_2 - 3 \cdot Z_1 }[/math]):

[math]\displaystyle{ \left( \begin{array}{cc|cc} 1 & 2 & 1 & 0 \\ 0 & -2 & -3 & 1 \end{array} \right) }[/math]

Schritt 2: Wir dividieren die zweite Zeile durch -2 ([math]\displaystyle{ Z_2 \rightarrow Z_2 / (-2) }[/math]), um auf der Diagonale eine 1 zu erhalten:

[math]\displaystyle{ \left( \begin{array}{cc|cc} 1 & 2 & 1 & 0 \\ 0 & 1 & \frac{3}{2} & -\frac{1}{2} \end{array} \right) }[/math]

Schritt 3: Wir subtrahieren das 2-fache der zweiten Zeile von der ersten Zeile ([math]\displaystyle{ Z_1 \rightarrow Z_1 - 2 \cdot Z_2 }[/math]):

[math]\displaystyle{ \left( \begin{array}{cc|cc} 1 & 0 & -2 & 1 \\ 0 & 1 & \frac{3}{2} & -\frac{1}{2} \end{array} \right) }[/math]

Auf der linken Seite steht nun die Einheitsmatrix. Auf der rechten Seite können wir die gesuchte Inverse zu Matrix [math]\displaystyle{ A }[/math] ablesen:

[math]\displaystyle{ A^{-1} = \begin{pmatrix} -2 & 1 \\ \frac{3}{2} & -\frac{1}{2} \end{pmatrix} }[/math]

Produktionswirtschaftliches Beispiel

Eine invertierbare Herstellungsmatrix beschreibt den Zusammenhang zwischen Zwischen- und Endprodukten. Mithilfe der Inversen können aus bekannten Endproduktmengen die erforderlichen Zwischenproduktmengen berechnet werden.