Lineares Ausgleichsproblem

Vom inkonsistenten System zur besten Anpassung

Seien $A \in \mathbb{R}^{m \times n}$, $x \in \mathbb{R}^n$ und $b \in \mathbb{R}^m$. Wir betrachten das folgende System.

Liegt $b$ nicht im Spaltenraum von $A$, besitzt dieses System keine exakte Lösung. Das kommt häufig vor, wenn ein Modell an verrauschte Messwerte angepasst wird oder ein überbestimmtes System mehr Gleichungen als Unbekannte enthält und diese Gleichungen widersprüchlich sind.

Wenn kein Vektor $x$ die Gleichung $Ax=b$ exakt erfüllt, definieren wir das Residuum

Gesucht ist der Vektor $x$ mit dem kleinsten Residuum. Das lineare Ausgleichsproblem wird wie folgt geschrieben.

Da das Residuum $m$ Komponenten besitzt, lässt sich die Zielfunktion schreiben als

Durch das Quadrieren sind alle Beiträge nicht negativ. Eine große Residualkomponente wird stärker gewichtet als eine kleine.

Die geometrische Bedingung

Der Vektor $A\hat{x}$ ist der Punkt in $\operatorname{col}(A)$, der $b$ im euklidischen Abstand am nächsten liegt. Im Optimum steht das Residuum senkrecht auf jeder Spalte von $A$:

Die zweite Gleichung heißt Normalgleichung.

Das Diagramm beschriftet den Zielvektor $b$, den Projektionspunkt $A\hat{x}$ und das Residuum $A\hat{x}-b$ zwischen beiden. Der blaue Vektor $A\hat{x}$ liegt im Spaltenraum. Die Orthogonalitätsbedingung oben beweist, dass dieser Punkt im Spaltenraum den kleinsten Abstand zu $b$ besitzt.

Eine Konstante an drei Beobachtungen anpassen

Eine Konstante $x$ soll die drei Beobachtungen $1$, $2$ und $6$ möglichst gut darstellen. Dazu verwenden wir die folgende Matrix und den folgenden Vektor.

Die Zielfunktion für dieses Beispiel lautet

Setzen wir die Ableitung gleich null, erhalten wir $\hat{x}=3$. Der angepasste Vektor und das Residuum sind

Die Residualkomponenten summieren sich zu null:

Damit ist die Normalgleichung erfüllt.

Andere Residualnormen

Die gewählte Norm bestimmt, welche Fehlerart bei der Anpassung im Vordergrund steht.

Die Formulierungen mit $\ell_1$ und $\ell_\infty$ lassen sich als lineare Programme schreiben. Ihre Eignung hängt weiterhin vom Entstehungsprozess der Daten und vom relevanten Fehlerkriterium der Anwendung ab.

Bei denselben Beobachtungen 1, 2 und 6 verändert die Norm die angepasste Konstante. Kleinste Quadrate wählen den Mittelwert, der absolute Verlust den Median, und der kleinste maximale Fehler gleicht die Abstände zu beiden Extremwerten aus.

Ein stabiles numerisches Verfahren wählen

Hat $A$ vollen Spaltenrang, ist der Ausgleichsvektor eindeutig. Aus der Normalgleichung folgt dann

Diese Identität beschreibt den eindeutigen Minimierer, wenn $A$ vollen Spaltenrang hat. Berechne ihn nicht durch ausdrückliches Bilden der Inversen. Wähle das numerische Verfahren anhand von Rang und Kondition:

• Verwende eine $\mathrm{QR}$-Zerlegung für ein stabiles Ausgleichsproblem mit vollem Rang
• Verwende eine $\mathrm{SVD}$, wenn Rangmangel oder schlechte Konditionierung wichtig sind
• Verwende die Pseudoinverse, um bei mehreren Minimierern die Lösung mit kleinster Norm auszuwählen

Es gibt außerdem eine präzise statistische Interpretation. Wir betrachten das folgende Modell.

Ist $A$ fest und sind die gaußverteilten Fehler unabhängig mit gleicher Varianz, liefert die Methode der kleinsten Quadrate den Maximum-Likelihood-Schätzer für $x_*$. Korrelierte Fehler oder unterschiedliche Varianzen erfordern Gewichte, die der Fehlerkovarianz entsprechen.