Normales Gleichungssystem

Die Optimalitätsbedingung als lineares Gleichungssystem

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

Gesucht ist das $x$, das $A \cdot x$ möglichst nahe an $b$ bringt:

Ein Minimierer erfüllt das folgende lineare Gleichungssystem:

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

Kleinste Quadrate und die Normalgleichung

Ein Vektor $\hat{x} \in \mathbb{R}^n$ minimiert $\|A \cdot x - b\|_2^2$ genau dann, wenn er $A^T A \cdot \hat{x} = A^T b$ erfüllt. Das Optimierungsproblem und die Normalgleichung haben daher dieselbe Lösungsmenge. Genau diese Äquivalenz macht aus einem Minimierungsproblem ein lineares Gleichungssystem, das du mit Elimination oder einer Faktorisierung lösen kannst.

Das Residuum steht senkrecht zum Spaltenraum

Wenn $\hat{x}$ den Ausdruck $\|A\hat{x} - b\|_2^2$ minimiert, steht der Residualvektor $A\hat{x} - b$ senkrecht auf jedem Vektor im Spaltenraum von $A$.

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

Diese Orthogonalitätsbedingung gilt für jeden Vektor $x \in \mathbb{R}^n$. Die Eigenschaften des inneren Produkts liefern

Da diese Gleichheit für jeden Vektor $x$ gilt, muss der Vektor in der Klammer null sein:

Nach dem Umstellen folgt $A^TA\hat{x}=A^Tb$, die Normalgleichung.

Beweis mit dem Satz des Pythagoras

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

Mit dem Satz des Pythagoras können wir schreiben

Da $\hat{x}$ die Normalgleichung erfüllt, verschwindet der Kreuzterm. Es bleibt:

Die addierte quadrierte Norm ist nicht negativ. Deshalb kann die quadrierte Norm des Residuums bei keinem $x$ kleiner sein als bei $\hat{x}$:

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

Die Gleichheit der Nullräume zeigt, dass $A^{\mathsf T}A$ genau dann positiv definit ist, 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 $\mathrm{QR}$, bei Rangmangel oder starker Fehlkonditionierung eine $\mathrm{SVD}$.

Ein Beispiel mit zwei Beobachtungen

Seien $A=(1,2)^T$ und $b=(2,1)^T$. Ein skalarer Parameter kann nicht beide Beobachtungen erfüllen. Die erste Gleichung verlangt $x=2$, die zweite $x=1/2$. Die Ausgleichslösung minimiert die Summe der quadrierten Residuen.

Das Residuum steht senkrecht auf der Geraden aller möglichen Vorhersagen. Eine Verschiebung entlang dieser Geraden addiert einen nichtnegativen quadratischen Abstand, wie im Pythagorasbeweis.