Überbestimmte lineare Systeme

Überbestimmte lineare Gleichungssysteme

Überbestimmte lineare Systeme

Ü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.

Reales Beispiel mit quadratischem Polynommodell

Betrachten wir $7$ 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$

Gesucht ist eine Parabel der Form:

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).

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.

a_2 \cdot (-3)^2 + a_1 \cdot (-3) + a_0 = -2{,}2

Nach dem Auswerten der Potenzen von $t_i$ ergibt sich:

9a_2 - 3a_1 + a_0 = -2{,}2

Matrixform

Das obige Gleichungssystem kann in der Matrixform $A \cdot x = b$ geschrieben werden.

\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:

\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.

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$ .

Durch das Anfügen von $b$ entsteht die erweiterte Matrix $(A\mid b)$ . Bereits ihre ersten vier Zeilen liefern den von null verschiedenen Minor

\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$ .

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.

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:

\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

A^TA=\begin{pmatrix}196&0&28\\0&28&0\\28&0&7\end{pmatrix}

Ihre Lösung ist

\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}

Die angepassten Werte stimmen erwartungsgemäß nicht mit jeder Beobachtung überein. Der Residuenvektor lautet

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

A^Tr=0

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$ .

Ü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.