Gaußsches Eliminierungsverfahren (Gauß-Algorithmus)

Unter einer äquivalenten Umformung versteht man jede Umformung, welche die Lösungsmenge des Gleichungssystems nicht verändert. Für äquivalente Umformungen gelten die folgenden Regeln:

• Eine Gleichung kann mit einer reellen Zahl $k\ne 0$ multipliziert werden.
• Gleichungen können untereinander vertauscht werden.
• Zu einer Gleichung kann das Vielfache einer anderen Gleichung addiert werden.

Im Folgenden wird das gaußsche Eliminierungsverfahren am Beispiel eines linearen Gleichungssystems mit drei Gleichungen und drei Variablen demonstriert.

Es ist das folgende Gleichungssystem zu lösen:

$\begin{array}{cc}(I)& 2x_1-x_2+x_3=8\\ (II)& x_1+2x_2+2x_3=6\\ (III)& 4x_1-2x_2-3x_3=1\end{array}$

Vertauschen der Gleichungen (I) und (II) ergibt:

$\begin{array}{cc}(I\text{'})& x_1+2x_2+2x_3=6\\ (II\text{'})& 2x_1-x_2+x_3=8\\ (III)& 4x_1-2x_2-3x_3=1\end{array}$

Die Gleichung $\left(I\text{'}\right)$ ist die Eliminationszeile und bleibt in den weiteren Umformungen unverändert.

Diese im Folgenden mit (E) bezeichnete Gleichung wird nun mit einem Faktor multipliziert, der sich als negativer Quotient der Koeffizienten der zu eliminierenden Variablen der Gleichungen $\left(II\text{'}\right)bzw.\left(III\text{'}\right)$ mit der Gleichung (E) ergibt (in diesem Beispiel ist $k=-2bzw.k=-4$):

$\begin{array}{ccc}(E)& x_1+2x_2+2x_3=6& \\ (II\text{'})& 2x_1-x_2+x_3=8& |\left(-2\right)(E)+(II\text{'})\\ (III\text{'})& 4x_1-2x_2-3x_3=1& |\left(-4\right)(E)+(III\text{'})\end{array}$

Damit ist die Unbekannte $x_1$ eliminiert, denn es ergibt sich:

$\begin{array}{ccc}(E)& x_1+2x_2+2x_3=6& \\ (II\text{'}\text{'})& -5x_2+3x_3=-4& \\ (III\text{'}\text{'})& -10x_2-11x_3=-23& \end{array}$

Jetzt wird $\left(II\text{'}\text{'}\right)$ zur Eliminationszeile $(E_2)$ und der Vorgang wird wiederholt. Die Gleichung $(E_2)$ wird mit dem Faktor $k=-2\left(=-\frac{-10}{-5}\right)$ multipliziert und zu $\left(III\text{'}\text{'}\right)$ addiert:

$\begin{array}{ccc}& x_1+2x_2+2x_3=6& \\ (E_2)& -5x_2+3x_3=-4& \\ (III\text{'})& -10x_2-11x_3=-23& |\left(-2\right)(E_2)+(III\text{'})\end{array}$

Man erhält ein neues Gleichungssystem, dessen dritte Gleichung eine Gleichung mit nur noch einer Variablen ist:

$\begin{array}{ccc}& x_1+2x_2+2x_3=6& \\ (E_2)& -5x_2+3x_3=-4& \\ (III\text{'}\text{'}\text{'})& -5x_3=-15& \end{array}$

Hieraus wird $x_3=3$ errechnet.
Einsetzen in $(E_2)$ liefert $x_2=-1$, Einsetzen in (E) $x_1=2$.
Probe durch Einsetzen der Lösungen in alle Gleichungen (Ausgangsform):

$\begin{array}{ccc}(I)& 2\cdot 2-\left(-1\right)+3=8& (wahreAussage)\\ (II)& 2+2\cdot \left(-1\right)+2\cdot 3=6& (wahreAussage)\\ (III)& 4\cdot 2-2\cdot \left(-1\right)-3\cdot 3=1& (wahreAussage)\end{array}$

Das am obigen Beispiel demonstrierte Verfahren lässt sich auf lineare Gleichungssysteme von n Gleichungen mit n Variablen verallgemeinern.
Es sei folgendes Gleichungssystem gegeben:

$\begin{array}{l}{a}_{11}{x}_1+a_{12}{x}_2+a_{13}{x}_3+\mathrm{...}+a_{1n}{x}_n=b_1\\ a_{21}{x}_1+a_{22}{x}_2+a_{23}{x}_3+\mathrm{...}+a_{2n}{x}_n=b_2\\ a_{31}{x}_1+a_{32}{x}_2+a_{33}{x}_3+\mathrm{...}+a_{3n}{x}_n=b_3\\ \mathrm{...}\\ a_{n1}{x}_1+a_{n2}{x}_2+a_{n3}{x}_3+\mathrm{...}+a_{nn}{x}_n=b_n\end{array}$

Durch entsprechende äquivalente Umformungen wird dieses Gleichungssystem in die folgende (so genannte) Dreiecksform gebracht:

$\begin{array}{l}{a}_{11}{x}_1+a_{12}{x}_2+a_{13}{x}_3+\mathrm{...}+a_{1n}{x}_n=b_1\\ a{\text{'}}_{22}{x}_2+a{\text{'}}_{23}{x}_3+\mathrm{...}+a{\text{'}}_{2n}{x}_n=b{\text{'}}_2\\ a{\text{'}}_{33}{x}_3+\mathrm{...}+a{\text{'}}_{3n}{x}_n=b{\text{'}}_3\\ \mathrm{...}\\ a{\text{'}}_{nn}{x}_n=b{\text{'}}_n\end{array}$

Hieraus erhält man $x_n=\frac{b{\text{'}}_n}{a{\text{'}}_{nn}},$ und sukzessive lassen sich $x_{n-1},x_{n-2},\mathrm{...,}{x}_1$ berechnen.

Anmerkung: Die Umformung des Gleichungssystems in diese Form (bzw. der Koeffizientenmatrix zu einer oberen Dreiecksmatrix) setzt voraus, dass die Determinante der Koeffizientenmatrix nicht verschwindet. Ist dies nicht erfüllt, wird die Koeffizientenmatrix in eine Trapezform überführt.