3.3. Die Minimum-Norm-Lösung

Wir haben uns in den vorherigen Abschnitten hauptsächlich mit linearen Gleichungssystemen der Form \(Ax=b\) mit \(A \in \mathbb{R}^{m\times n}\), \(x\in \mathbb{R}^n\) und \(b\in \mathbb{R}^m\) für den Fall \(m \geq n\) und \(\rank(A) = n\) beschäftigt. Für diesen Fall konnten wir bisher immer eine eindeutige Lösung des linearen Ausgleichsproblems

\[\min_{x\in\mathbb{R}^n} \norm{b - Ax}_2\]

angeben. Wie wir jedoch in Bemerkung 3.2 bereits festgestellt haben liefern die Normalengleichungen keine eindeutige Lösung falls der Rang der Matrix \(A\) nicht voll ist, d.h. \(\rank(A) < n\) und somit die Matrix \(A^TA\) singulär ist. Die folgende Berechnung verdeutlicht, dass man in diesem Fall keine eindeutige Lösung erwarten kann.

Sei \(A\in \mathbb{R}^{m\times n}\) und \(b\in \mathbb{R}^m\) beliebig. Für eine Lösung der Normalengleichung \(x \in \mathbb{R}^n\)

\[A^TAx \ = \ A^Tb.\]

sehen wir, dass für jeden Vektor \(n\in\Kern(A)\) gilt,

(3.5)\[\begin{aligned} A^T A (x + n) = A^T A x = A^T b. \end{aligned}\]

Ist nun \(\rank(A)< n\), so existiert immer solch ein nichttrivialer Vektor \(0\neq n\in\Kern(A)\), so dass \(x\in \R^n\) und \((x+n) \in \R^n\) zwei verschiedene Lösungen der Normalengleichungen darstellen.

Um selbst in diesem nicht-eindeutigen Fall einen sinnvollen Begriff einer Lösung des linearen Gleichungssystems \(Ax = b\) zu definieren, führen wir eine zusätzliche Bedingung an den Lösungsvektor \(x \in \mathbb{R}^n\) ein. Wir wählen aus allen Lösungen den mit der kleinsten Euklidischen Norm aus.

Definition 3.7 (Minimum-Norm-Lösung)

Sei \(A \in \mathbb{R}^{m\times n}\) und \(b\in \mathbb{R}^m\). Ein Vektor \(x^\mps \in \mathbb{R}^n\) heißt Minimum-Norm-Lösung von \(Ax = b\) genau dann, wenn folgende zwei Bedingungen erfüllt sind:

1. \(x^\mps\) ist Kleinste-Quadrate-Lösung von \(Ax=b\) (siehe (3.2)),

2. \(x^\mps\) hat von allen existierenden Kleinste-Quadrate-Lösungen \(x \in \R^n\) die kleinste Norm, d.h.,

   \[\begin{aligned} \norm{x^\mps}_2 \, \leq \, \norm{x}_2. \end{aligned}\]

Bemerkung 3.6

In der obigen Definition der Minimum-Norm-Lösung werden keinerlei Voraussetzungen an die Dimensionen \(m\) und \(n\), sowie den Rang \(\rank(A)\) von \(A\) gemacht.

Um den Zusammenhang der Kleinste-Quadrat-Lösungen und der Minimum-Norm-Lösung zu verstehen wollen wir das Problem wieder geometrisch deuten. Wir wissen, dass das lineare Gleichungssystem \(Ax = b\) genau dann lösbar ist, wenn die rechte Seite im Bild der Matrix \(A\) liegt, d.h., wenn \(b \in \mathcal{R}(A)\) gilt. Falls dem nicht so ist, so haben wir in Gaußsche Normalengleichungen und Ausgleichsprobleme den Vektor \(b\) orthogonal auf das Bild von \(A\) projiziert, um somit das geringste Residuum zu erhalten. Die so erhaltenen Lösungen sind die Kleinste-Quadrate-Lösungen.

Falls die Kleinste-Quadrate-Lösungen nicht eindeutig sind, d.h. es gilt \(\rank(A) < n\), so können wir wie folgt vorgehen. Da jede Kleinste-Quadrate-Lösung \(\hat{x} \in \R^n\) sich darstellen lässt als

\[\hat{x} \ = \ r + \hat{n}, \quad r\in \mathcal{R}(A^T), \ \hat{n} \in \mathcal{N}(A),\]

und der Anteil \(\hat{n}\) im Kern von \(A\) wegen (3.5) keine Bedeutung für die Lösung von \(Ax = b\) besitzt, so können wir orthogonal auf den Raum \(\mathcal{R}(A^T)\) projizieren. Diese Projektion ist eindeutig bestimmt und liefert uns die Minimum-Norm-Lösung \(x^\mps \in \mathcal{R}(A^T)\).

Der folgende Satz präzisiert die obige geometrische Betrachtung weiter gehend.

Satz 3.2 (Minimum-Norm-Lösung)

Sei \(A \in \mathbb{R}^{m\times n}\) und \(b\in \mathbb{R}^m\). Der Vektor \(x^\mps \in \mathbb{R}^n\) ist genau dann die eindeutige Minimum-Norm-Lösung von \(Ax=b\), falls gilt

1. \(A^TAx^\mps = A^Tb\), d.h., \(x^+\) löst die Normalengleichung,

2. \(x^\mps \in \mathcal{R}(A^T)\).

Proof. Es seien \(x_1,x_2 \in \R^n\) zwei Kleinste-Quadrate-Lösungen von (3.2). Dann existiert nach Lemma 3.1 jeweils zwei Vektoren \(r_1,r_2\in\Image(A^T)\) und \(n_1,n_2\in\Kern(A)\), so dass gilt

\[\begin{aligned} x_1 = r_1 + n_1,\qquad x_2 = r_2 + n_2. \end{aligned}\]

Da \(x_1\) und \(x_2\) nach Satz 3.1 ebenfalls die Normalengleichungen erfüllen, gilt außerdem

\[\begin{aligned} &A^TA r_1 \: = \: A^TA (r_1 + n_1) \: = \: A^T b \: = \: A^T A (r_2 + n_2) \: = \: A^T A r_2\\ \Rightarrow \quad &A^T A (r_1 - r_2) \: = \: 0\\ \Rightarrow \quad &r_1 - r_2 \in \Kern(A^TA). \end{aligned}\]

Da aber nach Lemma 3.1 gilt \(\Kern(A^TA)=\Image(A^T)^\perp\) und gleichzeitig aber auch \(r_1 - r_2\in \Image(A^T)\) ist, folgt schon \(r_1 - r_2 = 0\). Somit haben wir gezeigt, dass es ein eindeutig bestimmten Vektor \(r\in\Image(A^T)\) gibt, so dass jede Kleinste-Quadrate-Lösung für \(\hat{n}\in\Kern(A)\) von der folgenden Form ist:

\[\hat{x} \: = \: r + \hat{n}.\]

Wir definieren nun für \(\hat{n} = 0\) die spezielle Kleinste-Quadrate-Lösung \(x^\mps \in \R^n\) als

\[\begin{aligned} x^\mps \: \coloneqq \: r. \end{aligned}\]

Wir können außerdem für eine beliebige Kleinste-Quadrate-Lösung \(\hat{x} \in \mathbb{R}^n\) folgende Abschätzung treffen

\[\norm{\hat{x}}_2^2 \ = \ \norm{x^\mps + \hat{n}}^2_2 \ = \ \norm{x^\mps}_2^2 + 2\underbrace{\langle x^\mps, \hat{n}\rangle}_{=0} + \norm{\hat{n}}_2^2 \ = \ \norm{x^\mps}_2^2 + \norm{n}_2^2 \ \geq \ \norm{x^\mps}_2^2.\]

Eine echte Gleichheit in obiger Ungleichung erhält man genau dann wenn \(\hat{n} = 0\) ist und somit \(\hat{x} = x^\mps\) gilt. Die Minimum-Norm-Lösung ist also eindeutig durch \(x^\mps \in \Image(A^T)\) bestimmt. ◻