Gauss-Elimination

Die Gauss-Elimination ist ein Algorithmus zum Lösen von $Ax=b$ mit quadratischen Matrizen $A\in {\mathbb{R}}^{m\times m}$

1. In einem ersten Schritt wird das Gleichungssystem $Ax=b$ in ein System $Ux=c$ umgewandelt. Dieses neue Gleichungssystem hat die gleichen Lösungen wie das alte, hat aber ein “hübsches” $U$ in Form einer oberen Dreiecksmatrix.
2. Das Gleichungssystem $Ux=c$ kann leicht durch Rückwärtseinsetzen gelöst werden

$$\underset{U}{\underbrace{\left[\begin{array}{ccc}2& 3& 4\\ 0& 5& 6\\ 0& 0& 7\end{array}\right]}}\cdot \underset{x}{\underbrace{\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)}}=\underset{c}{\underbrace{\left(\begin{array}{c}19\\ 17\\ 14\end{array}\right)}}$$

Die obige Matrix-Vektor Gleichung kann auch als das folgende Gleichungssystem geschrieben werden:

$$\begin{array}{rlrlrlrl}1.& 2x_1& +& 3x_2& +& 4x_3& =& 19\\ 2.& & & 5x_2& +& 6x_3& =& 17\\ 3.& & & & & 7x_3& =& 14\end{array}$$

Das dritte Gleichungssystem besteht noch aus einer unbekannten und lässt sich daher einfach mit dem Ergebnis $x_3=2$ lösen. Dieses Ergebnis kann dann in die zweite Gleichung eingesetzt werden.

$$\begin{array}{rlrlrlrl}1.& 2x_1& +& 3x_2& +& 8& =& 19\\ 2.& & & 5x_2& +& 12& =& 17\end{array}$$

Nun gibt es auch im zweiten Gleichungssystem noch eine unbekannte und auch dieses Gleichungssystem kann gelöst werden: $x_2=1$. Wenn dieser Wert nun noch in die erste Gleichung eingesetzt wird, kommt man auf die folgende Gleichung:

$$\begin{array}{rlrlrl}1.& 2x_1& +& 11& =& 19\end{array}$$

Löst man diese Gleichung auf erhält man $x_1=4$. Somit hat man das Gleichungssystem gelöst und die folgenden Lösungen erhalten:
$x_1=4x_2=1x_3=2$
Im Fall einer $m\times m$ Gleichung $i=m,m-1,\dots 1$ :
${\sum }_{j=i}^m{u}_{ij}\cdot x_j=c_i$
oder

$$x_i=\frac{c_i-{\sum }_{j=i+1}^m{u}_{ij}\cdot x_j}{u_{ii}}$$

Hier wird sich zunutze gemacht, dass die bisherigen $x_m$, $x_{m-1}$ bis hin zu $x_{i+1}$ schon bekannt sind und verwendet werden können, um das aktuell gesuchte $x_i$ zu berechnen.
Wichtig ist hier noch, dass $u_{ii}\ne 0$ sein muss, da ansonsten eine Division mit $0$ stattfinden würde. Diese Einsicht ist gleichbedeutend mit der Aussage, dass es in der Diagonalen der Matrix keinen Eintrag mit Wert $0$ geben darf.

Elimination

Wenn $A$ keine obere Dreiecksmatrix kann das obige Verfahren noch nicht angewendet werden. $A$ muss also zuerst in die Form einer oberen Dreiecksmatrix gebracht werden. Somit wird also die Transformation von $Ax=b\to Ux=c$ durchgeführt.

$$\underset{A}{\underbrace{\left[\begin{array}{ccc}2& 3& 4\\ 4& 11& 14\\ 2& 8& 17\end{array}\right]}}\cdot \underset{x}{\underbrace{\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)}}=\underset{b}{\underbrace{\left(\begin{array}{c}19\\ 55\\ 50\end{array}\right)}}$$

Als erstes soll die $4$ eliminiert werden. Um das zu erreichen muss die erste Gleichung zwei Mal von der zweiten abgezogen werden.

\begin{array}{r@{\quad}rcrcrcr} (\text{Gleichung 2}): & 4x_1 &+& 11x_2 &+& 14x_3 &=& 55\\ -2(\text{Gleichung 1}): & 4x_1 &+& 6x_2 &+& 8x_3 &=& 38\\ \hline & & & 5x_2 &+& 6x_3 &=& 17 \end{array}

Dies wird nun als die Gleichung $A^{\prime }x=b^{\prime }$ geschrieben. Als Matrix-Vektor Gleichung sieht das folgendermassen aus:

$$\left[\begin{array}{ccc}2& 3& 4\\ 0& 5& 6\\ 2& 8& 17\end{array}\right]\cdot \left(\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right)=\left(\begin{array}{c}19\\ 17\\ 50\end{array}\right)$$

Das Verfahren, welches angewendet wurde, um die $4$ zu entfernen nennt sich Zeilensubtraktion. Eine Zeilensubtraktion ist eigentlich nichts anderes, als eine Matrixtransformation, welche auf alle Spalten von $A$ sowie auf den Vektor $b$ angewandt wird:

$$T_{E_{21}}\left(\left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right)\right)=\left(\begin{array}{c}{v}_1\\ v_2-2v_1\\ v_3\end{array}\right)=\underset{E_{21}}{\underbrace{\left[\begin{array}{ccc}1& 0& 0\\ -2& 1& 0\\ 0& 0& 1\end{array}\right]}}\left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right)$$

Wobei $E_{21}$ die Eliminationsmatrix ist, welche dafür sorgt, dass die $4$ verschwindet.
Jetzt gilt es noch zu zeigen, dass durch diese Umformungen die Lösungen auch erhalten bleiben.
Dazu lohnt es sich anzusehen, wie die Gleichung $A^{\prime }x=b^{\prime }$ definiert ist:

$A^{\prime }x=b^{\prime }:$ $A^{\prime }=E_{21}A$, $b^{\prime }=E_{21}b$
Wobei $E_{21}$ heisst: Ziehe Gleichung 1 zwei Mal von Gleichung 2 ab.

Da es sich hier um die Multiplikation mit einer Matrix handelt kann die Operation auch umgekehrt werden:
$A=E_{21}^{-1}{A}^{\prime }$ , $b=E_{21}^{-1}{b}^{\prime }$

Wobei $E_{21}^{-1}$ durch die Matrix $E_{21}^{-1}=\left[\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ 0& 0& 1\end{array}\right]$
dargestellt wird. Man kann $E_{21}^{-1}$ also als addiere Gleichung 1 zwei Mal zu Gleichung 2 interpretieren.

Aber wieso haben $Ax=b$ und $A^{\prime }x=b^{\prime }$ jetzt die gleichen Lösungen?

• Wenn $Ax=b$ gilt, dann gilt auch: $A^{\prime }x=E_{21}Ax=E_{21}b=b^{\prime }$
• Wenn $A^{\prime }x=b^{\prime }$ gilt, dann gilt auch $Ax=E_{21}^{-1}{A}^{\prime }x=E_{21}^{-1}{b}^{\prime }=b$
  Daraus folgt nun also, dass $Ax=b$ und $A^{\prime }x=b^{\prime }$ die gleichen Lösungen haben.

Um das System in eine schöne obere Dreiecksmatrix zu verwandeln muss man nun also alle Zahlen, welche in der obigen Matrix rot markiert sind eliminieren.
Dabei geht man so vor, dass man zuerst die erste Gleichung verwendet, um in jeder Zeile die Zahl der ersten Spalte zu entfernen, dann geht man weiter und verwendet die zweite Gleichung, um von der dritten Zeile an jede Zahl in der zweiten Spalte zu eliminieren. Diesen Prozess führt man solange durch, bis man den Zustand der oberen Dreiecksmatrix hergestellt hat.

Da die Schritte der Elimination $E_{21}$, $E_{31}$ und $E_{32}$ eigentlich nur Matrixmultiplikationen sind, welche nach und nach auf $A$ angewendet werden können, kann der gesamte Eliminationsprozess auch als eine einzige Eliminationsmatrix geschrieben werden, welcher dann das Produkt der einzelnen Eliminationsmatrizen ist:

$$E_{32}{E}_{31}{E}_{21}=E_{gesamt}$$ $$E_{gesamt}A=U$$

Somit kommt man dann auf das schöne $U$ von weiter oben, welches verwendet wird, um ganz einfach auf die Resultate des linearen Gleichungssystems zu kommen.