Normalgleichungen (Methode der kleinsten Quadrate)

Studium

A^{T} A\, \vec x = A^{T} \vec b

Voraussetzung: $A \in \mathbb{R}^{m \times n},$ $\vec b \in \mathbb{R}^{m}$

$A$: Koeffizientenmatrix eines meist überbestimmten Systems (m Gleichungen, n Unbekannte)
$\vec b$: rechte Seite, z.B. die Messwerte
$\vec x$: gesuchte Lösung im Sinne der kleinsten Quadrate
$A^{T}$: Transponierte von A

Der Vektor x, der den Fehler |Ax − b| minimiert, löst das quadratische System AᵀAx = Aᵀb.

Erklärung

Ein überbestimmtes Gleichungssystem $A\vec x = \vec b$ mit mehr Gleichungen als Unbekannten hat meist keine exakte Lösung, etwa wenn Messwerte gestreut sind. Man sucht dann das $\vec x$ , für das der Fehler $\lVert A\vec x - \vec b \rVert^2$ möglichst klein ist: die Methode der kleinsten Quadrate.

Dieses $\vec x$ löst die Normalgleichungen $A^T A \vec x = A^T \vec b$ . Der Grund ist geometrisch: $A\vec x$ ist der Punkt im Spaltenraum von $A$ , der $\vec b$ am nächsten liegt, also die orthogonale Projektion von $\vec b$ . Das Residuum $\vec r = \vec b - A\vec x$ steht deshalb senkrecht auf allen Spalten von $A$ , das heißt $A^T \vec r = \vec 0$ . Umgestellt sind das die Normalgleichungen.

Lösbarkeit:

Die Normalgleichungen sind immer lösbar.
$A^T A$ ist genau dann invertierbar, wenn die Spalten von $A$ linear unabhängig sind ( $\operatorname{rg}(A) = n$ ). Dann ist die Lösung eindeutig: $\vec x = (A^T A)^{-1} A^T \vec b$ .

Die Ausgleichsgerade $y = c_0 + c_1 t$ durch Messpunkte $(t_k,\ y_k)$ ist der Spezialfall mit Zeilen $(1,\ t_k)$ in $A$ und $\vec b = (y_k)$ . Für schlecht konditionierte Probleme rechnet man numerisch besser mit der QR-Zerlegung, weil $A^T A$ die Kondition quadriert.

Beispiele

Gesucht ist die Ausgleichsgerade $y = c_0 + c_1 t$ durch $(0 \mid 1)$ , $(1 \mid 3)$ , $(2 \mid 4)$ :

A = \begin{pmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{pmatrix}, \quad \vec b = \begin{pmatrix} 1 \\ 3 \\ 4 \end{pmatrix}, \quad A^T A = \begin{pmatrix} 3 & 3 \\ 3 & 5 \end{pmatrix}, \quad A^T \vec b = \begin{pmatrix} 8 \\ 11 \end{pmatrix}

Das System $3c_0 + 3c_1 = 8$ , $3c_0 + 5c_1 = 11$ liefert $c_1 = \frac32$ und $c_0 = \frac76$ . Die Gerade lautet $y = \frac76 + \frac32 t$ .

Das Residuum ist $\vec r = \left(-\frac16,\ \frac13,\ -\frac16\right)$ . Probe: $A^T \vec r = \left(-\frac16 + \frac13 - \frac16,\ \frac13 - \frac26\right) = (0,\ 0)$ . Die minimale Fehlerquadratsumme ist $\lVert \vec r \rVert^2 = \frac16$ .

Als Vorhersage für $t = 3$ ergibt sich $y = \frac76 + \frac92 = \frac{17}{3} \approx 5{,}67$ .

Typische Fehler

Das überbestimmte System $A\vec x = \vec b$ direkt mit dem Gauß-Algorithmus lösen wollen. Es ist in der Regel widersprüchlich.
$A A^T$ statt $A^T A$ bilden. $A A^T$ ist $m \times m$ und passt nicht zu $\vec x \in \mathbb{R}^n$ .
Die rechte Seite $A^T \vec b$ vergessen und nur $\vec b$ einsetzen.
$(A^T A)^{-1} = A^{-1} (A^T)^{-1}$ ansetzen. Für nicht quadratisches $A$ gibt es kein $A^{-1}$ .

Normalgleichungen (Methode der kleinsten Quadrate)