# Normalgleichungen lösen > 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-loesen Source: https://raw.githubusercontent.com/nakafaai/aksara/16d6b8e869d1a277313c65bbfc4b4a83efe77a46/packages/corpus/material/lesson/ai-ds/linear-methods/normal-equation-solution/de.mdx Löse lineare Ausgleichsprobleme mit QR-Zerlegung und Moore-Penrose-Pseudoinverser und vergleiche ihr numerisches Verhalten mit Normalgleichungen. --- ## Welches Problem wird gelöst? Für $$A \in \mathbb{R}^{m \times n}$$ und $$b \in \mathbb{R}^m$$ sucht ein lineares Ausgleichsproblem den Parametervektor, der das Residuum möglichst klein macht: Visible text: Für und sucht ein lineares Ausgleichsproblem den Parametervektor, der das Residuum möglichst klein macht: ```math \min_x \|Ax-b\|_2^2 ``` Jeder Minimierer erfüllt die Normalgleichung ```math A^T A\hat{x}=A^T b ``` Diese Gleichung ist immer lösbar. Der Minimierer ist genau dann eindeutig, wenn $$\operatorname{rank}(A)=n$$ gilt. Das setzt $$m\ge n$$ voraus. Bei vollem Spaltenrang gilt Visible text: Diese Gleichung ist immer lösbar. Der Minimierer ist genau dann eindeutig, wenn gilt. Das setzt voraus. Bei vollem Spaltenrang gilt ```math \hat{x}=(A^T A)^{-1}A^T b ``` Hat $$A$$ keinen vollen Spaltenrang, bleibt der angepasste Vektor $$A\hat{x}$$ eindeutig, der Parametervektor jedoch nicht. Ist $$\hat{x}$$ eine Lösung, dann liegen alle Lösungen in Visible text: Hat keinen vollen Spaltenrang, bleibt der angepasste Vektor eindeutig, der Parametervektor jedoch nicht. Ist eine Lösung, dann liegen alle Lösungen in ```math \hat{x}+\ker(A) ``` ### Warum gibt es immer eine Lösung? Der Spaltenraum von $$A$$ ist ein endlichdimensionaler abgeschlossener Unterraum von $$\mathbb{R}^m$$. Deshalb besitzt $$b$$ eine eindeutige orthogonale Projektion auf diesen Raum. Jedes $$\hat{x}$$ mit $$A\hat{x}=\operatorname{proj}_{\operatorname{col}(A)}b$$ ist eine Ausgleichslösung. Visible text: Der Spaltenraum von ist ein endlichdimensionaler abgeschlossener Unterraum von . Deshalb besitzt eine eindeutige orthogonale Projektion auf diesen Raum. Jedes mit ist eine Ausgleichslösung. Die Normalgleichung beschreibt dieselbe Geometrie, denn ```math A^T(A\hat{x}-b)=0 ``` bedeutet, dass das Residuum $$A\hat{x}-b$$ zu jeder Spalte von $$A$$ orthogonal ist. Visible text: bedeutet, dass das Residuum zu jeder Spalte von orthogonal ist. ## Moore-Penrose-Pseudoinverse Die Moore-Penrose-Pseudoinverse ist für jede reelle Matrix definiert, auch für rechteckige Matrizen und Matrizen ohne vollen Rang. Ist ```math A=U\Sigma V^T ``` eine Singulärwertzerlegung, wird jeder von null verschiedene Singulärwert $$\sigma_i$$ durch $$1/\sigma_i$$ ersetzt. Singulärwerte gleich null bleiben null. Damit erhält man Visible text: eine Singulärwertzerlegung, wird jeder von null verschiedene Singulärwert durch ersetzt. Singulärwerte gleich null bleiben null. Damit erhält man Component: MathContainer Children: ```math \Sigma^{\dagger}_{ii}=\begin{cases}1/\sigma_i,&\sigma_i>0,\\0,&\sigma_i=0,\end{cases} ``` ```math A^{\dagger}=V\Sigma^{\dagger}U^T ``` ```math x^{\dagger}=A^{\dagger}b ``` Der Vektor $$x^{\dagger}$$ ist die eindeutige Ausgleichslösung mit kleinster euklidischer Norm. Hat $$A$$ vollen Spaltenrang, vereinfacht sich die allgemeine Definition zu Visible text: Der Vektor ist die eindeutige Ausgleichslösung mit kleinster euklidischer Norm. Hat vollen Spaltenrang, vereinfacht sich die allgemeine Definition zu ```math A^{\dagger}=(A^T A)^{-1}A^T ``` Die Pseudoinverse wird durch die vier Penrose-Identitäten eindeutig bestimmt: Component: MathContainer Children: ```math AA^{\dagger}A=A ``` ```math A^{\dagger}AA^{\dagger}=A^{\dagger} ``` ```math (AA^{\dagger})^T=AA^{\dagger} ``` ```math (A^{\dagger}A)^T=A^{\dagger}A ``` ## Direkte Lösung mit der QR-Zerlegung Für eine Matrix mit vollem Spaltenrang und $$m\ge n$$ verwendet man die dünne QR-Zerlegung Visible text: Für eine Matrix mit vollem Spaltenrang und verwendet man die dünne QR-Zerlegung ```math A=Q_1R_1,\qquad Q_1^TQ_1=I ``` Die Zielfunktion des Ausgleichsproblems zerfällt in ```math \|Ax-b\|_2^2=\|R_1x-Q_1^Tb\|_2^2+\|(I-Q_1Q_1^T)b\|_2^2 ``` Der zweite Term hängt nicht von $$x$$ ab. Daher erhält man den Minimierer durch Lösen des oberen Dreieckssystems Visible text: Der zweite Term hängt nicht von ab. Daher erhält man den Minimierer durch Lösen des oberen Dreieckssystems ```math R_1\hat{x}=Q_1^Tb ``` Dieser Weg löst das ursprüngliche Ausgleichsproblem direkt. Man bildet nicht zuerst $$A^TA$$, um anschließend die Normalgleichung zu lösen. Visible text: Dieser Weg löst das ursprüngliche Ausgleichsproblem direkt. Man bildet nicht zuerst , um anschließend die Normalgleichung zu lösen. ## Beispiel einer Polynomanpassung Wir passen $$y=at^2+bt+c$$ an sieben Messwerte an. Die Designmatrix und der Beobachtungsvektor lauten Visible text: Wir passen an sieben Messwerte an. Die Designmatrix und der Beobachtungsvektor lauten Component: MathContainer Children: ```math A=\begin{pmatrix}9&-3&1\\4&-2&1\\1&-1&1\\0&0&1\\1&1&1\\4&2&1\\9&3&1\end{pmatrix} ``` ```math b=\begin{pmatrix}-2{,}2\\-4{,}2\\-4{,}2\\-1{,}8\\1{,}8\\8{,}2\\15{,}8\end{pmatrix} ``` Jede Zeile von $$A$$ hat die Form $$[t_i^2,t_i,1]$$. Eine gültige dünne QR-Zerlegung ist Visible text: Jede Zeile von hat die Form . Eine gültige dünne QR-Zerlegung ist Component: MathContainer Children: ```math Q_1=\begin{pmatrix}-0{,}64286&-0{,}56695&0{,}16496\\-0{,}28571&-0{,}37796&-0{,}24744\\-0{,}07143&-0{,}18898&-0{,}49487\\0&0&-0{,}57735\\-0{,}07143&0{,}18898&-0{,}49487\\-0{,}28571&0{,}37796&-0{,}24744\\-0{,}64286&0{,}56695&0{,}16496\end{pmatrix} ``` ```math R_1=\begin{pmatrix}-14&0&-2\\0&5{,}29150&0\\0&0&-1{,}73205\end{pmatrix} ``` Die Vorzeichen zusammengehöriger Spalten von $$Q_1$$ und Zeilen von $$R_1$$ können sich zwischen gültigen QR-Implementierungen unterscheiden. Das Produkt $$Q_1R_1$$ und die endgültige Anpassung bleiben gleich. Visible text: Die Vorzeichen zusammengehöriger Spalten von und Zeilen von können sich zwischen gültigen QR-Implementierungen unterscheiden. Das Produkt und die endgültige Anpassung bleiben gleich. Zuerst berechnen wir ```math Q_1^Tb=\begin{pmatrix}-9{,}71429\\16{,}02569\\3{,}48060\end{pmatrix} ``` Danach folgt die Rückwärtssubstitution: Component: MathContainer Children: ```math -1{,}73205x_3=3{,}48060\quad\Longrightarrow\quad x_3=-2{,}00952 ``` ```math 5{,}29150x_2=16{,}02569\quad\Longrightarrow\quad x_2=3{,}02857 ``` ```math -14x_1-2x_3=-9{,}71429\quad\Longrightarrow\quad x_1=0{,}98095 ``` Damit gilt Component: MathContainer Children: ```math \hat{x}=\begin{pmatrix}0{,}98095\\3{,}02857\\-2{,}00952\end{pmatrix} ``` ```math \hat{y}(t)=0{,}98095t^2+3{,}02857t-2{,}00952 ``` ```math \|A\hat{x}-b\|_2\approx0{,}41861 ``` Component: LineEquation Props: - title: Ausgleichskurve $$\hat{y}(t)=0{,}98095t^2+3{,}02857t-2{,}00952$$ Visible text: Ausgleichskurve - description: Die cyanfarbene Kurve ist das angepasste Polynom. Die orangefarbenen Punkte sind die sieben Messwerte aus $$b$$. Visible text: Die cyanfarbene Kurve ist das angepasste Polynom. Die orangefarbenen Punkte sind die sieben Messwerte aus . - cameraPosition: [15, 10, 15] - data: (() => { // Die von A und b codierten Messwerte const originalData = [ [-3, -2.2], [-2, -4.2], [-1, -4.2], [0, -1.8], [1, 1.8], [2, 8.2], [3, 15.8] ]; // Die mit der QR-Lösung bestimmten Koeffizienten const a = 0.98095; const b = 3.02857; const c = -2.00952; return [ { points: Array.from({ length: 50 }, (_, i) => { const t = -3 + (i * 6) / 49; const y = a * t * t + b * t + c; return { x: t, y: y, z: 0 }; }), color: "#0891b2", smooth: true, showPoints: false }, { points: originalData.map(([t, y]) => ({ x: t, y: y, z: 0 })), color: "#ea580c", smooth: false, showPoints: true } ]; })() ## Wahl des numerischen Verfahrens | Verfahren | Ungefähre Kosten für dichte Matrizen mit $$m\ge n$$ | Hauptvorteil | Wichtigste Einschränkung | | --- | --- | --- | --- | | Normalgleichungen und Cholesky | $$A^TA$$ in $$O(mn^2)$$ bilden, dann in etwa $$\frac{1}{3}n^3$$ Flops faktorisieren | schnell bei gut konditioniertem Problem und vollem Rang | $$\kappa_2(A^TA)=\kappa_2(A)^2$$ | | Householder-QR | etwa $$2mn^2-\frac{2}{3}n^3$$ Flops | bildet $$A^TA$$ nicht und ist meist stabiler | bei abhängigen Spalten ist eine rangoffenbarende Variante nötig | | SVD | aufwendiger als QR | macht den Rang sichtbar und liefert die Lösung kleinster Norm | höchste Kosten der drei Verfahren | Visible text: | Verfahren | Ungefähre Kosten für dichte Matrizen mit | Hauptvorteil | Wichtigste Einschränkung | | --- | --- | --- | --- | | Normalgleichungen und Cholesky | in bilden, dann in etwa Flops faktorisieren | schnell bei gut konditioniertem Problem und vollem Rang | | | Householder-QR | etwa Flops | bildet nicht und ist meist stabiler | bei abhängigen Spalten ist eine rangoffenbarende Variante nötig | | SVD | aufwendiger als QR | macht den Rang sichtbar und liefert die Lösung kleinster Norm | höchste Kosten der drei Verfahren | QR ist die übliche Wahl für dichte Probleme mit vollem Rang. Verwende die SVD, wenn Rangmangel, starke Fehlkonditionierung oder die Lösung kleinster Norm wichtig ist. Bilde die Normalmatrix nur, wenn ihr Geschwindigkeitsvorteil den Verlust an numerischer Robustheit rechtfertigt, und berechne in Produktionscode niemals explizit die Inverse.