Gaußsches Eliminationsverfahren: Unterschied zwischen den Versionen

Das '''Gaußsche Eliminationsverfahren''' (auch '''Gauß-Algorithmus''') ist ein fundamentales algorithmisches Verfahren zur Lösung [[Lineares_Gleichungssystem|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 [[Matrix|Matrizen]] verknüpft.

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

* 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''.

* die Lösungen für die Variablen direkt abgelesen werden können oder

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

* <math>A</math> ist genau dann invertierbar, wenn für den [[Matrix#Rang|Rang]] von <math>A</math> gilt: <math>\operatorname{rang}(A) = n</math> (voller Rang).

* Die [[Matrix#Inverse|Inverse]] <math>A^{-1}</math> kann mithilfe des Gauß-Jordan-Algorithmus bestimmt werden, indem man die um die Einheitsmatrix erweiterte Matrix <math>(A|I)</math> durch elementare Zeilenumformungen auf die Form <math>(I|A^{-1})</math> umformt.

:<math>A \cdot X = B</math>

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

:<math>X = A^{-1} \cdot B</math>,

sofern <math>A</math> eine quadratische und invertierbare Matrix ist.

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

* 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.

=== Lösung eines linearen Gleichungssystems ===

Gegeben sei das System:

Die Matrizengleichung lautet:

\end{pmatrix} = \begin{pmatrix}

Die erweiterte Koeffizientenmatrix lautet entsprechend:

 

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

 

'''Schritt 2:''' Wir subtrahieren die zweite Zeile von der ersten Zeile (<math>Z_1 \rightarrow Z_1 - Z_2</math>), um die reduzierte Zeilenstufenform zu erhalten:

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

:<math>x_1 = 2</math> und <math>x_2 = 3</math>.

Wir berechnen die Inverse <math>A^{-1}</math> zur folgenden Matrix:

 

'''Schritt 1:''' Wir subtrahieren das 3-fache der ersten Zeile von der zweiten Zeile (<math>Z_2 \rightarrow Z_2 - 3 \cdot Z_1</math>):

1 & 2 & 1 & 0 \\

0 & -2 & -3 & 1

 

'''Schritt 2:''' Wir dividieren die zweite Zeile durch -2 (<math>Z_2 \rightarrow Z_2 / (-2)</math>), um auf der Diagonale eine 1 zu erhalten:

1 & 2 & 1  & 0 \\

0 & 1 & \frac{3}{2} & -\frac{1}{2}

 

'''Schritt 3:''' Wir subtrahieren das 2-fache der zweiten Zeile von der ersten Zeile (<math>Z_1 \rightarrow Z_1 - 2 \cdot Z_2</math>):

1 & 0 & -2 & 1 \\

0 & 1 & \frac{3}{2} & -\frac{1}{2}

Auf der linken Seite steht nun die Einheitsmatrix. Auf der rechten Seite können wir die gesuchte Inverse zu Matrix <math>A</math> ablesen:

:<math>