\documentclass[12pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
%\usepackage{graphicx}

\thispagestyle{empty}

\title{}
\author{}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{../#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\noindent §72: METHODE DER KLEINSTEN QUADRATE \\[0.8cm]
72.1 Problemstellung \\
In einem Experiment interessiert man sich für die Beziehung zwischen 2 Variablen $x$ und $y$. Hierzu hat man viele Wertepaare $(x_1,y_1),...,(x_n, y_n)$ gemessen. Die Messungen können Fehler in Form von statistischen Fluktuationen enthalten. Man möchte nun die Beziehung zwischen $x$ und $y$ durch ein einfaches Polynom
$$y=f(x)=\sum_{k=1}^m a_k x{k-1}$$
approximieren (z.B. $m=2$:Gerade, $m=3$: Parabel) und sucht die \glqq optimalen\grqq\ Koeffizienten $a_1,...,a_m$. \\[0.5cm]
72.2 Methode der kleinsten Quadrate \\
Jede der $n$ Messungen $(x_i,y_i)$ beschreibt eine Gleichung für die Unbekannten $a_1,...,a_m$:
\begin{eqnarray*}
	a_1+a_2x_1 + ... + a_m x_1^{m-1} & = & y_1 \\
	\vdots & & \\
	a_1+a_2x_n + ... + a_m x_n^{m-1} & = & y_n
\end{eqnarray*}
Im Allgemeinen hat man sehr viel mehr Gleichungen als Unbekannte ($n>>m$), und das lineare Gleichungssystem
$$\underbrace{\left(\begin{array}{cccc}1 & x_1 & \cdots & x_1^{m-1} \\ \vdots & & & \vdots \\ 1 & x_n & \cdots & x_n^{m-1}\end{array}\right)}_{M \in \SetR^{n \times m}} \underbrace{\left(\begin{array}{c}a_1 \\ \vdots \\ a_m\end{array}\right)}_{a \in \SetR^m} = \underbrace{\left(\begin{array}{c}y_1 \\ \vdots \\ y_n\end{array}\right)}_{y \in \SetR^n}$$
ist inkonsistent, d.h. einzelne Gleichungen widersprechen sich. \\
Beispielsweise kann man nicht erwarten, dass 50 Messwerte exakt auf einer Geraden liegen ($n=50, m=2$). \\
Da $Ma=y$ nicht exakt lösbar ist, sucht man statt dessen eine \glqq Lösung\grqq\ $a^*$, die den quadratischen Fehler
$$|Ma-y|^2 = \left(\sum_{k=1}^m a_k x_1^{k-1} - y_1\right)^2 + ... + \left(\sum_{k=1}^m a_k x_n^{k-1} - y_n\right)^2$$
minimiert. \\
Die Koeffizienten $a_1,...,a_m$ bestimmen dann die Ausgleichskurve (Regressionskurve)
$$y=\sum_{k=1}^m a_k x^{k-1}$$
72.3 Minimierung des quadratischen Fehlers \\
Wir suchen das Minimum der Funktion
\begin{eqnarray*}
	f(a_1,...,a_m) & = & |Ma-y|^2 \\
	& = & (Ma-y)^T(Ma-y) \\
	& = & (a^TM^T-y^T)(Ma-y) \\
	& = & a^TM^TMa - a^TM^Ty - \underbrace{y^TMa}_{a^TM^Ty} + y^Ty \\
	& = & a^TM^TMa - 2a^TM^Ty + y^Ty
\end{eqnarray*}
Notwendige Bedingung:
\begin{eqnarray*}
	0 \stackrel{!}{=} \nabla_a f := \left(\begin{array}{c}\frac{\partial f}{\partial a_1} \\ \vdots \\ \frac{\partial f}{\partial a_m}\end{array}\right) & = & M^TMa + \underbrace{a^TM^TM}_{M^TMa \text{ da } M^TM \text{ symmetrisch}} - 2M^Ty \\
	& = & 2M^TMa-2M^Ty
\end{eqnarray*}
Die Lösung $a^*$ löst also die so genannte Normalengleichung
$$M^TMa = M^Ty$$
Dies ist ein System aus $m$ Gleichungen mit $m$ Unbekannten $a_1,...,a_m$. Ist $M^TM$ invertierbar, gilt:
$$a^* = (M^TM)^{-1} M^Ty$$
Man nennt
$$M^+ := (M^TM)^{-1} M^T$$
die Pseudoinverse (Moore-Penrose-Inverse) der (nicht invertierbaren!) $n \times m$-Matrix M. \\[0.5cm]
72.4 Bemerkungen:
\begin{enumerate}[(a)]
	\item $a^*$ ist tatsächlich ein Minimum: \\
		Die Hesse-Matrix $H_af=2M^TM$ ist positiv semidefinit:
		$$x^T2M^TMx = 2(Mx)^TMx =2|Mx|^2 \ge 0 \; \forall x$$
		Da $M^TM$ invertierbar sein soll, ist $H_af$ sogar positiv definit. Nach 57.5 folgt also: $a^*$ ist Minimum.
	\item Man kann zeigen, dass $M^TM$ invertierbar ist, falls $rang(M) = m$, d.h. es gibt $m$ der $n$ Gleichungen des Systems $Ma=b$, die linear unabhängig sind.
	\item Wir haben lso am Beispiel der Ausgleichsrechnung ein allgemeines Verfahren hergeleitet, um ein überbestimmtes (und i.A. inkonsistentes) Gleichungssystem zu \glqq lösen\grqq :
\end{enumerate}
72.5 Satz: (Pseudolösung überbestimmter Gleichungssysteme) \\
Sei $n>m$, $A \in \SetR^{n \times m}$, $rang(A) = m$ und $b \in \SetR^n$. Falls das überbestimmte lineare Gleichungssystem
$$Ax=b$$
inkonsistent ist, ist es nicht exakt lösbar. Es gibt jedoch eine eindeutig bestimmte Pseudolösung $x^*$, die den quadratischen Fehler $|Ax-b|^2$ minimiert:
$$x^* = A^+b$$
mit der Pseudoinversen $A^+ = (A^TA)^{-1}A^T$. \\[0.5cm]
72.6 Bemerkung: \\
Pseudolösungen spielen auch in der Informatik eine große Rolle. Überbestimmte Gleichungssysteme treten z.B. bei der Suche in Internetdatenbanken auf (Prof. Weikum: Informationssysteme). \\[0.5cm]
72.7 Beispiel: \\
Bestimme mit der Methode der kleinsten Quadrate die Regressionsgerade durch die 4 Punkte
$$(0,1), (1,3), (2,4), (3,4)$$
Lösung: Wir suchen die Koeffizienten $a_1,a_2$ der Geradengleichung
$$y=a_1+a_2x$$
Hierzu haben wir 4 Bestimmungsgleichungen
\begin{eqnarray*}
	a_1 + 0 \cdot a_2 & = & 1 \\
	a_1 + 1 \cdot a_2 & = & 3 \\
	a_1 + 2 \cdot a_2 & = & 4 \\
	a_1 + 3 \cdot a_2 & = & 4
\end{eqnarray*}
Das überbestimmte Gleichungssystem lautet:
$$Ma=y$$ mit
$$M = \left(\begin{array}{cc}1 & 0 \\ 1 & 1 \\ 1 & 2 \\ 1 & 3\end{array}\right), \quad a= \left(\begin{array}{c}a_1 \\ a_2\end{array}\right), \quad y = \left(\begin{array}{c}1 \\ 3 \\ 4 \\ 4\end{array}\right)$$
\begin{eqnarray*}
	\Rightarrow M^TM & = & \left(\begin{array}{cccc}1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3\end{array}\right) \cdot \left(\begin{array}{cc}1 & 0 \\ 1 & 1 \\ 1 & 2 \\ 1 & 3\end{array}\right) \\
	& = & \left(\begin{array}{cc}4 & 6 \\ 6 & 14\end{array}\right)
\end{eqnarray*}
Nach kurzer Rechnung erhält man:
$$(M^TM)^{-1} = \frac{1}{10} \left(\begin{array}{rr}7 & -3 \\ -3 & 2\end{array}\right)$$
Damit lautet die Pseudolösung von $Ma=y$:
\begin{eqnarray*}
	a^* = \left(\begin{array}{c}a_1 \\ a_2\end{array}\right) & = & (M^TM)^{-1}M^Ty \\
	& = & \frac{1}{10} \left(\begin{array}{rr}7 & -3 \\ -3 & 2\end{array}\right) \left(\begin{array}{cccc}1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3\end{array}\right) \left(\begin{array}{c}1 \\ 3 \\ 4 \\ 4\end{array}\right) \\
	& = & \frac{1}{10}\left(\begin{array}{rr}7 & -3 \\ -3 & 2\end{array}\right) \left(\begin{array}{c}12 \\ 23\end{array}\right) \\
	& = & \frac{1}{10} \left(\begin{array}{c}15 \\ 20\end{array}\right) \\
	& = & \left(\begin{array}{c}1.5 \\ 1\end{array}\right)
\end{eqnarray*}
Die Ausgleichsgerade ist somit $$y=1.5+x$$
Bemerkung: \\
$\displaystyle M^TM = \left(\begin{array}{cc}4 & 6 \\ 6 & 14\end{array}\right)$ ist invertierbar, da
\begin{eqnarray*}
	det(M^TM) & = & 4 \cdot 14 - 6 \cdot 6 \\
	& = & 56 - 36 = 20 \ne 0
\end{eqnarray*}

\end{document}
