Das Eliminationsverfahren

Mit dem folgenden Verfahren können wir ein beliebiges System Ax = b auf Lösbarkeit überprüfen und im positiven Fall seine Lösung effektiv angeben:

Gauß-Jordan-Eliminationsverfahren

Wir überführen A durch die elementaren Zeilenoperationen (Vervielfachung einer Zeile, Addition eines Vielfachen einer Zeile zu einer anderen) und Permutation der Spalten in reduzierte Zeilenstufenform mit diagonalen Pivots. Dabei führen wir die Zeilenoperationen zugleich auch für die rechte Seite b durch. Wir erhalten so ein System der Form

(◇) $( \begin{matrix} E_{r} & {\bar{a}}_{r + 1} & … & {\bar{a}}_{n} \\ 0 & 0 \end{matrix} )$ x = $( \begin{matrix} \bar{b} \\ b * \end{matrix} )$

mit a_{r +1}, …, a_n, b  ∈  ℝ^r, b*  ∈  ℝ^m − r. Ist b* ≠ 0, so geben wir „nicht lösbar“ als Ergebnis aus. Andernfalls bilden wir den affinen Unterraum

U = $( \begin{matrix} \bar{b} \\ 0 \end{matrix} )$ + span( $( \begin{matrix} - {\bar{a}}_{r + 1} \\ e_{1} \end{matrix} )$ , …, $( \begin{matrix} - {\bar{a}}_{n} \\ e_{n - r} \end{matrix} )$ )

mit den Basisvektoren e₁, …, e_n − r des ℝ^n − r. Abschließend ordnen wir die Koordinaten entsprechend den durchgeführten Spaltenpermutationen um. Der so entstehende affine Unterraum L ist das Ergebnis der Berechnung.

Das Verfahren lässt sich wie das Invertierungsverfahren von Matrizen durch „Ausräumen der Matrix A“ beschreiben. Um die Pivots nach links zu bringen, sind im Allgemeinen Spaltenpermutationen nötig. Sie entsprechen einer Umordnung der Variablen, die wir am Ende korrigieren können.

Das Verfahren ist korrekt, d. h. L ist die Lösung des Systems Ax = b: Die elementaren Zeilenoperationen verändern den Lösungsraum nicht und die Spaltenoperationen vertauschen nur die Variablen. Dass der affine Unterraum U die Lösungsmenge von (◇) ist, lässt sich direkt ablesen. Der Vektor (b, 0, …, 0) ist eine spezielle Lösung, die Vektoren des Spans lösen das homogene System.

Bemerkung

(1)	Wir formen A um, führen aber alle Operationen auch für b durch. Wir arbeiten also mit der sog. erweiterten Koeffizientenmatrix (A; b) mit der zusätzlichen Spalte b. Diese Matrix notieren wir auch als (A \| b).

(2)	Die Dimension des Lösungsraums ist n − r, also die Anzahl der Spalten rechts der Pivots.

(3)	Die erzeugten m − r Nullzeilen in (◇) spielen für die Lösungsmenge keine Rolle. Wichtig ist lediglich, dass auch der entsprechende untere Teil von b gleich 0 geworden ist. Andernfalls ist das System unlösbar.