<< Matrizen02 >>

Lineare Gleichungssysteme und Matrizen: Gaußverfahren

Gleichungssysteme lassen sich mit Hilfe von Matrizen und Vektoren sehr effizient aufschreiben und bearbeiten. Betrachte z.B. das folgende Gleichungssystem: \[ \begin{eqnarray} 3x_1=2580-(4x_2+5x_3) \\ 3x_2+3x_1=1770-2x_3 \\ 5x_1+3x_3+2x_2=2080 \end{eqnarray} \]

Ordnet man die Variablen und schreibt sie übersichtlich untereinander, so erhält man: \[ \begin{eqnarray} 3x_1+4x_2+5x_3= 2580 \\ 3x_1+3x_2+2x_3=1770 \\ 5x_1+2x_2+3x_3=2080 \end{eqnarray} \] Schreibt man nun die Koeffizienten in eine Matrix A, die Variablen in einen Vektor \vec{x} und die Zahlen auf der rechten Seite in einen Vektor \vec{b}, so schreibt sich das Gleichungssystem als \[ A\cdot\vec{x}=\vec{b} \] wobei \[ A=\left(\begin{array}{ccc}3&4&5\\3&3&2\\5&2&3\end{array}\right)\quad ,\quad \vec{x}=\left(\begin{array}{c}x_1\\x_2\\x_3\end{array}\right)\quad ,\quad \vec{b}=\left(\begin{array}{c}2580\\1770\\2080\end{array}\right) \]

Auf diese Weise kann man jedes System linearer Gleichungen mit Hilfe einer Matrix schreiben. Die Spaltenzahl der Matrix ist die Zahl der Variablen und die Zeilenanzahl ist die Zahl der Gleichungen.

Zu allgemeinen Fragen der Lösbarkeit von Gleichungssystemen muss ein eigenes Kapitel eingeplant werden. Wir verwenden zur Lösung den Gaußalgorithmus, in dessen Verlauf man feststellt, ob die Lösungsmenge leer ist, genau ein Element oder unendlich viele Elemente enthält.

Der Gaußalgorithmus

Um Gleichungssysteme zu lösen verwendet man verschiedene aus der Mittelstufe bekannte Äquivalenzumformungen:

  1. Multiplikation einer Zeile mit einem Faktor \neq 0
  2. Addition von Zeilen
  3. Vertauschen von Zeilen

Das Gaußverfahren ist ein Algorithmus, der diese Äquivalenzumformungen systematisch zum Lösen von linearen Gleichungssystemen (LGS) nutzt. Er eignet sich gut zur Implementierung in ein Computerprogramm.

Zuerst fasst man die Matrix A und den Vektor \vec{b} zur sogenannten erweiterten Koeffizientenmatrix zusammen:

\[ \left(\begin{array}{ccccc}3&4&5& |& 2580\\3&3&2&|&1770\\5&2&3&|&2080\end{array}\right) \]

Man multipliziert nun die erste Zeile so mit einem geeigneten Faktor, dass der erste Eintrag zu 1 wird. Gegebenenfalls muss man Zeilen tauschen (man könnte auch Spalten tauschen, würde dadurch aber die Reihenfolge der Variablen ändern!). Dann addiert man geeignete Vielfache dieser neuen ersten Zeile so zu den restlichen Zeilen, dass jeder erste Eintrag 0 wird. Ziel ist eine Matrix der Form: \[ \left(\begin{array}{cccccc}1&*&\dots& *& |& * \\0&*&\dots& *& |& * \\ \vdots &&\vdots &&|&\vdots \\0&*&\dots& *& |& * \end{array}\right) \] In unserem Beispiel sieht das so aus: \[ \left(\begin{array}{ccccc}3&4&5& |& 2580\\3&3&2&|&1770\\5&2&3&|&2080\end{array}\right) \longrightarrow \left(\begin{array}{ccccc}1&\frac{4}{3}&\frac{5}{3}& |& 860\\3&3&2&|&1770\\5&2&3&|&2080\end{array}\right) \longrightarrow \left(\begin{array}{ccccc}1&\frac{4}{3}&\frac{5}{3}& |& 860\\0&-1&-3&|&-810\\0&-\frac{14}{3}&-\frac{16}{3}&|&-2220\end{array}\right) \] Durch das (gedankliche) Streichen der ersten Zeile und ersten Spalte erhält man eine neue Matrix, auf die man den gleichen Schritt wieder anwendet. Dies führt man so lange durch bis man schließlich eine obere Dreicksmatrix erhält, die nur Einsen in der Diagonalen hat: \[ \left(\begin{array}{cccccc}1&*&\dots& *& |& * \\0&1&\ddots& \vdots& |& * \\ \vdots &\ddots&\ddots &*&|&\vdots \\0&\dots&0& 1& |& * \end{array}\right) \] Für unser Beispiel durchgeführt erhält man so: \[ \left(\begin{array}{ccccc}1&\frac{4}{3}&\frac{5}{3}& |& 860\\0&-1&-3&|&-810\\0&-\frac{14}{3}&-\frac{16}{3}&|&-2220\end{array}\right) \longrightarrow \left(\begin{array}{ccccc}1&\frac{4}{3}&\frac{5}{3}& |& 860\\0&1&3&|&810\\0&0&\frac{26}{3}&|&1560\end{array}\right) \longrightarrow \left(\begin{array}{ccccc}1&\frac{4}{3}&\frac{5}{3}& |& 860\\0&1&3&|&810\\0&0&1&|&180\end{array}\right) \] Nun nutzt man die letzte Zeile, um in den übrigen Zeilen die letzte Spalte (vor dem Ergebnisvektor, d.h. vor dem Strich!) zu Null zu machen. Da die restlichen Einträge in dieser Zeile 0 sind, wird außer der letzten Spalte nichts beeinflusst. Das Ziel ist eine Matrix der folgenden Gestalt: \[ \left(\begin{array}{cccccc}1&*&\dots& 0& |& * \\0&1&\ddots& \vdots& |& * \\ \vdots &\ddots&\ddots &0&|&\vdots \\0&\dots&0& 1& |& * \end{array}\right) \] In unserem Beispiel sieht das dann so aus: \[ \left(\begin{array}{ccccc}1&\frac{4}{3}&\frac{5}{3}& |& 860\\0&1&3&|&810\\0&0&1&|&180\end{array}\right) \longrightarrow \left(\begin{array}{ccccc}1&\frac{4}{3}&0& |& 560\\0&1&0&|&270\\0&0&1&|&180\end{array}\right) \] Streicht man wieder gedanklich die letzte Zeile, so kann man den letzten Schritt wieder anwenden. Dies führt man so lange durch, bis man eine Matrix erhält, die in der Diagonalen 1 hat und ansonsten nur 0. Rechts ist der Ergebnisvektor. Hier kann man die Lösung des Gleichungssystems ablesen. \[ \left(\begin{array}{cccccc}1&0&\dots& 0& |& * \\0&1&\ddots& \vdots& |& * \\ \vdots &\ddots&\ddots &0&|&\vdots \\0&\dots&0& 1& |& * \end{array}\right) \] In unserem Beispiel ergibt sich: \[ \left(\begin{array}{ccccc}1&\frac{4}{3}&0& |& 560\\0&1&0&|&270\\0&0&1&|&180\end{array}\right)\longrightarrow \left(\begin{array}{ccccc}1&0&0& |& 200\\0&1&0&|&270\\0&0&1&|&180\end{array}\right) \quad\mbox{also} \left(\begin{array}{c}x_1\\x_2\\x_3\end{array}\right)=\left(\begin{array}{c}200\\270\\180\end{array}\right) \]

<< Matrizen02 >>