1.1. Gauss-Eliminationsverfahren

Bevor wir den allgemeinen Fall eines quadratischen LGS wie in Gleichung (1.1) betrachten, wollen wir zwei Spezialfälle diskutieren, in denen sich die Determinante von \(A\) direkt ablesen lässt. Dies bedeutet wiederum, dass man in diesen Fällen direkt eine Aussage über die Lösbarkeit des LGS machen kann. Der einfachste zu betrachtende Fall ist, wenn die Matrix \(A\) eine Diagonalmatrix ist, wenn also gilt \(a_{i,j} = 0\) für alle \(i \neq j\):

\[A \ = \ \begin{pmatrix} a_{1,1} & & 0 \\ & \ddots & \\ 0 & & a_{n,n} \end{pmatrix}.\]

In diesem Fall weiß man, dass

(1.3)\[\operatorname{det}(A) = \prod_{i=1}^n a_{i,i}\]

gilt und somit \(\operatorname{det}(A) \neq 0 \Leftrightarrow a_{i,i} \neq 0\) für alle \(i=1,\ldots,n\), d.h., das LGS in Gleichung (1.1) ist genau dann lösbar, wenn alle Diagonaleinträge der Matrix \(A\) ungleich Null sind. Weiterhin lässt sich eine Lösung \(x \in \mathbb{R}^n\) in diesem Fall sehr einfach bestimmen, nämlich:

(1.4)\[x_i \ = \ \frac{b_i}{a_{i,i}}, \quad \forall i=1,\ldots,n.\]

Da man zur Bestimmung des Lösungsvektors \(x \in \R^n\) in (1.4) nur \(n\) Divisionen benötigt, liegt der Rechenaufwand in \(\mathcal{O}(n)\).

Widmen wir uns nun dem zweiten Fall unserer Diskussion, nämlich wenn die Matrix \(A\) die Gestalt einer rechten, obere Dreiecksmatrix besitzt, d.h. wenn \(a_{ij} = 0\) für alle \(i > j\) gilt:

\[A \ = \ \begin{pmatrix} a_{1,1} & \dots & a_{1,n} \\ 0 & \ddots & \vdots \\ 0 & 0 & a_{n,n} \end{pmatrix} \ =: \ R.\]

Wie im Fall der Diagonalmatrix lässt sich die Determinante hier analog als Produkt der Diagonaleinträge nach Gleichung (1.3) berechnen und es gelten die gleichen Aussagen zur Existenz einer Lösung. Die konkrete Berechnung des Lösungsvektors \(x \in \mathbb{R}^n\) stellt sich jedoch, verglichen mit dem ersten Spezialfall, als etwas schwieriger heraus. Betrachten wir das ursprüngliche LGS in Gleichung (1.1) für den Fall einer rechten, oberen Dreiecksmatrix \(A=R\) so ergeben sich die folgenden gestaffelten Gleichungen

(1.5)\[\begin{aligned} \begin{split} a_{1,1}x_1 + a_{1,2}x_2 + \ldots + a_{1,n-1}x_{n-1} + a_{1,n}x_n & = b_1 \\ a_{2,2}x_2 + \ldots + a_{2,n-1}x_{n-1} + a_{2,n}x_n & = b_2 \\ \vdots & \\ a_{n-1,n-1}x_{n-1} + a_{n-1,n}x_n & = b_{n-1} \\ a_{n,n} x_n & = b_n \end{split} \end{aligned}\]

Für den Fall, dass \(A\) nicht singulär ist, d.h., dass alle Diagonalelemente der Matrix \(A=R\) ungleich Null sind, lässt sich direkt ein Verfahren zur Bestimmung der unbekannten Lösung \(x\in\mathbb{R}^n\) durch Rückwärtseinsetzen angeben. Hierzu beginnt man mit dem letzten Element \(x_n\) des Vektors \(x\) und setzt die Lösung sukzessive in die gestaffelten Gleichungen (1.5) ein. Hieraus ergibt sich das folgende Lösungsverfahren.

Algorithmus 1.1 (Rückwärtseinsetzen)

Wir betrachten das LGS \(Rx = b\) für eine rechte obere Dreiecksmatrix \(R \in \R^{n \times n}\), einen Vektor \(b \in \R^n\) und einen unbekannten Lösungsvektor \(x \in \R^n\). Wenn alle Diagonalelemente \(a_{i,i} \in \R, i = 1,\ldots,n\) ungleich Null sind, so können wir den unbekannten Lösungsvektor sukzessive durch Rückwärtseinsetzen wie folgt berechnen:

(1.6)\[\begin{aligned} \begin{split} x_n \ = & \ b_n / a_{n,n} \\ x_{n-1} \ = & \ (b_{n-1} - a_{n-1,n}x_n) / a_{n-1,n-1} \\ \vdots & \\ x_1 \ = & \ (b_1 - a_{1,2}x_2 - \ldots - a_{1,n}x_n) / a_{1,1} \end{split} \end{aligned}\]

Bemerkung 1.1

In der ersten Gleichung von (1.6) benötigt man eine einzige Division zur Bestimmung von \(x_n\). Mit jeder weiteren Gleichung kommt eine Subtraktion und eine Multiplikation hinzu (wir fassen diese zwei Schritte nach Definition 1.1 hier zu einem FLOP zusammen). Dementsprechend lässt sich der Rechenaufwand für das Rückwärtseinsetzen mit

\[1 + \sum_{i=2}^n i \ = \ \sum_{i=1}^n i \ = \ \frac{n(n+1)}{2} = \frac{n^2}{2} + \frac{n}{2},\]

also in \(\frac{1}2 n^2 + \mathcal{O}(n)\) bzw. in \(\mathcal{O}(n^2)\) angeben.

Sei \(A \in \R^{n \times n}\) nun im Folgenden eine beliebige nichtsinguläre Matrix. Wir versuchen im Folgenden mit Hilfe des Gauss’schen Eliminationsverfahren durch geschickte Rechenoperationen eine Rückführung auf den oben diskutierten Fall der rechten, oberen Dreiecksmatrix zu erhalten. Betrachten wir hierzu zunächst wieder die gestaffelten Gleichungen für den allgemeinen Fall

(1.7)\[\begin{aligned} \begin{split} a_{1,1}x_1 + a_{1,2}x_2 + \ldots + a_{1,n-1}x_{n-1} + a_{1,n}x_n & = b_1 \\ \vdots & \\ a_{i,1}x_1 + a_{i,2}x_2 + \ldots + a_{i,n-1}x_{n-1} + a_{i,n}x_n & = b_i \\ \vdots & \\ a_{n,1}x_1 + a_{n,2}x_2 + \ldots + a_{n,n-1}x_{n-1} + a_{n,n}x_n & = b_n \end{split} \end{aligned}\]

Die Idee beim Eliminationsverfahren ist es im \(j-\)ten Schritt die unbekannte Variable \(x_j\) aus allen darunter liegenden Gleichungen zu entfernen, sodass nur Nullen unterhalb des \(j\)-ten Diagonaleintrags bleiben und so sukzessive eine rechte, obere Dreiecksmatrix entsteht. Obwohl schon aus der linearen Algebra bekannt, geben wir im Folgenden den Algorithmus des Gauss-Eliminationsverfahrens ausführlich an.

Algorithmus 1.2 (Gauss-Eliminationsverfahren)

Wir nehmen zunächst an, dass die Matrix \(A\) nicht singulär ist. Man beginnt im ersten Schritt mit der Elimination der Variablen \(x_1\) aus den Gleichungen \(i=2,\ldots,n\) in (1.7). Hierzu bestimmen wir für jede Gleichung den passenden Vorfaktor, der nötig ist, damit eine Differenz mit der ersten Gleichung zu einer Null unterhalb der Diagonalen führt, d.h., wir setzen für \(i=2,\ldots,n\) die Koeffizienten

(1.8)\[l_{i,1} \ = \ \frac{a_{i,1}}{a_{1,1}}.\]

An dieser Stelle wollen wir zunächst die starke Annahme machen, dass \(a_{1,1} \neq 0\) ist. Wir werden uns an späterer Stelle um diesen Fall gesondert kümmern.

Die Vorfaktoren \(l_{i,1} \in \R\) multiplizieren wir nun mit der ersten Gleichung und subtrahieren diese von der \(i\)-ten Gleichung. Im Ergebnis verschwindet nun die unbekannte Variable \(x_1\), da wir die Vorfaktoren \(l_{i,1}\) in (1.8) entsprechend gewählt haben. Wir erhalten somit die folgenden neuen Gleichungen für \(i=2,\ldots,n\):

\[0\cdot x_1 + (a_{i,2}-l_{i,1}a_{1,2})x_2 + \ldots + (a_{i,n} - l_{i,1}a_{1,n})x_n \ = \ b_i - l_{i,1}b_1.\]

Wir können das verbleibende System von \(n\) Gleichungen nun wie folgt schreiben

\[\begin{aligned} \begin{split} a_{1,1}x_1 + a_{1,2}x_2 + \ldots + a_{1,n-1}x_{n-1} + a_{1,n}x_n & = b_1 \\ a_{2,2}^{(2)}x_2 + \ldots + a_{2,n-1}^{(2)}x_{n-1} + a_{2,n}^{(2)}x_n & = b_2^{(2)} \\ \vdots & \\ a_{i,2}^{(2)}x_2 + \ldots + a_{i,n-1}^{(2)}x_{n-1} + a_{i,n}^{(2)}x_n & = b_i^{(2)} \\ \vdots & \\ a_{n,2}^{(2)}x_2 + \ldots + a_{n,n-1}^{(2)}x_{n-1} + a_{n,n}^{(2)}x_n & = b_n^{(2)} \end{split} \end{aligned}\]

mit

\[a_{i,k}^{(2)} \coloneqq a_{i,k}^{(1)} - l_{i,1}a_{1,k}^{(1)}, \quad b_i^{(2)} \coloneqq b_i^{(1)} - l_{i,1}b_1^{(1)} \ \text{ für } \ i,k=2,\ldots,n.\]

Hierbei haben wir implizit \(a_{i,k}^{(1)} = a_{i,k}\) und \(b_i^{(1)} = b_i\) gesetzt.

Dieses Vorgehen lässt sich nun für den \(\pmb{j}\)-ten Schritt des Verfahrens für \(j=2,\ldots,n-1\) wie folgt verallgemeinern. Wir setzen nun für die relevanten Gleichungen \(i=j+1,\ldots,n\) die Vorfaktoren als

(1.9)\[l_{i,j} \ \coloneqq \ \frac{a_{i,j}^{(j)}}{a_{j,j}^{(j)}}.\]

Hierbei nehmen wir wiederum an, dass \(a_{j,j}^{(j)} \neq 0\) für \(j=2,\ldots,n\) gilt. Diesen Vorfaktor multipliziert man wieder mit der \(j\)-ten Gleichung und subtrahiert diese von der \(i\)-ten Gleichung für \(i=j+1,\ldots,n\). Im Ergebnis verschwindet nun die unbekannte Variable \(x_j\) in allen Zeilen unterhalb der \(j\)-ten Gleichung. Man erhält damit die folgenden neuen Gleichungen für \(i=j+1,\ldots,n\):

\[\!\!\!0\cdot x_1 + \ldots + 0\cdot x_{j} + (a_{i,j+1}^{(j)}-l_{i,j}a_{j,j+1}^{(j)})x_{j+1} + \ldots + (a_{i,n}^{(j)} - l_{i,j}a_{j,n}^{(j)})x_n = b_i^{(j)} - l_{i,j}b_j^{(j)}.\]

Wir können dieses System von \((n-j)\) Gleichungen nun wie folgt schreiben

\[\begin{aligned} \begin{split} a_{j+1,j+1}^{(j+1)}x_{j+1} + \ldots + a_{j+1,n-1}^{(j+1)}x_{n-1} + a_{j+1,n}^{(j+1)}x_n & = b_{j+1}^{(j+1)} \\ \vdots & \\ a_{n,j+1}^{(j+1)}x_{j+1} + \ldots + a_{n,n-1}^{(j+1)}x_{n-1} + a_{n,n}^{(j+1)}x_n & = b_n^{(j+1)} \end{split} \end{aligned}\]

mit

\[a_{i,k}^{(j+1)} \coloneqq a_{i,k}^{(j)} - l_{i,j}a_{j,k}^{(j)}, \quad b_i^{(j+1)} \coloneqq b_i^{(j)} - l_{i,j}b_j^{(j)} \ \text{ für } \ i,k=j+1,\ldots,n.\]

Nach \(n-1\) Schritten des oben beschriebenen Verfahrens hat man die ursprüngliche Matrix \(A\) in eine obere, rechte Dreiecksform überführt und man erhält nach dem letzten Schritt in der letzten Zeile eine Gleichung mit nur einer unbekannten Variable \(x_n\) wie folgt

\[a_{n,n}^{(n)}x_n \ = \ b_n^{(n)}\]

mit der oben beschriebenen Notation.

Nun lässt sich der unbekannte Vektor \(x \in \mathbb{R}^n\) durch Rückwärtseinsetzen berechnen, wie in Algorithmus 1.1 beschrieben, wenn wir annehmen, dass \(a_{n,n}^{(n)} \neq 0\) gilt.

Das gesamte Verfahren zur Lösung des LGS (1.1) lässt sich anschaulich durch folgenden Pseudo-Code beschreiben.

function x = SolveLES(A,b):
    # Gauss-Elimination
    for j=1,...,n:
        for i=j+1,...,n:
            l = a[i,j] / a[j,j]
            for k=j,...,n:
                a[i,k] = a[i,k] - l * a_[j,k]
            b[i] = b[i] - l * b[j]

    # Rückwärtseinsetzen
    for j=n,...,1:
        x[j] = b[j]
        for k=j+1,...,n:
            x[j] = x[j] - a[j,k] * x[k]
        x[j] = x[j] / a[j,j]

Bemerkung 1.2

Der Rechenaufwand des Gauss-Eliminationsverfahrens in Algorithmus 1.2 liegt in \(\mathcal{O}(n^3)\) bzw. genauer \(\frac{1}3 n^3+ \mathcal{O}(n^2)\).

Beispiel 1.2

Sei

\[A \ = \ \begin{pmatrix} 1 & 2 & 3\\ 1 & 1 & 1\\ 3 & 3 & 1\\ \end{pmatrix}, \quad b \ = \ \begin{pmatrix} 2\\ 2\\ 0 \end{pmatrix}.\]

Das Gauss-Eliminationsverfahren in Algorithmus 1.2 liefert einem die rechte, obere Dreiecksmatrix \(R \coloneqq A^{(n)} \in \R^{3 \times 3}\) und den modifizierten Vektor \(b^{(n)}\in \R^{3}\) mit

\[R \ = \ \begin{pmatrix} 1 & 2 & 3 \\ 0 & -1 & -2\\ 0 & 0 & -2 \end{pmatrix}, \quad b^{(n)} \ = \ \begin{pmatrix} 2\\ 0\\ -6 \end{pmatrix}.\]

Durch Rückwärtseinsetzen mit Algorithmus 1.1 erhält man für das LGS den Lösungsvektor \(x = (5, -6, 3)^T\).