Gaußsches Eliminationsverfahren

Das Gaußsche Eliminationsverfahren oder Gauß-Algorithmus ist ein algorithmisches Verfahren zur Lösung linearer Gleichungssysteme. Es basiert auf elementaren Zeilenumformungen von Matrizen und ermöglicht Aussagen über Existenz, Eindeutigkeit und Struktur der 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 Zeilenstufenform. Wird die erweiterte Koeffizientenmatrix in reduzierte Zeilenstufenform gebracht, sprechen wir vom Gauß-Jordan-Algorithmus.

Zulässige elementare Zeilenumformungen sind:

• Vertauschen zweier Zeilen,
• Multiplikation einer Zeile mit einer von null verschiedenen Zahl,
• Addition eines Vielfachen einer Zeile zu einer anderen Zeile.

Diese Umformungen verändern die Lösungsmenge des linearen Gleichungssystems nicht.

Ziel des Verfahrens

Ziel ist es, die Matrix so umzuformen, dass

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

Damit lassen sich Existenz und Anzahl der Lösungen 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].
• Die Inverse [math]\displaystyle{ A^{-1} }[/math] kann mithilfe des Gauß-Jordan-Algorithmus bestimmt werden, indem man die Matrix [math]\displaystyle{ (A|I) }[/math] auf [math]\displaystyle{ (I|A^{-1}) }[/math] umformt.

Lineare Matrizengleichungen

Matrizengleichungen der Form [math]\displaystyle{ A \cdot X = B }[/math] können mit der Inversen gelöst werden: [math]\displaystyle{ X = A^{-1} \cdot B }[/math], sofern [math]\displaystyle{ A }[/math] invertierbar ist.

Anwendungen in mehrstufigen Produktionsprozessen

In der Produktionswirtschaft werden Inverse von Matrizen genutzt, um

• Stücklisten zu rekonstruieren,
• benötigte Rohstoffmengen zu bestimmen,
• mehrstufige Produktionsprozesse zu analysieren.

Ist beispielsweise eine Herstellungsmatrix invertierbar, lassen sich aus Endproduktmengen 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

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

Wir multiplizieren die erste Zeile mit 2 und erhalten:

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

Wir subtrahieren Zeile 1 von Zeile 2:

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

Wir teilen Zeile 1 durch 2 und erhalten die folgende Zeilenstufenform:

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

Wir subtrahieren Zeile 2 von Zeile 1 und erhalten die erweiterte Koeffizientenmatrix in reduzierter Zeilenstufenform:

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

Nach Anwendung des Gauß-Verfahrens können wir die Lösung direkt ablesen: [math]\displaystyle{ x_1 = 2 }[/math], [math]\displaystyle{ x_2 = 3 }[/math]

Bestimmung der Inversen

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

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

mit Hilfe des Gauß'schen Eliminationsverfahrens:

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

Wir multiplizieren Zeile 2 mit der Zahl 3:

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

Wir subtrahieren Zeile 2 von Zeile 1:

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

Wir dividieren Zeile 2 durch 2 und Zeile 1 durch 3:

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

Wir subtrahieren 2 mal Zeile 2 von Zeile 1:

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

Die Inverse zu Matrix [math]\displaystyle{ A }[/math] ist damit [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.