Gaußsches Eliminationsverfahren: Unterschied zwischen den Versionen
Keine Bearbeitungszusammenfassung |
|||
| (12 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
Das '''Gaußsche Eliminationsverfahren''' ist ein algorithmisches Verfahren zur Lösung [[Lineares_Gleichungssystem|linearer Gleichungssysteme]]. Es basiert auf elementaren Zeilenumformungen von Matrizen und ermöglicht Aussagen über Existenz, Eindeutigkeit und Struktur | 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. | ||
== Definition == | == Definition == | ||
Das Gaußsche Eliminationsverfahren ist ein Verfahren zur schrittweisen Umformung der [[Lineares_Gleichungssystem#Erweiterte_Koeffizientenmatrix|erweiterten Koeffizientenmatrix]] <math>(A|b)</math> eines [[Lineares_Gleichungssystem| | 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'''. | ||
Zulässige '''elementare Zeilenumformungen''' sind: | Zulässige '''elementare Zeilenumformungen''' sind: | ||
* Vertauschen zweier Zeilen, | * Vertauschen zweier Zeilen, | ||
* Multiplikation einer Zeile mit einer von null verschiedenen Zahl, | * Multiplikation einer Zeile mit einer von null verschiedenen reellen Zahl, | ||
* Addition eines Vielfachen einer Zeile zu einer anderen Zeile. | * Addition (oder Subtraktion) eines Vielfachen einer Zeile zu einer anderen Zeile. | ||
Diese Umformungen verändern die Lösungsmenge des | Diese Umformungen verändern die Lösungsmenge des linearen Gleichungssystems nicht. Man nennt die resultierenden Matrizen daher ''äquivalent''. | ||
== Ziel des Verfahrens == | == Ziel des Verfahrens == | ||
Ziel ist es, die Matrix so umzuformen, dass | Ziel ist es, die Matrix so umzuformen, dass | ||
* die Lösungen direkt abgelesen werden können oder | * die Lösungen für die Variablen direkt abgelesen werden können oder | ||
* der Rang der Matrix bestimmt werden kann. | * der Rang der Matrix bestimmt werden kann. | ||
Damit lassen sich Existenz und Anzahl der Lösungen eindeutig beurteilen. | 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 == | == Zusammenhang mit der Inversen einer Matrix == | ||
Für eine quadratische Matrix <math>A</math> gilt: | Für eine quadratische Matrix <math>A</math> gilt: | ||
* <math>A</math> ist genau dann invertierbar, wenn <math>\operatorname{rang}(A) = n</math>. | * <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 Inverse <math>A^{-1}</math> kann mithilfe des Gauß-Algorithmus bestimmt werden, indem man die Matrix <math>(A|I)</math> auf <math>(I|A^{-1})</math> umformt. | * 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. | ||
== Lineare Matrizengleichungen == | == Lineare Matrizengleichungen == | ||
Matrizengleichungen der Form | Matrizengleichungen der Form | ||
<math> | :<math>A \cdot X = B</math> | ||
A \cdot X = B | können mithilfe der Inversen gelöst werden durch: | ||
</math> | :<math>X = A^{-1} \cdot B</math>, | ||
können | sofern <math>A</math> eine quadratische und invertierbare Matrix ist. | ||
<math> | |||
X = A^{-1} \cdot B | |||
</math>, | |||
sofern <math>A</math> | |||
== Anwendungen in mehrstufigen Produktionsprozessen == | == Anwendungen in mehrstufigen Produktionsprozessen == | ||
In der Produktionswirtschaft werden Inverse von Matrizen genutzt, um | In der Produktionswirtschaft werden Inverse von Matrizen (insbesondere Verflechtungsmatrizen) genutzt, um | ||
* Stücklisten zu rekonstruieren, | * Stücklisten zu rekonstruieren, | ||
* benötigte Rohstoffmengen zu bestimmen, | * benötigte Rohstoffmengen direkt aus Endproduktanforderungen zu bestimmen, | ||
* mehrstufige Produktionsprozesse zu analysieren. | * mehrstufige Produktionsprozesse auf Effizienz zu analysieren. | ||
Ist beispielsweise eine Herstellungsmatrix invertierbar, lassen sich aus Endproduktmengen direkt die erforderlichen Einsatzmengen berechnen. | Ist beispielsweise eine Herstellungsmatrix invertierbar, lassen sich aus den Zielvorgaben für die Endproduktmengen durch Rückwärtsrechnung direkt die erforderlichen Einsatzmengen berechnen. | ||
== Beispiele == | == Beispiele == | ||
=== Lösung eines | === Lösung eines linearen Gleichungssystems === | ||
Gegeben sei das System | Gegeben sei das System: | ||
:<math> | :<math> | ||
\begin{aligned} | \begin{aligned} | ||
| Zeile 53: | Zeile 49: | ||
</math> | </math> | ||
Die | Die Matrizengleichung lautet: | ||
:<math>\begin{pmatrix} | :<math>\begin{pmatrix} | ||
1 & 1 \\ | 1 & 1 \\ | ||
| Zeile 60: | Zeile 56: | ||
x_1 \\ | x_1 \\ | ||
x_2 \\ | x_2 \\ | ||
\end{pmatrix}=\begin{pmatrix} | \end{pmatrix} = \begin{pmatrix} | ||
5 \\ | 5 \\ | ||
13 \\ | 13 \\ | ||
\end{pmatrix}</math> | \end{pmatrix}</math> | ||
Die | Die erweiterte Koeffizientenmatrix lautet entsprechend: | ||
:<math> | :<math> | ||
\left( | \left( | ||
| Zeile 74: | Zeile 70: | ||
\right) | \right) | ||
</math> | </math> | ||
Wir | |||
'''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: | |||
:<math> | :<math> | ||
\left( | \left( | ||
\begin{array}{cc|c} | \begin{array}{cc|c} | ||
1 & 1 & 5 \\ | |||
0 & 1 & 3 | |||
\end{array} | \end{array} | ||
\right) | \right) | ||
</math> | </math> | ||
Wir subtrahieren Zeile | ''(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>Z_1 \rightarrow Z_1 - Z_2</math>), um die reduzierte Zeilenstufenform zu erhalten: | |||
:<math> | :<math> | ||
\left( | \left( | ||
\begin{array}{cc|c} | \begin{array}{cc|c} | ||
1 & 0 & 2 \\ | |||
0 & 1 & 3 | 0 & 1 & 3 | ||
\end{array} | \end{array} | ||
\right) | \right) | ||
</math> | </math> | ||
Wir | |||
Nach Anwendung des Verfahrens können wir die Lösung direkt ablesen: | |||
:<math>x_1 = 2</math> und <math>x_2 = 3</math>. | |||
=== Bestimmung der Inversen === | |||
Wir berechnen die Inverse <math>A^{-1}</math> zur folgenden Matrix: | |||
:<math> | |||
A = \begin{pmatrix} | |||
1 & 2 \\ | |||
3 & 4 | |||
\end{pmatrix} | |||
</math> | |||
Wir notieren die Matrix <math>A</math> gekoppelt mit der Einheitsmatrix <math>I</math>: | |||
:<math> | :<math> | ||
\left( | \left( | ||
\begin{array}{cc| | \begin{array}{cc|cc} | ||
1 & 1 & | 1 & 2 & 1 & 0 \\ | ||
0 & 1 | 3 & 4 & 0 & 1 | ||
\end{array} | \end{array} | ||
\right) | \right) | ||
</math> | </math> | ||
Wir subtrahieren Zeile | |||
'''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>): | |||
:<math> | :<math> | ||
\left( | \left( | ||
\begin{array}{cc| | \begin{array}{cc|cc} | ||
1 & 0 | 1 & 2 & 1 & 0 \\ | ||
0 & | 0 & -2 & -3 & 1 | ||
\end{array} | \end{array} | ||
\right) | \right) | ||
</math> | </math> | ||
'''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: | |||
:<math> | |||
\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>Z_1 \rightarrow Z_1 - 2 \cdot Z_2</math>): | |||
:<math> | |||
<math> | \left( | ||
\begin{array}{cc|cc} | |||
1 & 2 \\ | 1 & 0 & -2 & 1 \\ | ||
3 & | 0 & 1 & \frac{3}{2} & -\frac{1}{2} | ||
\end{ | \end{array} | ||
\right) | |||
</math> | </math> | ||
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> | :<math> | ||
A^{-1} = \begin{pmatrix} | A^{-1} = \begin{pmatrix} | ||
-2 & 1 \\ | -2 & 1 \\ | ||