TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 547

Bestimmen Sie mit dem Gauß'schen Eliminationsverfahren die Lösung des Gleichungssystems über dem Körper $K$ :
a) $K=\mathbb {R}$
b) $K=\mathbb {Z} _{2}$

${\begin{array}{rcrcrcrl}3x_{1}&+&x_{2}&-&2x_{3}&+&x_{4}&=2\\x_{1}&+&x_{2}&-&x_{3}&-&x_{4}&=1\\5x_{1}&+&x_{2}&-&3x_{3}&+&3x_{4}&=1\end{array}}$

Dieses Beispiel ist als solved markiert. Ist dies falsch oder ungenau? Aktualisiere den Lösungsstatus (Details: Vorlage:Beispiel)

Lösungsvorschlag von Hapi[Bearbeiten | Quelltext bearbeiten]

1. Schritt: nach dem Gauss-schen Eliminationsvervahren die erste und 2. Zeile vertauschen und aufschreiben

  1  1 -1 -1 | 1
  3  1 -2  1 | 2
  5  1 -3  3 | 1

2. Schritt: die erste Zeile 3× von der 2. Zeile und 5× von der 3. Zeile subtrahieren

  1  1 -1 -1 |  1
  0 -2  1  4 | -1 ( 2 - 3 )
  0 -4  2  8 | -4 ( 1 - 5 )

3. Schritt: vertauschen Spalte 2 und 3, damit in der 2. Zeile 1 an erster Stelle steht (x1, x3, x2, x4 !)

  1 -1  1 -1 |  1
  0  1 -2  4 | -1
  0  2 -4  8 | -4

4. Schritt: Zeile 2 von Zeile 3 dann 2x abziehen

  1 -1  1 -1 |  1
  0  1 -2  4 | -1 
  0  0  0  0 | -2

Falls kein Rechenfehler unterlaufen ist, ist das Gleichungssystem nicht lösbar.

Die dritte Zeile ergibt nämlich 4x die Variablen mit 0 multipliziert können nur 0 ergeben, nicht aber -2.

Hapi

Lösungsvorschlag von m0mo[Bearbeiten | Quelltext bearbeiten]

1. Schritt: Da wir uns in den Restklassen befinden können wir hier ein wenig kürzen!

  3  1 -2  1 | 2   
  1  1 -1 -1 | 1
  5  1 -3  3 | 1

-->

  1  1  0  1 | 0   
  1  1 -1 -1 | 1
  1  1 -1  1 | 1

2. Schritt: z2-z1 und z3-z1

  1  1  0  1 | 0   
  0  0 -1 -2 | 1
  0  0 -1  0 | 1

-->

  1  1  0 1 | 0   
  0  0 -1 0 | 1
  0  0 -1 0 | 1

3. Schritt: z3-z2

  1  1  0 1 | 0   
  0  0 -1 0 | 1
  0  0  0 0 | 0

4. Schritt: vertauschen der Spalten x2 und x3

  1  0 1 1 | 0   
  0 -1 0 0 | 1
  0  0 0 0 | 0

Falls kein Rechenfehler unterlaufen ist, ist das Gleichungssystem nicht lösbar.

Wie wir sehen ist zwar x3 berechenbar mit x3 = -1 jedoch x2 und x4 zum berrechnen von x1 sind nicht eindeutig!

x1 = -(x2+x4) x2 und x4 sind unbekannt!

Anmerkung von Ryus[Bearbeiten | Quelltext bearbeiten]

Nur weil die Lösung nicht eindeutig ist, ist das Gleichungssystem deswegen noch lange nicht unlösbar. Wir haben nur eine Lösungsmenge aus mehreren Elementen.

Unsere Matrix schaut so aus:

  1  0 1 1 | 0   
  0  1 0 0 | 1

Da wir auf der linken Seite die Einheitsmatrix haben, können wir das im Buch gezeigte Verfahren (Satz. 3.44) verwenden, um die allgemeine Lösung in Parameterdarstellung zu zeigen:

$\mathbf {x} ={\begin{pmatrix}0\\1\\0\\0\\\end{pmatrix}}+{\begin{pmatrix}1&1\\0&0\\1&0\\0&1\end{pmatrix}}*{\begin{pmatrix}t_{1}\\t_{2}\end{pmatrix}}$

Der Vektor links ist einfach die rechte Seite des Gleichungssystems um zwei Nuller ergänzt. Die ersten zwei Zeilen der Matrix bestehen aus der negativen rechten Teilmatrix im 2x4-Block (-1 = 1 in Z2) und der 2x2-Einheitsmatrix darunter. Da wir die Spalten 2 und 3 vertauscht haben, müssen wir dies hier aber nun noch entsprechend rückgängig machen. Durch weitere Auflösung erhält man dann:

$\mathbf {x} ={\begin{pmatrix}0\\0\\1\\0\\\end{pmatrix}}+{\begin{pmatrix}1\\1\\0\\0\end{pmatrix}}*t_{1}+{\begin{pmatrix}1\\0\\0\\1\end{pmatrix}}*t_{2}$

Da wir in Z2 sind uns es für die Variablen nur zwei Werte gibt, können wir sogar alle Ergebnisse ausrechnen:

$L=\left\{{\begin{pmatrix}0\\0\\1\\0\end{pmatrix}},{\begin{pmatrix}1\\0\\1\\1\end{pmatrix}},{\begin{pmatrix}1\\1\\1\\0\end{pmatrix}},{\begin{pmatrix}0\\1\\1\\1\end{pmatrix}}\right\}$

Hilfreiches von Har203[Bearbeiten | Quelltext bearbeiten]

Lineares Gleichungssystem

Gauß'sches Eliminationsverfahren

Das gaußsche Eliminationsverfahren oder einfach Gauß-Verfahren (nach Carl Friedrich Gauß) ist ein Algorithmus aus den mathematischen Teilgebieten der linearen Algebra und der Numerik Numerik. Es ist ein wichtiges Verfahren zum Lösen von linearen Gleichungssystemen und beruht darauf, dass Äquivalenzumformungen zwar das Gleichungssystem ändern, aber die Lösung erhalten. Dies erlaubt es, jedes eindeutig lösbare Gleichungssystem auf Stufenform zu bringen, an der die Lösung durch sukzessive Elimination der Unbekannten leicht ermittelt oder die Lösungsmenge abgelesen werden kann.

LGS-Äquivalenzumformungen

Allgemein gilt: Die Lösungsgesamtheit eines linearen Gleichungssystems ändert sich durch folgende Äquivalenzumformungen nicht:

Vertauschen zweier Zeilen/Spalten,
Multiplikation einer Zeile/Spalte mit einem Faktor $\neq 0$ ,
Addition einer Zeile/Spalte (mit einem Faktor) zu einer anderen Zeile/Spalte.

Zeilen-/Spaltenrang einer Matrix

Für eine Matrix $A$ definiert man den Zeilenraum $ZR(A)$ als die lineare_Hülle der Zeilenvektoren aus $A$ . Die [Dimension des Zeilenraums bezeichnet man als Zeilenrang, sie entspricht der Maximalzahl linear unabhängiger Zeilenvektoren.

Analog definiert man den Spaltenraum $SR(A)$ und den Spaltenrang durch die Spaltenvektoren. Man kann für Matrizen mit Elementen aus einem Körper zeigen, dass der Zeilen- und Spaltenrang jeder Matrix gleich ist. Dies gilt für Matrizen über einem beliebigen kommutativen Ring, der kein Körper ist, im Allgemeinen nicht.

Rang

Bei einer linearen Abbildung $f$ ist der Rang als Dimension des Bildes dieser Abbildung definiert. Dabei gilt stets, dass eine lineare Abbildung und die zugehörige Abbildungsmatrix denselben Rang haben:

\operatorname {rg} (f)=\dim(\operatorname {im} (f))

, also dem Bild der Abbildung

f

.

Lösungsvorschlag von Har203[Bearbeiten | Quelltext bearbeiten]

Bestimmen Sie mit dem Gaußschen Eliminationsverfahren die Lösung des Gleichungssystems über dem Körper $K$ . a) $K=\mathbb {R} \quad$ b) $K=\mathbb {Z} _{2}$

Folgendes Gleichungssystem ist gegeben:

 ${\begin{alignedat}{1}3\cdot &x_{1}\ +\ &x_{2}\ -\ 2\cdot &x_{3}\ +\ &x_{4}\ =2&\\&x_{1}\ +\ &x_{2}\ -\ &x_{3}\ -\ &x_{4}\ =1&\\5\cdot &x_{1}\ +\ &x_{2}\ -\ 3\cdot &x_{3}\ +\ 3\cdot &x_{4}\ =1&\end{alignedat}}$

Wir stellen das Gleichungssystem mittels erweiterter Matrix auf:

 ${\begin{alignedat}{1}&\left({\begin{array}{cccc|c}3&1&-2&1&2\\1&1&-1&-1&1\\5&1&-3&3&1\end{array}}\right){\begin{array}{l|}\to Z1/3\\\to 3\cdot Z2-Z1\;\\\to -5\cdot Z2\end{array}}\to \left({\begin{array}{cccc|c}1&1/3&-2/3&1/3&2/3\\0&2&-1&-4&1\\0&-4&2&8&-4\end{array}}\right){\begin{array}{l|}\,\\\to Z2/2\\\to +2\cdot Z2\;\end{array}}\to \\&\left({\begin{array}{cccc|c}1&1/3&-2/3&1/3&2/3\\0&1&-1/2&-2&1/2\\0&0&0&0&-2\end{array}}\right){\begin{array}{l|}\,\\\,\\\to Z3/(-2)\;\end{array}}\to \left({\begin{array}{cccc|c}1&1/3&-2/3&1/3&2/3\\0&1&-1/2&-2&1/2\\0&0&0&0&1\end{array}}\right)\end{alignedat}}$

a) In der letzten Zeile müsste der Nullvektor ${\vec {0_{V}}}\in V=\mathbb {R} ^{4}$ durch die lineare Abbildung auf einen anderen Vektor als den Nullvektor ${\vec {0_{W}}}\in \mathbb {R} ^{3}$ abgebildet werden, was nicht möglich ist. Der Nullvektor ${\vec {0_{V}}}$ wird immer auf den Nullvektor ${\vec {0_{W}}}$ abgebildet. Daher hat dieses Gleichungssystem über dem Körper $K=\mathbb {R}$ keine Lösung: $0\cdot x_{1}+0\cdot x_{2}+0\cdot x_{3}+0\cdot x_{4}=\mathbf {1}$ hat keine Lösung.

b) Über dem Körper $K=\mathbb {Z} _{2}$ müssen wir die Umformungen neu und nur mit Hilfsmittel aus $\mathbb {Z} _{2}$ durchführen. Vorher haben wir z.B. mit ${\frac {1}{3}}$ multipliziert bzw. sogar mit $2$ , was in $\mathbb {Z} _{2}$ einer Multiplikation mit ${\overline {0}}$ entspricht: Diese Operationen sind in $\mathbb {Z} _{2}$ nicht erlaubt. Wir haben nur die beiden Restklassen ${\overline {0}}$ und ${\overline {1}}$ . Daher wird jede ungerade Zahl zu ${\overline {1}}$ und die Null sowie gerade Zahlen zu ${\overline {0}}$ . Das neue Gleichungssystem in $\mathbb {Z} _{2}$ schaut dann folgend aus:

 ${\begin{alignedat}{1}\left({\begin{array}{cccc|c}{\overline {1}}&{\overline {1}}&{\overline {0}}&{\overline {1}}&{\overline {0}}\\{\overline {1}}&{\overline {1}}&{\overline {1}}&{\overline {1}}&{\overline {1}}\\{\overline {1}}&{\overline {1}}&{\overline {1}}&{\overline {1}}&{\overline {1}}\end{array}}\right){\begin{array}{l|}\,\\\to -Z{\overline {1}}\;\\\to -Z2\end{array}}\to \left({\begin{array}{cccc|c}{\overline {1}}&{\overline {1}}&{\overline {0}}&{\overline {1}}&{\overline {0}}\\{\overline {0}}&{\overline {0}}&{\overline {1}}&{\overline {0}}&{\overline {1}}\\{\overline {0}}&{\overline {0}}&{\overline {0}}&{\overline {0}}&{\overline {0}}\end{array}}\right)\end{alignedat}}$

Als Lösungen haben wir schließlich folgende Gleichung:

 $\color {green}x_{3}\in {\overline {1}}$  und  $x_{1}+x_{2}+x_{4}\in {\overline {0}}$

Das ergibt in $\mathbb {Z} _{2}$ folgende vier Lösungen:

 ${\begin{array}{c|c|c|c}x_{1}&x_{2}&\color {green}x_{3}&x_{4}&\mathbf {x_{1}+x_{2}+x_{4}} \\\hline {\overline {0}}&{\overline {0}}&\color {green}{\overline {1}}&{\overline {0}}&\mathbf {\overline {0}} \\{\overline {0}}&{\overline {1}}&\color {green}{\overline {1}}&{\overline {1}}&\mathbf {\overline {0}} \\{\overline {1}}&{\overline {0}}&\color {green}{\overline {1}}&{\overline {1}}&\mathbf {\overline {0}} \\{\overline {1}}&{\overline {1}}&\color {green}{\overline {1}}&{\overline {0}}&\mathbf {\overline {0}} \end{array}}$

$\qquad \qquad \blacksquare$

Links[Bearbeiten | Quelltext bearbeiten]

Foren:

siehe Diskussion Informatik WS07 Beispiel 397 und WS07 Beispiel 397 und 401

Wikipedia:

Ähnliche Beispiele: