1. Direkte Lösung linearer Gleichungssysteme

In diesem Kapitel beschäftigen wir uns zunächst mit einem wohlverstandenen mathematischen Problem - nämlich der direkten Lösung von linearen Gleichungssystemen (abgekürzt als LGS) der Form

(1.1)\[Ax \, = \, b,\]

wobei \(A \in \mathbb{R}^{n \times m}\) eine gegebene reelle \(n \times m\)-Matrix, \(b \in \mathbb{R}^n\) ein gegebener \(n\)-dimensionaler Vektor und \(x \in \mathbb{R}^m\) der unbekannte \(m\)-dimensionale Lösungsvektor ist. Diese werden wir immer in folgender Form indizieren:

\[A \ = \ \begin{pmatrix} a_{1,1} & \dots & a_{1,m} \\ \vdots & \ddots & \vdots \\ a_{n,1} & \dots & a_{n,m} \end{pmatrix}, \quad x \ = \ \begin{pmatrix} x_1 \\ \vdots \\ x_m \end{pmatrix}, \quad b \ = \ \begin{pmatrix} b_1 \\ \vdots \\ b_n \end{pmatrix}.\]

Für unsere Betrachtungen nehmen wir in diesem Kapitel vorerst an, dass \(m = n\) gilt, d.h., es handelt sich bei der Matrix \(A\) um eine quadratische Matrix.

Wir suchen nun einen Vektor \(x \in \mathbb{R}^n\), der die Gleichung (1.1) löst. Wir suchen also nach denjenigen Koeffizienten, mit denen sich der Vektor \(b\) als Linearkombination aus Spaltenvektoren der Matrix \(A\) darstellen lässt. Diese Koeffizienten entsprechen den Einträgen des unbekannten Vektors \(x\). In einem späteren Kapitel der Vorlesung werden wir uns mit dem komplizierteren Fall von überbestimmten und unterbestimmten LGS beschäftigen. Aus der linearen Algebra ist bekannt, dass es genau dann eine eindeutige Lösung \(x \in \mathbb{R}^n\) für die Gleichung (1.1) gibt, falls die Determinante \(\operatorname{det}(A) \neq 0\) ist, wie folgendes Theorem besagt.

Satz 1.1 (Lösbarkeit von linearen Gleichungssystemen)

Das lineare Gleichungssystem (1.1) ist genau dann eindeutig lösbar, wenn \(A\) nicht singulär ist, d.h., wenn die Determinante der Matrix \(A\) ungleich Null ist.

Wir sehen für den Fall \(\operatorname{det}(A) \neq 0\), dass die Spalten von \(A\) linear unabhängig sind und damit eine Basis des \(\mathbb{R}^n\), deshalb ist \(b\) immer als Linearkombination der Spaltenvektoren von \(A\) darstellbar. Für den Fall \(\operatorname{det}(A) = 0\) lässt sich bemerken, dass das Problem einen Lösungsvektor \(x \in \mathbb{R}^n\) für (1.1) zu finden schlecht gestellt ist, da hier keine eindeutige Lösung existiert.

Leider lässt sich der Matrix \(A\) in der Regel nicht direkt ansehen, ob sie singulär ist oder nicht, d.h., ob \(\operatorname{det}(A) = 0\) gilt oder nicht. Würde man die Determinante von A mit der in der linearen Algebra geläufigen Leibniz-Formel

(1.2)\[\operatorname{det}(A) \ = \ \sum_{\sigma\in S_n} \left( \operatorname{sgn}(\sigma) \prod_{i=1}^n a_{i,\sigma(i)} \right)\]

berechnen, so stellt man fest, dass der Rechenaufwand für wachsende \(n \in \mathbb{N}\) sehr schnell ansteigt, was an der großen Zahl an kombinatorischen Möglichkeiten liegt, die es gibt um die Einträge von \(A\) mit Hilfe von Permutationen \(\sigma\) der symmetrischen Gruppe \(S_n\) vom Grad \(n \in \N\) zu permutieren. In diesem Zusammenhang bezeichnet \(\operatorname{sgn}(\sigma)\) das Signum der Permutation \(\sigma\), welches \(+1\) für gerade und \(-1\) für ungerade Permutationen ist. Auf Grund der Anzahl der möglichen Permutation wird klar, dass man für gegebenes \(n \in \mathbb{N}\) genau \(n!\) Summanden in (1.2) aufsummieren muss, um die Determinante zu prüfen.

Um im Allgemeinen Aussagen über den Rechenaufwand eines Algorithmus machen zu können, benötigen wir folgende Definition.

Definition 1.1 (Rechenaufwand und Landau-Notation)

Um den Rechenaufwand eines Algorithmus anzugeben, zählt man die benötigte Anzahl an Additionen, Multiplikationen und Vergleichen. Angegeben wird der Rechenaufwand häufig in Floating Point Operations (abgekürzt als FLOPs), bei welchen historisch bedingt eine Addition und eine Multiplikation zu einer Rechenoperation zusammengefasst werden. Für moderne Mikroprozessorarchitekturen ist dies natürlich eine sehr starke Vereinfachung. Weitere Informationen zur Berechnung von FLOPS finden sich unter [FLO].  
Um den Rechenaufwand eines Algorithmus in eine Klasse von Funktionen einzuordnen verwendet man häufig die Landau-Notation wie folgt. Seien \(f,g \colon \mathbb{R} \rightarrow \mathbb{R}\) zwei reelle Funktionen. Wir schreiben \(f \in \mathcal{O}(g)\), d.h., \(g\) ist eine asymptotisch obere Schranke für \(f\), wenn gilt:

\[\exists C > 0, \exists x_0 \in \R, \forall x > x_0 \colon |f(x)| \leq C |g(x)|.\]

Das folgende Beispiel verwendet die Landau-Notation zur Angabe des Rechenaufwands für die Suche eines Elements in einer unsortierten und einer sortierten Menge.

Beispiel 1.1 (Elementsuche)

Die Anzahl der Vergleiche, die man beim Suchen eines Werts in einer unsortierten Menge aus \(n\) Elementen benötigt liegt in \(\mathcal{O}(n)\), da man jedes Element einzeln überprüfen muss.

Ist die Menge bereits sortiert, so liegt die Anzahl der benötigten Vergleichsoperationen mit dem Intervallhalbierungsverfahren in \(\mathcal{O}(\operatorname{log} n)\).

Für große \(n\) ist immer nur die führende Ordnung beim Aufwand interessant, deshalb ist es nicht so wichtig die weiteren Ordnungen genau zu bestimmen. So werden wir für ein Verfahren, dass beispielsweise \(2n^2+4n + 3\) Operationen benötigt, als Aufwand typischerweise \(2n^2 + \mathcal{O}(n)\) angeben.