Gauß Eliminationsverfahren

Das Gaußsche Eliminationsverfahren ist ein Verfahren zur Lösung von linearen Gleichungssystemen (LGS). Dieses Verfahren beruht darauf, dass elementare Umformungen das Gleichungssystem zwar ändern, aber die Lösung trotzdem erhalten bleibt. Durch die Umformungen wird das Gleichungssystem in ein einfacher zu lösendes LGS überführt.

Zu den elementaren Umformungen zählen:

• Addition/Subtraktion einer Gleichung zu einer anderen
• Multiplikation einer Gleichung mit einem Skalar $\lambda$ ungleich null
• Vertauschen zweier Zeilen
• Addition/Subtraktion des $\lambda$-Fachen einer Zeile mit den $\mu$-Fachen einer Spalte.

Lineares Gleichungssystem

Ein lineares Gleichungssystem ist ein System von $m$ linearen Gleichungen mit $n$ Variablen $x_1, x_2, ..., x_n$:

$a_{11}x_1 + a_{12}x_2 + ... + a_{1n}x_n = b_1$

$a_{21}x_1 + a_{22}x_2 + ... + a_{2n}x_n = b_2$

$...$

$a_{m1}x_1 + a_{m2}x_2 + ... + a_{mn}x_n = b_n$

In Matrixschreibweise:

$\begin{pmatrix} a_{11} & a_{12} & ... & a_{1n} \\ a_{21} & a_{22} & ... & a_{2n} \\ . \\ . \\ . \\ a_{m1} & a_{m2} & ... & a_{mn} \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \\ . \\ . \\ . \\ x_n \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \\ . \\ . \\ . \\ b_n \end{pmatrix}$

Vorgehensweise des Gaußschen Eliminationsverfahrens

In einer Matrix $A$ sucht man die Spalte aus, welche möglichst viele Nullen aufweist und mit einer möglichst einfachen Zahl $\neq 0$. Mit Hilfe dieser Spalte wird versucht, mittels der elementaren Umformungen Nullen zu erzeugen, sodass das Gleichungssystem gelöst werden kann. 

Beispiel: Gauß Eliminationsverfahren

Gegeben sei: $\begin{pmatrix} -1 & 4 & 2 \\ 2 & 8 & 4 \\ 0 & 3 & 1 \\ 3 & 5 & 4 \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 4 \\ 8 \\ 3 \\ 5 \end{pmatrix}$

Gauß Eliminationsverfahren

Die letzte Gleichung ist für alle $x_i = 0$ und wird weggelassen. Das ursprüngliche LGS ist nun durch die blau markierten Gleichungen ersetzt:

(1)  $-x_1 + 4x_2 + 2x_3 = 4$

(2)  $          3x_2 + x_3 = 3$

(3)  $         -8x_2          = -8$

Lösung des LGS:

Dieses LGS kann nun aufgelöst werden (rückwärts):

(3) $x_2 = 1$

(2) $x_3 = 3 - 3x_2$

(1) $x_1 = 4x_2 + 2x_3 - 4$

Einsetzen ergibt dann:

$x_3 = 3 - 3 \cdot 1 = 0$

$x_1 = 4 \cdot 1 + 2 \cdot 0  - 4 = 0$

Dieses LGS hat die eindeutige Lösung: $(0, 1, 0)$