MathGymOS/ LGS/ Der Gauß-Algorithmus

(Teilweise aus: Gaußsches Eliminationsverfahren (Wikipedia).)

Ein lineares Gleichungssystem mit drei Variablen bzw. Unbekannten $\left(x_{1},x_{2},x_{3}\right)$ und den jeweiligen Koeffizienten $a_{i},b_{i},c_{i},e_{i}\;(i=1,\ldots ,3)$ hat die Form:

${\begin{array}{ccccccccc}(1)&a_{1}\cdot x_{1}&+&b_{1}\cdot x_{2}&+&c_{1}\cdot x_{3}&=&e_{1}\\(2)&a_{2}\cdot x_{1}&+&b_{2}\cdot x_{2}&+&c_{2}\cdot x_{3}&=&e_{2}\\(3)&a_{3}\cdot x_{1}&+&b_{3}\cdot x_{2}&+&c_{3}\cdot x_{3}&=&e_{3}\\\end{array}}$

Es werden schematisch nur die Koeffizienten (a, b, c, e) geschrieben:

$\left[{\begin{array}{ccc|c}a_{1}&b_{1}&c_{1}&e_{1}\\a_{2}&b_{2}&c_{2}&e_{2}\\a_{3}&b_{3}&c_{3}&e_{3}\end{array}}\right]$

Der Algorithmus zur Berechnung der Variablen x, y und z lässt sich in zwei Etappen einteilen:

1. Vorwärtselimination
2. Rückwärtseinsetzen (Rücksubstitution)

Im ersten Schritt wird das Gleichungssystem durch Äquivalenzumformungen, bei denen die Informationen des Gleichungssystems nicht geändert werden, in die Stufenform gebracht. Stufenform heißt, dass pro Zeile mindestens eine Variable weniger auftritt, also mindestens eine Variable eliminiert wird, indem die Zeile so umgeformt wird, dass der Koeffizient der Variablen Null ist. Im obigen Beispiel würde man $a_{2}$, $a_{3}$ und $b_{3}$ eliminieren.

$\left[{\begin{array}{ccc|c}m_{1}&n_{1}&k_{1}&l_{1}\\0&n_{2}&k_{2}&l_{2}\\0&0&k_{3}&l_{3}\end{array}}\right]$

Zum Erreichen der Stufenform sind drei Umformungen zulässig:

1. Es können (komplette) Zeilen vertauscht werden.
2. Eine Zeile kann mit einer von Null verschiedenen Zahl multipliziert werden.
3. Es darf, wie beim Additionsverfahren, eine Zeile oder das Vielfache einer Zeile zu einer anderen Zeile addiert werden.

Im zweiten Schritt werden ausgehend von der letzten Zeile, in der sich nur noch eine Variable befindet, die Variablen ausgerechnet und in die darüberliegende Zeile eingesetzt.

Regel: Anzahl der Lösungen

Ein lineares Gleichungssystem kann eine, unendlich viele oder keine Lösung haben. Diese Unterscheidung kann schon nach der Vorwärtselimination getroffen werden. Das System besitzt:

• genau eine eindeutige Lösung, wenn kein Element der Diagonalen $\left(m_{1},n_{2},k_{3}\right)$ Null ist.
• keine oder keine eindeutige Lösungen, wenn ein Element der Diagonalen Null ist.
  Befindet sich die einzige Null auf der Diagonalen in der letzten Zeile $(k_{3}=0)$, so besitzt das System
  • keine Lösungen, wenn auf der rechten Seite ($l_{3}$) eine Zahl ungleich Null steht, da es sich dann um eine falsche (unerfüllbare) Aussage handelt (z. B. $0=1$).
  • unendlich viele Lösungen und ist nicht eindeutig lösbar, wenn dort eine Null steht, da es sich um eine wahre Aussage ($0=0$) handelt.

 

Beispiele

• Beispiel 1: LGS mit eindeutiger Lösung

${\begin{array}{ccccccccc}(1)&1\cdot x_{1}&+&2\cdot x_{2}&+&2\cdot x_{3}&=&-2\\(2)&2\cdot x_{1}&+&3\cdot x_{2}&+&1\cdot x_{3}&=&1\\(3)&3\cdot x_{1}&+&4\cdot x_{2}&+&1\cdot x_{3}&=&3\end{array}}$

In schematischer Darstellung:

${\begin{array}{c}(1.)\\(2.)\\(3.)\end{array}}\left[{\begin{array}{ccc|c}1&2&2&-2\\2&3&1&1\\3&4&1&3\end{array}}\right]{\begin{array}{l}(1.)\cdot (-6)\\(2.)\cdot 3\\(3.)\cdot 2\end{array}}\Rightarrow {\begin{array}{c}(4.)\\(5.)\\(6.)\end{array}}\left[{\begin{array}{ccc|c}-6&-12&-12&12\\6&9&3&3\\6&8&2&6\end{array}}\right]{\begin{array}{l}(4.)\\(4.)+(5.)\\(4.)+(6.)\end{array}}\Rightarrow$

${\begin{array}{c}(7.)\\(8.)\\(9.)\end{array}}\left[{\begin{array}{ccc|c}-6&-12&-12&12\\0&-3&-9&15\\0&-4&-10&18\end{array}}\right]{\begin{array}{l}(7.)\\(8.)\cdot 4\\(9.)\cdot (-3)\end{array}}\Rightarrow {\begin{array}{c}(10.)\\(11.)\\(12.)\end{array}}\left[{\begin{array}{ccc|c}-6&-12&-12&12\\0&-12&-36&60\\0&12&30&-54\end{array}}\right]{\begin{array}{l}(10.)\\(11.)\\(11.)+(12.)\end{array}}$

$\Rightarrow {\begin{array}{c}(13.)\\(14.)\\(15.)\end{array}}\left[{\begin{array}{ccc|c}-6&-12&-12&12\\0&-12&-36&60\\0&0&-6&6\end{array}}\right]$

Die Stufenform ist erreicht. Das LGS ist eindeutig lösbar, da die Diagonale keine Null enthält.

Die letzte Zeile (15.) ist gleichbedeutend mit $-6\cdot x_{3}=6$, also $\left.x_{3}=-1\right.$.

Eingesetzt in der Zeile (14.) ergibt das $-12\cdot x_{2}+36=60$, also $\left.x_{2}=-2\right.$.

Die Ergebnisse für $x_{2}$ und </math>x_3</math> werden in Zeile (13.) eingesetzt. Das führt zu $-6\cdot x_{1}+24+12=12$, also $\left.x_{1}=4\right.$.

Die Lösungsmenge des LGS ist demnach:

${\mathfrak {L}}=\left\{(\,4\,|\,-2\,|\,-1\,)\right\}$

• Beispiel 2: LGS mit unendlich vielen Lösung

${\begin{array}{ccccccccc}(1)&1\cdot x_{1}&+&2\cdot x_{2}&+&2\cdot x_{3}&=&-2\\(2)&2\cdot x_{1}&+&3\cdot x_{2}&+&1\cdot x_{3}&=&1\\(3)&3\cdot x_{1}&+&5\cdot x_{2}&+&3\cdot x_{3}&=&-1\end{array}}$

In schematischer Darstellung:

${\begin{array}{c}(1.)\\(2.)\\(3.)\end{array}}\left[{\begin{array}{ccc|c}1&2&2&-2\\2&3&1&1\\3&5&3&-1\end{array}}\right]{\begin{array}{l}(1.)\cdot (-6)\\(2.)\cdot 3\\(3.)\cdot 2\end{array}}\Rightarrow {\begin{array}{c}(4.)\\(5.)\\(6.)\end{array}}\left[{\begin{array}{ccc|c}-6&-12&-12&12\\6&9&3&3\\6&10&6&-2\end{array}}\right]{\begin{array}{l}(4.)\\(4.)+(5.)\\(4.)+(6.)\end{array}}\Rightarrow$

${\begin{array}{c}(7.)\\(8.)\\(9.)\end{array}}\left[{\begin{array}{ccc|c}-6&-12&-12&12\\0&-3&-9&15\\0&-2&-6&10\end{array}}\right]{\begin{array}{l}(7.)\\(8.)\cdot \left(-{\frac {1}{3}}\right)\\(9.)\cdot {\frac {1}{2}}\end{array}}\Rightarrow {\begin{array}{c}(10.)\\(11.)\\(12.)\end{array}}\left[{\begin{array}{ccc|c}-6&-12&-12&12\\0&1&3&-5\\0&-1&-3&5\end{array}}\right]{\begin{array}{l}(10.)\\(11.)\\(11.)+(12.)\end{array}}$ :$\Rightarrow {\begin{array}{c}(13.)\\(14.)\\(15.)\end{array}}\left[{\begin{array}{ccc|c}-6&-12&-12&12\\0&1&3&-5\\0&0&0&0\end{array}}\right]$

Die Stufenform ist erreicht. Das LGS besitzt unendlich viele Lösungen, da Zeile (15.) $\left.0=0\right.$ bedeutet.

Aus Zeile (14.) entnimmt man $x_{2}+3\cdot x_{3}=-5$, also $x_{2}=-5-3\cdot x_{3}$.

Eingesetzt in Zeile (13.) ergibt das: $-6\cdot x_{1}-12\cdot (-5-3\cdot x_{3})-12\cdot x_{3}=12$.

Umformen ergibt $x_{1}=8+4\cdot x_{3}$.

Bei vorgegebenem $\left.x_{3}=t\right.$ sind also $x_{2}=-5-3\cdot t$ und $x_{1}=8+4\cdot t$.

Die Lösungsmenge des LGS ist demnach:

${\mathfrak {L}}=\left\{(\,8+4\,t\,|\,-5-3\,t\,|\,t\,),\;t\in \mathbb {R} \right\}$

• Beispiel 3: LGS ohne Lösung

${\begin{array}{ccccccccc}(1)&1\cdot x_{1}&+&2\cdot x_{2}&+&2\cdot x_{3}&=&-2\\(2)&2\cdot x_{1}&+&3\cdot x_{2}&+&1\cdot x_{3}&=&1\\(3)&3\cdot x_{1}&+&5\cdot x_{2}&+&3\cdot x_{3}&=&1\end{array}}$

In schematischer Darstellung:

${\begin{array}{c}(1.)\\(2.)\\(3.)\end{array}}\left[{\begin{array}{ccc|c}1&2&2&-2\\2&3&1&1\\3&5&3&1\end{array}}\right]{\begin{array}{l}(1.)\cdot (-6)\\(2.)\cdot 3\\(3.)\cdot 2\end{array}}\Rightarrow {\begin{array}{c}(4.)\\(5.)\\(6.)\end{array}}\left[{\begin{array}{ccc|c}-6&-12&-12&12\\6&9&3&3\\6&10&6&2\end{array}}\right]{\begin{array}{l}(4.)\\(4.)+(5.)\\(4.)+(6.)\end{array}}\Rightarrow$

${\begin{array}{c}(7.)\\(8.)\\(9.)\end{array}}\left[{\begin{array}{ccc|c}-6&-12&-12&12\\0&-3&-9&15\\0&-2&-6&5\end{array}}\right]{\begin{array}{l}(7.)\\(8.)\cdot \left(-2\right)\\(9.)\cdot 3\end{array}}\Rightarrow {\begin{array}{c}(10.)\\(11.)\\(12.)\end{array}}\left[{\begin{array}{ccc|c}-6&-12&-12&12\\0&6&18&-30\\0&-6&-18&15\end{array}}\right]{\begin{array}{l}(10.)\\(11.)\\(11.)+(12.)\end{array}}$

$\Rightarrow {\begin{array}{c}(13.)\\(14.)\\(15.)\end{array}}\left[{\begin{array}{ccc|c}-6&-12&-12&12\\0&6&18&-30\\0&0&0&-15\end{array}}\right]$

Die Stufenform ist erreicht. Das LGS besitzt keine Lösungen, da Zeile (15.) $\left.0=-15\right.$ bedeutet.

Die Lösungsmenge des LGS ist demnach:

${\mathfrak {L}}=\emptyset$

 

Zurück zu "Matrizen-Invertierung" | Hoch zum "Lineare Gleichungssysteme" | Vor zu "Das Determinanten-Verfahren"