Normales Gleichungssystem

Die Normalgleichung überführt die Optimalitätsbedingung erster Ordnung eines linearen Ausgleichsproblems in ein lineares Gleichungssystem.

Wenn wir minimieren wollen

Es stellt sich heraus, dass die Lösung durch Lösen des folgenden Gleichungssystems gefunden werden kann

Diese Gleichung heißt Normalgleichung, weil das Residuum am Minimum normal, also senkrecht, zum Spaltenraum von $A$ steht.

Grundlegende Beziehung

Es besteht eine sehr interessante Beziehung zwischen dem Minimierungsproblem und diesem normalen Gleichungssystem. Der Vektor $\hat{x} \in \mathbb{R}^n$ ist genau dann eine Lösung für das Problem der kleinsten Quadrate, wenn dieser Vektor das Normalengleichungssystem erfüllt.

Mit anderen Worten: Das Finden von $\hat{x}$, das $\|A \cdot x - b\|_2^2$ minimal macht, ist genau dasselbe wie das Finden von $\hat{x}$, das $A^T A \cdot \hat{x} = A^T b$ erfüllt.

Warum dieses System funktioniert

Um zu verstehen, warum diese Beziehung gilt, müssen wir sie aus einer geometrischen Perspektive betrachten.

Wenn $\hat{x}$ den Minimalwert für $\|A\hat{x} - b\|_2^2$ angibt, muss der Fehlervektor $A\hat{x} - b$ orthogonal zu allen Vektoren im Spaltenraum der Matrix $A$ sein.

Dieser Spaltenraum besteht aus allen Vektoren, die als $Ax$ für $x \in \mathbb{R}^n$ geschrieben werden können. Die Orthogonalitätsbedingung bedeutet

für jeden Vektor $x \in \mathbb{R}^n$. Mithilfe der Eigenschaften des inneren Produkts können wir schreiben

Da diese Beziehung also für alle Vektoren $x$ gelten muss

Dies ist es, was uns das normale Gleichungssystem liefert.

Beweis mit dem Satz des Pythagoras

Wir können dieses Ergebnis auch auf andere Weise überprüfen. Sei $\hat{x}$ die Lösung des Normalengleichungssystems und $x$ ein beliebiger Vektor in $\mathbb{R}^n$.

Mit dem Satz des Pythagoras können wir schreiben

Da $\hat{x}$ das Normalgleichungssystem erfüllt, sind $A^T A\hat{x} - A^T b = 0$ und die quadrierte Norm immer nicht negativ. Deshalb

Diese Ungleichung beweist, dass $\hat{x}$ tatsächlich den Minimalwert ergibt.

Existenz und Eindeutigkeit

Die Normalgleichung ist für jede Matrix $A \in \mathbb{R}^{m\times n}$ und jeden Vektor $b \in \mathbb{R}^m$ lösbar, weil in endlichdimensionalen Räumen stets ein Ausgleichsvektor existiert. Der Minimierer ist genau dann eindeutig, wenn $A$ vollen Spaltenrang besitzt:

In diesem Fall ist $A^{\mathsf T}A$ invertierbar und

Ist $A$ rangdefizient, besitzt die Normalgleichung weiterhin Lösungen, diese sind jedoch nicht eindeutig. Für eine beliebige partikuläre Lösung $\hat{x}$ lautet die vollständige Lösungsmenge

Alle diese Parametervektoren erzeugen denselben angepassten Vektor $A\hat{x}$.

Beweis über Nullraum und Definitheit

Für jedes $z\in\mathbb{R}^n$ gilt

Somit ist $A^{\mathsf T}A$ stets symmetrisch positiv semidefinit. Außerdem gilt

Daher ist

und $A^{\mathsf T}A$ ist genau dann positiv definit, wenn $A$ vollen Spaltenrang hat.

Numerischer Hinweis

Positive Definitheit liefert Eindeutigkeit und erlaubt ein Cholesky-Verfahren, garantiert aber keine gute Kondition. Für eine Matrix mit vollem Spaltenrang gilt

Das explizite Bilden von $A^{\mathsf T}A$ kann daher Empfindlichkeit und Rundungseffekte verstärken. Die Inversenformel ist eine algebraische Identität und keine Anweisung, in Software eine Inverse zu bilden. Für ein gut bestimmtes Ausgleichsproblem mit vollem Rang verwendet man QR, bei Rangmangel oder starker Fehlkonditionierung eine SVD.