# Normales Gleichungssystem > For AI agents: use [llms.txt](https://nakafa.com/llms.txt) for the site index. Markdown versions are available by appending `.md` to content URLs or sending `Accept: text/markdown`. URL: https://nakafa.com/de/faecher/ki-und-data-science/lineare-methoden-der-ki/normalengleichung Source: https://raw.githubusercontent.com/nakafaai/aksara/16d6b8e869d1a277313c65bbfc4b4a83efe77a46/packages/corpus/material/lesson/ai-ds/linear-methods/normal-equation/de.mdx Lernen Sie Normalgleichungen für die Optimierung der kleinsten Quadrate. Lernen Sie geschlossene Lösungen, Orthogonalitätsprinzipien und wann Systeme lösbar sind. --- ## Was ist ein Normalgleichungssystem? Die Normalgleichung überführt die Optimalitätsbedingung erster Ordnung eines linearen Ausgleichsproblems in ein lineares Gleichungssystem. Wenn wir minimieren wollen ```math \min_x \|A \cdot x - b\|_2^2 ``` Es stellt sich heraus, dass die Lösung durch Lösen des folgenden Gleichungssystems gefunden werden kann ```math A^T A \cdot x = A^T b ``` Diese Gleichung heißt **Normalgleichung**, weil das Residuum am Minimum normal, also senkrecht, zum Spaltenraum von $$A$$ steht. Visible text: Diese Gleichung heißt **Normalgleichung**, weil das Residuum am Minimum normal, also senkrecht, zum Spaltenraum von steht. ## Grundlegende Beziehung Es besteht eine sehr interessante Beziehung zwischen dem Minimierungsproblem und diesem normalen Gleichungssystem. Der Vektor $$\hat{x} \in \mathbb{R}^n$$ ist genau dann eine Lösung für das Problem der kleinsten Quadrate, wenn dieser Vektor das Normalengleichungssystem erfüllt. Visible text: Es besteht eine sehr interessante Beziehung zwischen dem Minimierungsproblem und diesem normalen Gleichungssystem. Der Vektor ist genau dann eine Lösung für das Problem der kleinsten Quadrate, wenn dieser Vektor das Normalengleichungssystem erfüllt. Mit anderen Worten: Das Finden von $$\hat{x}$$, das $$\|A \cdot x - b\|_2^2$$ minimal macht, ist genau dasselbe wie das Finden von $$\hat{x}$$, das $$A^T A \cdot \hat{x} = A^T b$$ erfüllt. Visible text: Mit anderen Worten: Das Finden von , das minimal macht, ist genau dasselbe wie das Finden von , das erfüllt. ## Warum dieses System funktioniert Um zu verstehen, warum diese Beziehung gilt, müssen wir sie aus einer geometrischen Perspektive betrachten. Wenn $$\hat{x}$$ den Minimalwert für $$\|A\hat{x} - b\|_2^2$$ angibt, muss der Fehlervektor $$A\hat{x} - b$$ orthogonal zu allen Vektoren im Spaltenraum der Matrix $$A$$ sein. Visible text: Wenn den Minimalwert für angibt, muss der Fehlervektor orthogonal zu allen Vektoren im Spaltenraum der Matrix sein. Dieser Spaltenraum besteht aus allen Vektoren, die als $$Ax$$ für $$x \in \mathbb{R}^n$$ geschrieben werden können. Die Orthogonalitätsbedingung bedeutet Visible text: Dieser Spaltenraum besteht aus allen Vektoren, die als für geschrieben werden können. Die Orthogonalitätsbedingung bedeutet ```math 0 = \langle Ax, A\hat{x} - b \rangle ``` für jeden Vektor $$x \in \mathbb{R}^n$$. Mithilfe der Eigenschaften des inneren Produkts können wir schreiben Visible text: für jeden Vektor . Mithilfe der Eigenschaften des inneren Produkts können wir schreiben Component: MathContainer Children: ```math 0 = (Ax)^T (A\hat{x} - b) = x^T (A^T A\hat{x} - A^T b) ``` Da diese Beziehung also für alle Vektoren $$x$$ gelten muss Visible text: Da diese Beziehung also für alle Vektoren gelten muss ```math A^T A\hat{x} - A^T b = 0 ``` Dies ist es, was uns das normale Gleichungssystem liefert. ## Beweis mit dem Satz des Pythagoras Wir können dieses Ergebnis auch auf andere Weise überprüfen. Sei $$\hat{x}$$ die Lösung des Normalengleichungssystems und $$x$$ ein beliebiger Vektor in $$\mathbb{R}^n$$. Visible text: Wir können dieses Ergebnis auch auf andere Weise überprüfen. Sei die Lösung des Normalengleichungssystems und ein beliebiger Vektor in . Mit dem Satz des Pythagoras können wir schreiben Component: MathContainer Children: ```math \|Ax - b\|_2^2 = \|A\hat{x} - b - A(\hat{x} - x)\|_2^2 ``` ```math = \|A\hat{x} - b\|_2^2 + \|A(\hat{x} - x)\|_2^2 - 2 \langle A\hat{x} - b, A(\hat{x} - x) \rangle ``` ```math = \|A\hat{x} - b\|_2^2 + \underbrace{\|A(\hat{x} - x)\|_2^2}_{\geq 0} - 2 \underbrace{(\hat{x} - x)^T (A^T A\hat{x} - A^T b)}_{=0} ``` Da $$\hat{x}$$ das Normalgleichungssystem erfüllt, sind $$A^T A\hat{x} - A^T b = 0$$ und die quadrierte Norm immer nicht negativ. Deshalb Visible text: Da das Normalgleichungssystem erfüllt, sind und die quadrierte Norm immer nicht negativ. Deshalb ```math \|Ax - b\|_2^2 = \|A\hat{x} - b\|_2^2 + \|A(\hat{x} - x)\|_2^2 \geq \|A\hat{x} - b\|_2^2 ``` Diese Ungleichung beweist, dass $$\hat{x}$$ tatsächlich den Minimalwert ergibt. Visible text: Diese Ungleichung beweist, dass tatsächlich den Minimalwert ergibt. ## Existenz und Eindeutigkeit Die Normalgleichung ist für jede Matrix $$A \in \mathbb{R}^{m\times n}$$ und jeden Vektor $$b \in \mathbb{R}^m$$ lösbar, weil in endlichdimensionalen Räumen stets ein Ausgleichsvektor existiert. Der Minimierer ist genau dann eindeutig, wenn $$A$$ vollen Spaltenrang besitzt: Visible text: Die Normalgleichung ist für jede Matrix und jeden Vektor lösbar, weil in endlichdimensionalen Räumen stets ein Ausgleichsvektor existiert. Der Minimierer ist genau dann eindeutig, wenn vollen Spaltenrang besitzt: ```math \operatorname{rank}(A)=n ``` In diesem Fall ist $$A^{\mathsf T}A$$ invertierbar und Visible text: In diesem Fall ist invertierbar und ```math \hat{x}=(A^{\mathsf T}A)^{-1}A^{\mathsf T}b ``` Ist $$A$$ rangdefizient, besitzt die Normalgleichung weiterhin Lösungen, diese sind jedoch nicht eindeutig. Für eine beliebige partikuläre Lösung $$\hat{x}$$ lautet die vollständige Lösungsmenge Visible text: Ist rangdefizient, besitzt die Normalgleichung weiterhin Lösungen, diese sind jedoch nicht eindeutig. Für eine beliebige partikuläre Lösung lautet die vollständige Lösungsmenge ```math \hat{x}+\ker(A) ``` Alle diese Parametervektoren erzeugen denselben angepassten Vektor $$A\hat{x}$$. Visible text: Alle diese Parametervektoren erzeugen denselben angepassten Vektor . ## Beweis über Nullraum und Definitheit Für jedes $$z\in\mathbb{R}^n$$ gilt Visible text: Für jedes gilt ```math z^{\mathsf T}A^{\mathsf T}Az=\|Az\|_2^2\ge0 ``` Somit ist $$A^{\mathsf T}A$$ stets symmetrisch positiv semidefinit. Außerdem gilt Visible text: Somit ist stets symmetrisch positiv semidefinit. Außerdem gilt ```math A^{\mathsf T}Az=0\quad\Longleftrightarrow\quad z^{\mathsf T}A^{\mathsf T}Az=0\quad\Longleftrightarrow\quad Az=0 ``` Daher ist ```math \ker(A^{\mathsf T}A)=\ker(A) ``` und $$A^{\mathsf T}A$$ ist genau dann positiv definit, wenn $$A$$ vollen Spaltenrang hat. Visible text: und ist genau dann positiv definit, wenn vollen Spaltenrang hat. ## Numerischer Hinweis Positive Definitheit liefert Eindeutigkeit und erlaubt ein Cholesky-Verfahren, garantiert aber keine gute Kondition. Für eine Matrix mit vollem Spaltenrang gilt ```math \kappa_2(A^{\mathsf T}A)=\kappa_2(A)^2 ``` Das explizite Bilden von $$A^{\mathsf T}A$$ kann daher Empfindlichkeit und Rundungseffekte verstärken. Die Inversenformel ist eine algebraische Identität und keine Anweisung, in Software eine Inverse zu bilden. Für ein gut bestimmtes Ausgleichsproblem mit vollem Rang verwendet man QR, bei Rangmangel oder starker Fehlkonditionierung eine SVD. Visible text: Das explizite Bilden von kann daher Empfindlichkeit und Rundungseffekte verstärken. Die Inversenformel ist eine algebraische Identität und keine Anweisung, in Software eine Inverse zu bilden. Für ein gut bestimmtes Ausgleichsproblem mit vollem Rang verwendet man QR, bei Rangmangel oder starker Fehlkonditionierung eine SVD.