3.4.4 Die Methode der kleinsten Quadrate (least squares)

Die sogenannte ``Methode der kleinsten Quadrate'' (Least Squares) ist eine Methode, um überbestimmte lineare Gleichungssysteme

$$A \mathbf{x} = \mathbf{b}, \qquad A\in{\mathbb{R}}^{m\times n}, \mathbf{x}\in{\mathbb{R}}^{n}, \mathbf{b}\in{\mathbb{R}}^{m}$$ (3.4)

zu lösen. Die $m\times n$-Matrix $A$ hat mehr Zeilen als Spalten ($m>n$). Wir haben also mehr Gleichungen als Unbekannte. Deshalb gibt es im allgemeinen kein $\mathbf{x}$, das die Gleichung (3.4) erfüllt. Die Methode der kleinsten Quadrate bestimmt nun ein $\mathbf{x}$ so, dass die Gleichungen ``möglicht gut'' erfüllt werden. Dabei wird $\mathbf{x}$ so berechnet, dass der Residuenvektor $\mathbf{r} = \mathbf{b}-A\mathbf{x}$ minimale Länge hat. Dieser Vektor $\mathbf{x}$ ist Lösung der Gauss'schen Normalgleichungen

$$A^TA \mathbf{x} = A^T \mathbf{b}.$$

(Die Lösung ist eindeutig, wenn $A$ linear unabhängige Spalten hat.) Die Gaussschen Normalgleichungen haben unter Numerikern einen schlechten Ruf, da für die Konditionszahl cond$(A^TA) =$   cond$(A)^2$ gilt und somit die Lösung $\mathbf{x}$ durch die verwendete Methode ungenauer berechnet wird, als dies durch die Konditionszahl der Matrix $A$ zu erwarten wäre.

Deshalb wird statt der Normalgleichungen die QR-Zerlegung für die Lösung der Gleichung (3.4) nach der Methode der kleinsten Quadrate vorgezogen. Dabei wird die Matrix $A$ zerlegt als Produkt von zwei Matrizen

$$A = Q \begin{bmatrix} R \\ O \end{bmatrix}\quad \Longleftrightarrow \quad Q^T A = \begin{bmatrix} R \\ O \end{bmatrix}.$$

wobei $Q$ $m\times m$ orthogonal und $R$ eine $n\times n$ Rechtsdreiecksmatrix ist. Da orthogonale Matrizen die Länge eines Vektors invariant lassen, gilt

$$\Vert\mathbf{r}\Vert^2 = \Vert Q^T \mathbf{r}\Vert^2 = \Vert Q^T(\mathbf{b}-A\mathbf{x})\Vert^2$$

$$= \left\Vert \begin{bmatrix}\mathbf{y}_1 \\ \mathbf{y}_2 \end{bma... ...ht\Vert^2 = \Vert\mathbf{y}_1 - R\mathbf{x} \Vert^2 + \Vert\mathbf{y}_2\Vert^2.$$

Daraus ist ersichtlich, dass $\vert\vert r\vert\vert^2$ minimiert wird durch jenes $x$, welches $Rx = y_1$ löst.

In MATLAB werden überbestimmte Gleichungssysteme der Form (3.4) automatisch mit der QR-Zerlegung gelöst, wenn man den Backslash-Operator

x = A\b

benützt.