# Überbestimmte lineare Systeme > 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/lineare-gleichungssysteme Source: https://raw.githubusercontent.com/nakafaai/aksara/16d6b8e869d1a277313c65bbfc4b4a83efe77a46/packages/corpus/material/lesson/ai-ds/linear-methods/system-linear-equation/de.mdx Stelle aus Daten ein überbestimmtes lineares System auf und verstehe, warum die kleinsten Quadrate bei fehlender exakter Lösung das bestangepasste Polynom liefern. --- ## Überbestimmte lineare Gleichungssysteme Angenommen, wir möchten eine Kurve an Messdaten anpassen. Häufig gibt es mehr Beobachtungen als Modellparameter. Schreiben wir für jede Beobachtung eine Gleichung auf, entsteht ein **überbestimmtes lineares System**. Ein System heißt überbestimmt, wenn die Anzahl $$m$$ der Gleichungen größer als die Anzahl $$n$$ der Unbekannten ist, also $$m > n$$ gilt. Dadurch ist eine exakte Lösung nicht automatisch ausgeschlossen. Messdaten liegen jedoch meist nicht genau auf dem gewählten Modell. Visible text: Ein System heißt überbestimmt, wenn die Anzahl der Gleichungen größer als die Anzahl der Unbekannten ist, also gilt. Dadurch ist eine exakte Lösung nicht automatisch ausgeschlossen. Messdaten liegen jedoch meist nicht genau auf dem gewählten Modell. ## Reales Beispiel mit quadratischem Polynommodell Betrachten wir $$7$$ Datenpunkte, an die ein quadratisches Polynom angepasst werden soll. Visible text: Betrachten wir Datenpunkte, an die ein quadratisches Polynom angepasst werden soll. Die Beobachtungen sind: | $$i$$ | $$1$$ | $$2$$ | $$3$$ | $$4$$ | $$5$$ | $$6$$ | $$7$$ | |---|---|---|---|---|---|---|---| | $$t_i$$ | $$-3$$ | $$-2$$ | $$-1$$ | $$0$$ | $$1$$ | $$2$$ | $$3$$ | | $$y_i$$ | $$-2{,}2$$ | $$-4{,}2$$ | $$-4{,}2$$ | $$-1{,}8$$ | $$1{,}8$$ | $$8{,}2$$ | $$15{,}8$$ | Visible text: | | | | | | | | | |---|---|---|---|---|---|---|---| | | | | | | | | | | | | | | | | | | Gesucht ist eine Parabel der Form: ```math y = a_2 \cdot t^2 + a_1 \cdot t + a_0 ``` Unbekannt sind die $$3$$ Parameter $$a_2$$ (quadratischer Koeffizient), $$a_1$$ (linearer Koeffizient) und $$a_0$$ (konstanter Term). Visible text: Unbekannt sind die Parameter (quadratischer Koeffizient), (linearer Koeffizient) und (konstanter Term). ## Aufstellen des Gleichungssystems Setzen wir jedes Paar $$(t_i,y_i)$$ in das Polynom ein, entsteht jeweils eine Gleichung. Die $$7$$ Beobachtungen liefern somit $$7$$ Gleichungen für nur $$3$$ unbekannte Koeffizienten. Visible text: Setzen wir jedes Paar in das Polynom ein, entsteht jeweils eine Gleichung. Die Beobachtungen liefern somit Gleichungen für nur unbekannte Koeffizienten. Component: MathContainer Children: ```math a_2 \cdot (-3)^2 + a_1 \cdot (-3) + a_0 = -2{,}2 ``` ```math a_2 \cdot (-2)^2 + a_1 \cdot (-2) + a_0 = -4{,}2 ``` ```math a_2 \cdot (-1)^2 + a_1 \cdot (-1) + a_0 = -4{,}2 ``` ```math a_2 \cdot 0^2 + a_1 \cdot 0 + a_0 = -1{,}8 ``` ```math a_2 \cdot 1^2 + a_1 \cdot 1 + a_0 = 1{,}8 ``` ```math a_2 \cdot 2^2 + a_1 \cdot 2 + a_0 = 8{,}2 ``` ```math a_2 \cdot 3^2 + a_1 \cdot 3 + a_0 = 15{,}8 ``` Nach dem Auswerten der Potenzen von $$t_i$$ ergibt sich: Visible text: Nach dem Auswerten der Potenzen von ergibt sich: Component: MathContainer Children: ```math 9a_2 - 3a_1 + a_0 = -2{,}2 ``` ```math 4a_2 - 2a_1 + a_0 = -4{,}2 ``` ```math 1a_2 - 1a_1 + a_0 = -4{,}2 ``` ```math 0a_2 + 0a_1 + a_0 = -1{,}8 ``` ```math 1a_2 + 1a_1 + a_0 = 1{,}8 ``` ```math 4a_2 + 2a_1 + a_0 = 8{,}2 ``` ```math 9a_2 + 3a_1 + a_0 = 15{,}8 ``` ## Matrixform Das obige Gleichungssystem kann in der Matrixform $$A \cdot x = b$$ geschrieben werden. Visible text: Das obige Gleichungssystem kann in der Matrixform geschrieben werden. ```math \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} \begin{pmatrix} a_2 \\ a_1 \\ a_0 \end{pmatrix} = \begin{pmatrix} -2{,}2 \\ -4{,}2 \\ -4{,}2 \\ -1{,}8 \\ 1{,}8 \\ 8{,}2 \\ 15{,}8 \end{pmatrix} ``` Für ein quadratisches Modell mit $$m$$ Datenpunkten hat dieselbe Konstruktion die allgemeine Form: Visible text: Für ein quadratisches Modell mit Datenpunkten hat dieselbe Konstruktion die allgemeine Form: ```math \begin{pmatrix} t_1^2 & t_1 & 1 \\ \vdots & \vdots & \vdots \\ t_m^2 & t_m & 1 \end{pmatrix} \begin{pmatrix} a_2 \\ a_1 \\ a_0 \end{pmatrix} = \begin{pmatrix} y_1 \\ \vdots \\ y_m \end{pmatrix} ``` ## Warum es keine exakte Lösung gibt In diesem Beispiel hat die Matrix $$A$$ die Größe $$7 \times 3$$, der Koeffizientenvektor $$x$$ die Größe $$3 \times 1$$. Es gibt also $$7$$ Gleichungen für $$3$$ Unbekannte. Visible text: In diesem Beispiel hat die Matrix die Größe , der Koeffizientenvektor die Größe . Es gibt also Gleichungen für Unbekannte. Ob eine exakte Lösung existiert, folgt nicht allein aus den Dimensionen, sondern aus den Rängen der Matrizen. Die drei Spalten von $$A$$ sind linear unabhängig. Ein Polynom $$c_2t^2+c_1t+c_0$$ vom Grad höchstens $$2$$, das an allen sieben verschiedenen Werten $$t_i$$ verschwindet, muss nämlich das Nullpolynom sein. Daher gilt $$\operatorname{rank}(A)=3$$. Visible text: Die drei Spalten von sind linear unabhängig. Ein Polynom vom Grad höchstens , das an allen sieben verschiedenen Werten verschwindet, muss nämlich das Nullpolynom sein. Daher gilt . Durch das Anfügen von $$b$$ entsteht die erweiterte Matrix $$(A\mid b)$$. Bereits ihre ersten vier Zeilen liefern den von null verschiedenen Minor Visible text: Durch das Anfügen von entsteht die erweiterte Matrix . Bereits ihre ersten vier Zeilen liefern den von null verschiedenen Minor ```math \det\begin{pmatrix}9&-3&1&-2{,}2\\4&-2&1&-4{,}2\\1&-1&1&-4{,}2\\0&0&1&-1{,}8\end{pmatrix}=-\frac45 ``` und somit $$\operatorname{rank}(A\mid b)=4$$. Visible text: und somit . Da $$\operatorname{rank}(A) \ne \operatorname{rank}(A\mid b)$$ gilt, **hat das System keine exakte Lösung**. Kein einziges quadratisches Polynom verläuft durch alle $$7$$ Beobachtungen. Visible text: Da gilt, **hat das System keine exakte Lösung**. Kein einziges quadratisches Polynom verläuft durch alle Beobachtungen. ## Lösung mit kleinsten Quadraten Besitzt ein überbestimmtes System keine exakte Lösung, lässt sich stattdessen das Polynom bestimmen, das den Beobachtungen im Sinne der **kleinsten Quadrate** am nächsten liegt. Für die Beobachtung $$i$$ ist das vertikale Residuum $$r_i = y_i-(a_2t_i^2+a_1t_i+a_0)$$. Die Methode der kleinsten Quadrate wählt die Koeffizienten so, dass die Summe der quadrierten Residuen minimal wird: Visible text: Für die Beobachtung ist das vertikale Residuum . Die Methode der kleinsten Quadrate wählt die Koeffizienten so, dass die Summe der quadrierten Residuen minimal wird: ```math \min_{a_2,a_1,a_0}\sum_{i=1}^{7}\left[y_i-(a_2t_i^2+a_1t_i+a_0)\right]^2 ``` Dieses Kriterium gewichtet große Abweichungen stärker und liefert genau eine bestangepasste Parabel, weil $$A$$ vollen Spaltenrang besitzt. Die Normalgleichungen lauten Visible text: Dieses Kriterium gewichtet große Abweichungen stärker und liefert genau eine bestangepasste Parabel, weil vollen Spaltenrang besitzt. Die Normalgleichungen lauten Component: MathContainer Children: ```math A^TA=\begin{pmatrix}196&0&28\\0&28&0\\28&0&7\end{pmatrix} ``` ```math A^Tb=\begin{pmatrix}136\\\frac{424}{5}\\\frac{67}{5}\end{pmatrix} ``` Ihre Lösung ist Component: MathContainer Children: ```math \hat x=\begin{pmatrix}\hat a_2\\\hat a_1\\\hat a_0\end{pmatrix}=\begin{pmatrix}\frac{103}{105}\\\frac{106}{35}\\-\frac{211}{105}\end{pmatrix} ``` ```math \hat y(t)=\frac{103}{105}t^2+\frac{106}{35}t-\frac{211}{105} ``` Die angepassten Werte stimmen erwartungsgemäß nicht mit jeder Beobachtung überein. Der Residuenvektor lautet ```math r=b-A\hat x=\begin{pmatrix}\frac1{15}\\-\frac2{35}\\-\frac17\\\frac{22}{105}\\-\frac15\\\frac8{35}\\-\frac{11}{105}\end{pmatrix} ``` und erfüllt Component: MathContainer Children: ```math A^Tr=0 ``` ```math \lVert r\rVert_2^2=\frac{92}{525}\approx0{,}17524 ``` Die Gleichung $$A^Tr=0$$ besagt, dass der verbleibende Fehler zu jeder Spalte von $$A$$ orthogonal ist. Geometrisch ist $$A\hat x$$ die orthogonale Projektion von $$b$$ auf den Spaltenraum von $$A$$. Visible text: Die Gleichung besagt, dass der verbleibende Fehler zu jeder Spalte von orthogonal ist. Geometrisch ist die orthogonale Projektion von auf den Spaltenraum von . Überbestimmte Systeme treten in Technik und Naturwissenschaften häufig auf, weil Experimente viele Messwerte für Modelle mit wenigen Parametern liefern. Die Methode der kleinsten Quadrate nutzt alle Messwerte, ohne vorzugeben, verrauschte Daten passten exakt zum Modell.