# Lineares Ausgleichsproblem > 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/lineares-ausgleichsproblem Source: https://raw.githubusercontent.com/nakafaai/aksara/16d6b8e869d1a277313c65bbfc4b4a83efe77a46/packages/corpus/material/lesson/ai-ds/linear-methods/linear-equilibrium-problem/de.mdx Löse inkonsistente lineare Systeme mit kleinsten Quadraten, Residualnormen, orthogonaler Projektion, Normalgleichungen und numerisch stabilen Verfahren. --- ## Vom inkonsistenten System zur besten Anpassung Seien $$A \in \mathbb{R}^{m \times n}$$, $$x \in \mathbb{R}^n$$ und $$b \in \mathbb{R}^m$$. Liegt $$b$$ nicht im Spaltenraum von $$A$$, dann besitzt das System Visible text: Seien , und . Liegt nicht im Spaltenraum von , dann besitzt das System ```math Ax=b ``` keine exakte Lösung. Das kommt häufig vor, wenn ein Modell an verrauschte Messwerte angepasst wird oder ein überbestimmtes System mehr unabhängige Gleichungen als Unbekannte enthält. Statt die Gleichheit zu erzwingen, definieren wir das Residuum ```math e(x)=Ax-b ``` und wählen den Vektor mit dem kleinsten Residuum. Das gewöhnliche lineare Ausgleichsproblem lautet ```math \hat{x}\in\operatorname*{arg\,min}_{x\in\mathbb{R}^n}\|Ax-b\|_2^2 ``` Da das Residuum $$m$$ Komponenten besitzt, lässt sich die Zielfunktion schreiben als Visible text: Da das Residuum Komponenten besitzt, lässt sich die Zielfunktion schreiben als ```math \|Ax-b\|_2^2=\sum_{i=1}^{m}(Ax-b)_i^2 ``` Durch das Quadrieren sind alle Beiträge nicht negativ. Eine große Residualkomponente wird stärker gewichtet als eine kleine. ## Die geometrische Bedingung Der Vektor $$A\hat{x}$$ ist der Punkt in $$\operatorname{col}(A)$$, der $$b$$ im euklidischen Abstand am nächsten liegt. Im Optimum steht das Residuum senkrecht auf jeder Spalte von $$A$$: Visible text: Der Vektor ist der Punkt in , der im euklidischen Abstand am nächsten liegt. Im Optimum steht das Residuum senkrecht auf jeder Spalte von : Component: MathContainer Children: ```math A^{\mathsf T}(A\hat{x}-b)=0 ``` ```math A^{\mathsf T}A\hat{x}=A^{\mathsf T}b ``` Die zweite Gleichung heißt **Normalgleichung**. Component: LineEquation Props: - title: Orthogonale Projektion beim Ausgleichsproblem - description: Der blaue Vektor endet bei $$A\hat{x}$$, der orangefarbene bei $$b$$, und der violette Vektor ist das Residuum $$A\hat{x}-b$$. Visible text: Der blaue Vektor endet bei , der orangefarbene bei , und der violette Vektor ist das Residuum . - data: [ { points: [ { x: 0, y: 0, z: 0 }, { x: 4, y: 2, z: 1 }, { x: 6, y: 3, z: 1.5 } ], color: "#0284c7", cone: { position: "end" }, showPoints: false, labels: [ { text: $$A\hat{x}$$, at: 2, offset: [0.5, 0.5, 0] } ] }, { points: [ { x: 0, y: 0, z: 0 }, { x: 2.5, y: 2, z: 1.5 }, { x: 5, y: 4, z: 3 } ], color: "#d97706", cone: { position: "end" }, showPoints: false, labels: [ { text: $$b$$, at: 2, offset: [0.5, 0, 0.5] } ] }, { points: [ { x: 5, y: 4, z: 3 }, { x: 5.5, y: 3.5, z: 2.25 }, { x: 6, y: 3, z: 1.5 } ], color: "#9333ea", cone: { position: "end" }, showPoints: false, labels: [ { text: $$A\hat{x}-b$$, at: 1, offset: [0, -0.5, 0] } ] } ] Visible text: [ { points: [ { x: 0, y: 0, z: 0 }, { x: 4, y: 2, z: 1 }, { x: 6, y: 3, z: 1.5 } ], color: "#0284c7", cone: { position: "end" }, showPoints: false, labels: [ { text: , at: 2, offset: [0.5, 0.5, 0] } ] }, { points: [ { x: 0, y: 0, z: 0 }, { x: 2.5, y: 2, z: 1.5 }, { x: 5, y: 4, z: 3 } ], color: "#d97706", cone: { position: "end" }, showPoints: false, labels: [ { text: , at: 2, offset: [0.5, 0, 0.5] } ] }, { points: [ { x: 5, y: 4, z: 3 }, { x: 5.5, y: 3.5, z: 2.25 }, { x: 6, y: 3, z: 1.5 } ], color: "#9333ea", cone: { position: "end" }, showPoints: false, labels: [ { text: , at: 1, offset: [0, -0.5, 0] } ] } ] Die Szene zeigt den Zielvektor, seine Projektion und das verbindende Residuum. Der blaue Vektor stellt den projizierten Punkt im Spaltenraum dar, nicht den gesamten Unterraum. Die Orthogonalitätsbedingung oben ist die exakte Aussage, durch die $$A\hat{x}$$ zum nächstgelegenen Punkt wird. Visible text: Die Szene zeigt den Zielvektor, seine Projektion und das verbindende Residuum. Der blaue Vektor stellt den projizierten Punkt im Spaltenraum dar, nicht den gesamten Unterraum. Die Orthogonalitätsbedingung oben ist die exakte Aussage, durch die zum nächstgelegenen Punkt wird. ## Ein kleines durchgerechnetes Beispiel Eine Konstante $$x$$ soll die drei Beobachtungen $$1$$, $$2$$ und $$6$$ möglichst gut darstellen. Dann gilt Visible text: Eine Konstante soll die drei Beobachtungen , und möglichst gut darstellen. Dann gilt ```math A=\begin{pmatrix}1\\1\\1\end{pmatrix},\qquad b=\begin{pmatrix}1\\2\\6\end{pmatrix} ``` und die Zielfunktion lautet Component: MathContainer Children: ```math F(x)=(x-1)^2+(x-2)^2+(x-6)^2 ``` ```math F'(x)=2(x-1)+2(x-2)+2(x-6)=6x-18 ``` Setzen wir die Ableitung gleich null, erhalten wir $$\hat{x}=3$$. Der angepasste Vektor und das Residuum sind Visible text: Setzen wir die Ableitung gleich null, erhalten wir . Der angepasste Vektor und das Residuum sind Component: MathContainer Children: ```math A\hat{x}=\begin{pmatrix}3\\3\\3\end{pmatrix} ``` ```math A\hat{x}-b=\begin{pmatrix}2\\1\\-3\end{pmatrix} ``` Die Residualkomponenten summieren sich zu null: ```math A^{\mathsf T}(A\hat{x}-b)=2+1-3=0 ``` Damit ist die Normalgleichung erfüllt. ## Andere Residualnormen Die gewählte Norm bestimmt, welche Fehlerart bei der Anpassung im Vordergrund steht. | Zielfunktion | Was sie steuert | | --- | --- | | $$\displaystyle\min_x\|Ax-b\|_2^2=\min_x\sum_{i=1}^{m}(Ax-b)_i^2$$ | Bestraft große Residuen quadratisch und ergibt die gewöhnliche Projektion nach kleinsten Quadraten. | | $$\displaystyle\min_x\|Ax-b\|_1=\min_x\sum_{i=1}^{m}\lvert(Ax-b)_i\rvert$$ | Verwendet eine lineare Strafe, sodass ein vereinzeltes großes Residuum weniger Einfluss hat als beim quadrierten Verlust. | | $$\displaystyle\min_x\|Ax-b\|_\infty=\min_x\max_{1\le i\le m}\lvert(Ax-b)_i\rvert$$ | Minimiert das größte absolute Residuum. | Visible text: | Zielfunktion | Was sie steuert | | --- | --- | | | Bestraft große Residuen quadratisch und ergibt die gewöhnliche Projektion nach kleinsten Quadraten. | | | Verwendet eine lineare Strafe, sodass ein vereinzeltes großes Residuum weniger Einfluss hat als beim quadrierten Verlust. | | | Minimiert das größte absolute Residuum. | Die Formulierungen mit $$\ell_1$$ und $$\ell_\infty$$ lassen sich als lineare Programme schreiben. Ihre Eignung hängt weiterhin vom Entstehungsprozess der Daten und vom relevanten Fehlerkriterium der Anwendung ab. Visible text: Die Formulierungen mit und lassen sich als lineare Programme schreiben. Ihre Eignung hängt weiterhin vom Entstehungsprozess der Daten und vom relevanten Fehlerkriterium der Anwendung ab. ## Kleinste Quadrate zuverlässig berechnen Hat $$A$$ vollen Spaltenrang, ist der Ausgleichsvektor eindeutig. Aus der Normalgleichung folgt dann Visible text: Hat vollen Spaltenrang, ist der Ausgleichsvektor eindeutig. Aus der Normalgleichung folgt dann ```math \hat{x}=(A^{\mathsf T}A)^{-1}A^{\mathsf T}b ``` Diese Identität ist für die Analyse nützlich. Das explizite Bilden der Inversen ist jedoch nicht das bevorzugte numerische Verfahren. In der Praxis: - verwendet man eine QR-Zerlegung für ein stabiles Ausgleichsproblem mit vollem Rang - verwendet man eine SVD, wenn Rangmangel oder schlechte Konditionierung wichtig sind - verwendet man die Pseudoinverse, um bei mehreren Minimierern die Lösung mit kleinster Norm auszuwählen Es gibt außerdem eine präzise statistische Interpretation. Im Modell ```math b=Ax_*+\varepsilon,\qquad \varepsilon\sim\mathcal{N}(0,\sigma^2I) ``` mit festem $$A$$ und unabhängigen gaußverteilten Fehlern gleicher Varianz ist die Methode der kleinsten Quadrate der Maximum-Likelihood-Schätzer für $$x_*$$. Korrelierte Fehler oder unterschiedliche Varianzen erfordern eine andere Gewichtung statt der uneingeschränkten gewöhnlichen Ausgleichsformel. Visible text: mit festem und unabhängigen gaußverteilten Fehlern gleicher Varianz ist die Methode der kleinsten Quadrate der Maximum-Likelihood-Schätzer für . Korrelierte Fehler oder unterschiedliche Varianzen erfordern eine andere Gewichtung statt der uneingeschränkten gewöhnlichen Ausgleichsformel.