Lineares Ausgleichsproblem

Seien $A \in \mathbb{R}^{m \times n}$, $x \in \mathbb{R}^n$ und $b \in \mathbb{R}^m$. Liegt $b$ nicht im Spaltenraum von $A$, dann besitzt das System

keine exakte Lösung. Das kommt häufig vor, wenn ein Modell an verrauschte Messwerte angepasst wird oder ein überbestimmtes System mehr unabhängige Gleichungen als Unbekannte enthält.

Statt die Gleichheit zu erzwingen, definieren wir das Residuum

und wählen den Vektor mit dem kleinsten Residuum. Das gewöhnliche lineare Ausgleichsproblem lautet

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.

Die Szene zeigt den Zielvektor, seine Projektion und das verbindende Residuum. Der blaue Vektor stellt den projizierten Punkt im Spaltenraum dar, nicht den gesamten Unterraum. Die Orthogonalitätsbedingung oben ist die exakte Aussage, durch die $A\hat{x}$ zum nächstgelegenen Punkt wird.

Ein kleines durchgerechnetes Beispiel

Eine Konstante $x$ soll die drei Beobachtungen $1$, $2$ und $6$ möglichst gut darstellen. Dann gilt

und die Zielfunktion 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.

Kleinste Quadrate zuverlässig berechnen

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

Diese Identität ist für die Analyse nützlich. Das explizite Bilden der Inversen ist jedoch nicht das bevorzugte numerische Verfahren. In der Praxis:

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

Es gibt außerdem eine präzise statistische Interpretation. Im Modell

mit festem $A$ und unabhängigen gaußverteilten Fehlern gleicher Varianz ist die Methode der kleinsten Quadrate der Maximum-Likelihood-Schätzer für $x_*$. Korrelierte Fehler oder unterschiedliche Varianzen erfordern eine andere Gewichtung statt der uneingeschränkten gewöhnlichen Ausgleichsformel.