Gaußsches Eliminationsverfahren

Das Gaußsche Eliminationsverfahren 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 oder reduzierte Zeilenstufenform.

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 [math]\displaystyle{ \operatorname{rang}(A) = n }[/math].
• Die Inverse [math]\displaystyle{ A^{-1} }[/math] kann mithilfe des Gauß-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:

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

Wir subtrahieren Zeile 2 von Zeile 1:

[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

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

Durch Anwendung des Gauß-Algorithmus auf [math]\displaystyle{ (A|I) }[/math] erhält man [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.