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

Bestimmen Sie mit dem Gaußschen Eliminationsverfahren die Lösung des Gleichungssystems über dem Körper $K$.

a) $K=\mathbb {Q} \quad$ \quadb) $K=\mathbb {Z} _{11}$

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

Dieses Beispiel hat noch keinen Lösungsvorschlag. Um einen zu erstellen, kopiere folgende Zeilen, bearbeite die Seite und aktualisiere den status=unsolved Mögliche status=... Werte stehen hier: Vorlage:Beispiel

== Lösungsvorschlag von ~~~ ==
--~~~~

Siehe auch Hilfe:Formeln und Hilfe:Beispielseiten.

Hilfreiches von Har203

Gaußsche 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. 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

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

Folgendes Gleichungssystem ist gegeben:

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

Wir stellen das Gleichungssystem mittels erweiterter Matrix auf:

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

a) In der letzten Zeile haben wir $x_{3}=1\in \mathbb {Q}$, in der zweiten Zeile erhalten wir $x_{2}-8/15=7/15\implies x_{2}=1\in \mathbb {Q}$ und aus der ersten Zeie erhalten wir $x_{1}+5/2-1=5/2\implies x_{1}=x_{3}=1\in \mathbb {Q}$. D.h. die eindeutige Lösung in $\mathbb {Q}$ ist $x_{1}=x_{2}=x_{3}=1$.

b) Über dem Körper $K=\mathbb {Z} _{11}$ müssen wir die Umformungen neu und nur mit Hilfsmittel aus $\mathbb {Z} _{11}$ durchführen. Wir haben jetzt nur die Restklassen ${\overline {0}}$ bis ${\overline {10}}$. D.h. wir werden alle negativen Zahlen durch die positive Restklasse ersetzen (mit $11$ addieren). Das Gleichungssystem in $\mathbb {Z} _{11}$ schaut folgend aus

${\begin{alignedat}{1}\left({\begin{array}{ccc|c}2&5&9&5\\3&0&1&4\\0&10&2&1\end{array}}\right){\begin{array}{l|}\to {\overline {6}}\cdot Z1\;\\\to +{\overline {4}}\cdot Z1\;\\\,\end{array}}\to \left({\begin{array}{ccc|c}1&\color {red}8&10&8\\0&9&4&2\\0&\color {red}10&2&1\end{array}}\right){\begin{array}{l|}\to +{\overline {8}}\cdot Z3\;\\\to {\overline {5}}\cdot Z2\;\\\to {\overline {10}}\cdot Z3\;\end{array}}\to \left({\begin{array}{ccc|c}1&0&4&5\\0&1&9&10\\0&1&9&10\end{array}}\right){\begin{array}{l|}\,\\\,\\\to +{\overline {2}}\cdot Z2\;\end{array}}\to \left({\begin{array}{ccc|c}1&0&4&5\\0&1&9&10\\0&0&0&0\end{array}}\right)\end{alignedat}}$

Erklärung zum Schritt 2:

• 2.Spalte, Zeile 1 und Zeile 3: Wir wollen in der ersten Zeile eine ${\overline {0}}$ erzeugen. D.h. wir müssen zu $\color {red}{\overline {8}}$ in der ersten Zeile ${\overline {3}}$ addieren. Diese ${\overline {3}}$ müssen wir als Vielfaches von $\color {red}{\overline {10}}$ in der dritten Zeile erzeugen. Da $11$ eine Primzahl ist, können wir in jeden Fall ${\overline {10}}$ sooft multiplizieren, dass wir die Restklasse ${\overline {3}}$ erhalten: $10\cdot n=11\cdot m+{\overline {3}}\quad \mid +{\overline {8}}\implies 10\cdot n+{\overline {8}}=11\cdot m\implies m=8,\,n=8\implies \color {red}{\overline {8}}\color {black}+{\overline {3}}\equiv \color {red}{\overline {8}}\color {black}+8\cdot 10{\bmod {11}}\equiv \color {red}{\overline {8}}\color {black}+80{\bmod {11}}\equiv \color {red}{\overline {8}}\color {black}+7\cdot 11+{\overline {3}}{\bmod {11}}\equiv \color {red}{\overline {8}}\color {black}+{\overline {3}}{\bmod {11}}\equiv {\overline {0}}{\bmod {11}}$

D.h. unsere Lösungsmatrix schaut folgend aus:

$A^{*}=\left({\begin{array}{ccc|c}1&0&4&5\\0&1&9&10\\0&0&0&0\end{array}}\right)$

Unser Lösungsraum ist für $x_{2}$ und $x_{3}$ gegeben durch $x_{2}+9\cdot x_{3}=10$. Für $x_{1}$ gilt die Gleichung $x_{1}=5-4\cdot x_{3}$.

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

${\begin{array}{|c|c|c|c|c|c|c|}x_{2}&x_{3}&9\cdot x_{3}&{\overline {RK}}(9\cdot x_{3})&4\cdot x_{3}&{\overline {RK}}(4\cdot x_{3})&x_{1}=5-4\cdot x_{3}\\\hline {\overline {0}}&{\overline {6}}&{\overline {54}}&{\overline {10}}&{\overline {24}}&{\overline {2}}&{\overline {3}}\\{\overline {1}}&{\overline {1}}&{\overline {9}}&{\overline {9}}&{\overline {4}}&{\overline {4}}&{\overline {1}}\\{\overline {2}}&{\overline {7}}&{\overline {63}}&{\overline {8}}&{\overline {28}}&{\overline {6}}&{\overline {10}}\\{\overline {3}}&{\overline {2}}&{\overline {18}}&{\overline {7}}&{\overline {8}}&{\overline {8}}&{\overline {8}}\\{\overline {4}}&{\overline {8}}&{\overline {72}}&{\overline {6}}&{\overline {32}}&{\overline {10}}&{\overline {6}}\\{\overline {5}}&{\overline {3}}&{\overline {27}}&{\overline {5}}&{\overline {12}}&{\overline {1}}&{\overline {4}}\\{\overline {6}}&{\overline {9}}&{\overline {81}}&{\overline {4}}&{\overline {36}}&{\overline {3}}&{\overline {2}}\\{\overline {7}}&{\overline {4}}&{\overline {36}}&{\overline {3}}&{\overline {16}}&{\overline {5}}&{\overline {0}}\\{\overline {8}}&{\overline {10}}&{\overline {90}}&{\overline {2}}&{\overline {40}}&{\overline {7}}&{\overline {9}}\\{\overline {9}}&{\overline {5}}&{\overline {45}}&{\overline {1}}&{\overline {20}}&{\overline {9}}&{\overline {7}}\\{\overline {10}}&{\overline {0}}&{\overline {0}}&{\overline {0}}&{\overline {0}}&{\overline {0}}&{\overline {5}}\end{array}}$ 

$\qquad \qquad \blacksquare$