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 hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Hilfreiches[Bearbeiten | Quelltext bearbeiten]

LGS-Äquivalenzumformungen

LGS-Äquivalenzumformungen[Bearbeiten | Quelltext bearbeiten]

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.

a) 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

b) 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]

Gaußsche Eliminationsverfahren[Bearbeiten | Quelltext bearbeiten]

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

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}}$