Lösungsraum Trick

Einstieg

Viele Probleme lassen sich in der linearen Algebra auf das Lösen lineare Gleichungssysteme zurückführen. Dieser Trick funktioniert nur für lösbare lineare Gleichungssysteme in Treppenform und erlaubt es, einen Lösungsraum schnell zu bestimmen.

Als Erstes stellen wir das Gleichungssystem in einer Koeffizientenmatrix da. Falls das Gleichungssystem mehr unbekannte als Gleichungen besitzt, fügen wir entsprechend viele Nullzeilen ein. Wir verwenden solange den Gauß-Jordan-Algorithmus, bis die Koeffizientenmatrix die Treppenform besitzt d.h :

  • Das jeweils erste Element einer Zeile von M\mathcal{M} ist eine 11

  • Alle Elemente über und unter der Diagonal 11 ist 00

Außerdem muss gefodert werden. Das die jeweils ersten Elemente einer Zeile auf der Diagonale stehen.

Versucht man diesen Trick auf eine Matrix anzuwenden, welche nicht diese Gestalt besitzt. So liefert das Verfahren falsche Ergebnisse.

Verfahren

Besitzt nun die Matrix die Gestalt von M,\mathcal{M}, so geht man wie folgt vor:

  • Jede Diagonal 0 wird mit 1-1 ersetzt

  • Jede korrospondierende Spalte von einer ersetzen Diagonal 0, ist automatisch ein Lösungsvektor

  • Der Vektor bb \in Kn\mathbb{K}^n ist der Lösungsvektor

Beispiel

Betrachten wir folgendes Gleichungssystem

Wir repräsentieren das Gleichungssystem in einer Matrix. Außerdem muss die Matrix mit Nullzeilen aufgeführt werden, da es mehr Unbekannte als Gleichungen gibt. Ohne den Vektor bb besitzt die Matrix nun eine Blockgestalt.

Die Matrix kann nun in Gauß Normalform gebracht werden. Durch Addieren der ersten Zeile auf die zweite und die zweite anschließend auf die erste, erhalten wie die gewünschte Gestalt.

Nun ersetzen wir alle Diagonalnullen. In unserem Beispiel ersetzen wir also die Diagonalnull in Spalte 3 und 4 Spalte mit 1-1.

Jetzt können wir die Lösungen ablesen. Die Spalte 3 und 4 beinhaltet unsere Lösungsvektoren und der Vektor bb ist der entsprechende Lösungsvektor. Damit erhalten wir dem Lösungsraum

Bemerkung

Der Trick funktioniert auch für nicht homogene Gleichungssysteme. Der Lösungsvektor muss aber zwingend in den Lösungsraum mit einfließen.

Für homogene Gleichungssysteme lässt sich das Verfahren ganz einfach beweisen. Dazu betrachtet man den Spaltenindex  si\ s_i der die jeweilige Spalte des ersten, zweiten und n-ten Pivotelement angibt. Im vorherigen Beispiel galt si=i,s_i=i, aber natürlich können die Spalten vertauscht sein. Dann kann man durch nachrechnen prüfen, dass die Fundamentallösung FjF^j tatsächlich eine gültige Lösung für das Gleichungssystem Ax = 0 ist,Ax\ =\ 0\ ist, wobei jj definiert ist als j   {qi, ... , qr}   {s1, ... , sr}j\ \ \in\ \left\{q_{i,\ ...\ ,\ q_r}\right\}\ \setminus\ \ \left\{s_{1,\ ...\ ,\ s_r}\right\}, also genau die Spalten die frei belegt werden können. Dann lässt sich die Fundamentallösung schreiben als Fj = ej i=1rtij esiF^j\ =\ e_{j\ }-\sum_{i=1}^rt_{ij}\ e_{s_i}. Nun muss man prüfen ob T Fj = 0T\ F_j\ =\ 0. Durch einsetzen folgt: T  Fj  = T T\ \cdot\ F_{j\ }\ =\ T\ \cdotej  e_j\ -\ i=1rtij   T  esi =k=1rtkj  ej   i=1rtij ei =0  \sum_{i=1}^rt_{ij}\ \ \cdot\ T\ \cdot\ e_{s_i}\ =\sum_{k=1}^rt_{kj}\ \ \cdot e_{j\ }\ -\ \sum_{i=1}^rt_{ij}\ \cdot e_i\ =0\ \ und somit folgt die Behauptung.


Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0.Was bedeutet das?