Überbestimmte lineare Systeme

Mehr Gleichungen als Unbekannte

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. Ein solches System kann eine exakte Lösung besitzen. Messdaten liegen meist nicht genau auf dem gewählten Modell.

Quadratische Anpassung an sieben Messwerte

Betrachten wir $7$ Datenpunkte, an die ein quadratisches Polynom angepasst werden soll.

Die Beobachtungen sind:

Gesucht ist eine Parabel der Form:

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.

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

Matrixform

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

Für ein quadratisches Modell mit $m$ Datenpunkten hat dieselbe Konstruktion die allgemeine Form:

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.

Eine exakte Lösung existiert genau dann, wenn $\operatorname{rank}(A)=\operatorname{rank}(A\mid b)$ gilt. Die Matrixgrößen allein entscheiden das nicht.

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

Dieser von null verschiedene Minor zeigt, dass $\operatorname{rank}(A\mid b)=4$ gilt.

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, bestimmen wir das Polynom, 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:

Dieses Kriterium gewichtet große Abweichungen stärker und liefert genau eine bestangepasste Parabel, weil $A$ vollen Spaltenrang besitzt. Die Normalgleichungen lauten

Die mittlere Gleichung liefert direkt den linearen Koeffizienten. Drücke mit der letzten Gleichung die Konstante durch den quadratischen Koeffizienten aus und setze das Ergebnis in die erste Gleichung ein.

Ihre Lösung ist

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

Der Residuenvektor $r$ erfüllt

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.

Die Kurve zeigt das angepasste Modell, die Punkte markieren die Beobachtungen. Drehe oder vergrößere die Darstellung und vergleiche jeden Punkt mit der Kurve. Der vertikale Unterschied ist das Residuum beim selben Zeitwert.