AuK/Hilfsmittel Mathematik 1 SS09
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
== Autoren ==
''' Igor Geiger ,Ralf Bergmann'''
== Exponentialfunktionen und Lineare Regression ==
Bei der Analyse von Algorithmen zur Bestimmung des Aufwandes ,für eine bestimmte
Anzahl an Eingabegrößen,die von der Anwendung des Algorithmus abhängt,tritt eine Punktmenge
im Kartesischen Koordinatesystem auf,die exponentiel beschrieben werden kann.
In realen Meßungen ergibt sich aber meistens eine verworfene Punktmenge die einer Exponentialfunktion angenährt werden kann.Jedoch lässt sich anhand dieser Kurve der
Aufwand des Algorithmus nicht exakt bestimmen da man dazu einen exakten Anstieg braucht bzw. eine exakte Funktion.
Dazu würd die entstandene Punktmenge in ein Kartesiches Koordinatensystem mit einer
logarithmischen y-Achse überführt.
Darstellung von <math> T(n)=10*2^n </math> im neuen System nach Gnuplot.
Es entsteht folgende Gerade,Schnittpunkt bei y=10 mit der y-Achse:
Darstellung von <math>T(n)=10*2^n</math> im logarithmischen System:
<gnuplot>
set logscale y
set ytics(0,1,10,100,1000,10000,100000,1000000,10000000)
plot [n=0:8]10*2**n,10**n*10,79.43**n*31.62
</gnuplot>
Dies entspricht,vom Aussehen,der Geraden im normalen kartesischen Koordinatensystem:
<math>T(n)=log(T(n))</math>
<math>=log(2)*n+log(10)</math>
Desweiteren hat sich gezeigt das es viel einfacher ist eine Gerade im dargestellten Logarithmischen
Koordinatensystem anhand der eingetragenen Punkte zu verlegen als eine Exponentialfunktion im normalen Koordinatensystem zu bestimmen.
Die mathematische Methode zur Bestimmung einer Geraden im logarithmischen Koordinatensystem,anhand der verstreuten Messpunkte,nennt man '''Lineare Regression'''.
Die Gerade <math> f(n)=a*n+b </math> soll so bestimmt werden das der maximale Abstand zwischen der Geraden und den Messpunkten möglichst klein wird.
Mathematische Vorgehensweise:
<math>max|T(n)-(a*n+b)|->minimal</math>
Da es für jeden Messpunkt gelten muß,würd die gesuchte Funktion als Summe der Abstände der einzelnen Messpunkte dargestellt:
<math>\sum_{n}|T(n)-(a*n+b)|->minimal </math>
Von der entstandenen Funktion wird aber zur Bestimmung des Minimums die erste Ableitung benötigt
jedoch ist die Betragsfunktion an der Stelle <math>x=0</math> nicht stetig differenzierbar.
Dazu Quadriert man sie nach der Methode der kleinsten Fehlerquadrate von Gauss,dadurch wird sie
Differenzierbar aber die Suche nach dem Minimum wird dadurch nicht beeinflußt.
<math>\sum_{n}(T(n)-(a*n+b))^{2}->minimal </math>
Für das Minimum muß die erste Ableitung der obigen Funktion Null gesetzt werden.
<math>f'(x)=0</math>
Da man aber das Minimum nach a und b haben will muß man auch jeweils nach a und b ableiten.
Ableitung nach a:
<math>2*\sum_{i=1}^{r}(T(i)-a*i-b)(-i)->0 </math>
Ableitung nach b:
<math>2*\sum_{i=1}^{r}(T(i)-a*i-b)(-1)->0 </math>
Durch Vereinfachung erhält man die sogennante Normalengleichung:
<math>a*\sum_{i=1}^{r}i^{2}+b*\sum_{i=1}^{r}i=\sum_{i=1}^{r}i+T(i)</math>
<math>a*\sum_{i=1}^{r}i+r*b=\sum_{i=1}^{r}i=\sum_{i=1}^{r}T(i)</math>
Durch weiteres Umstellen nach a bzw. b erhält man die gewünschten Parameter für
die Regressionsgerade.
Umformung nach a:
<math>a*\sum_{i=1}^{r}i+r*b=\sum_{i=1}^{r}i=\sum_{i=1}^{r}T(i)</math>
<math>r*b=\sum_{i=1}^{r}T(i)-a*\sum_{i=1}^{r}i</math>
<math>b=\frac{\sum_{i=1}^{r}T(i)-a*\sum_{i=1}^{r}i}{r}</math>
<math>a*\sum_{i=1}^{r}i^{2}+(\frac{\sum_{i=1}^{r}T(i)-a*\sum_{i=1}^{r}i}{r})\sum_{i=1}^{r}i
=\sum_{i=1}^{r}i*T(i)</math>
<math>\frac{r*a*\sum_{i=1}^{r}i^{2}+\sum_{i=1}^{r}i*(\sum_{i=1}^{r}T(i)-a\sum_{i=1}^{r}i)}{r}=\sum_{i=1}^{r}i*T(i)</math>
<math>r*a*\sum_{i=1}^{r}i^{2}+\sum_{i=1}^{r}i*(\sum_{i=1}^{r}T(i)-a\sum_{i=1}^{r}i)=r\sum_{i=1}^{r}i*T(i)</math>
<math>a*(r*\sum_{i=1}^{r}i^{2}-(\sum_{i=1}^{r}i)^{2}))=r*\sum_{i=1}^{r}i*T(i)-\sum_{i=1}^{r}i*\sum_{i=1}^{r}T(i)</math>
<math>a=\frac{r*(\sum_{i=1}^{r}i*T(i))-(\sum_{i=1}^{r}i)*(\sum_{i=1}^{r}T(i))}{r*\sum_{i=1}^{r}i^{2}-(\sum_{i=1}^{r}i)^{2}}</math>
<math>b=\frac{(\sum_{i=1}^{r}i^{2})*(\sum_{i=1}^{r}T(i))-(\sum_{i=1}^{r}i*T(i))*\sum_{i=1}^{r}i}{r*\sum_{i=1}^{r}i^{2}-(\sum_{i=1}^{r}i)^{2}}</math>
Somit erhält man die Parameter a und b für die Regressionsgerade:
'''Beispielrechnung:'''
folgende Meßwerte:
T(1)=3
T(2)=6
T(3)=7
T(4)=9
T(5)=11
In die Gleichung für a und b einsetzen!
<math>\sum_{i=1}^{r}i*T(i)=127</math>
<math>\sum_{i=1}^{r}i=15</math>
<math>\sum_{i=1}^{r}T(i)=36</math>
<math>\sum_{i=1}^{r}i^{2}=55</math>
<math>(\sum_{i=1}^{r}i)^{2}=225</math>
<math>\frac{(5*127)-(15*36)}{(5*55)-15^{2}}=1.9</math>
<math>\frac{(36*55)-(127*15)}{(5*55)-15^{2}}=1.5</math>
Parameter für die Regressionsgerade im kartesischen Koordinatensystem.
<math>a=1.9</math>
<math>b=1.5</math>
<math>f(n)=1.9n+1.5</math>
Würde man die folgenden Messpunkte im logarithmischen Koordinatensystem als ansteigende Gerade erkennen so wäre die Gleichung zur Exponentialfunktion dieser Geraden
<math>T(n)=a*b^{n}</math>
Wobei dan aber gelten muß : <math>b=log </math>(das a von der Regressionsgeraden oben)
dabei ergibt sich für unser Beispiel folgende Exponentialfunktion:
<math>T(n)=1.5*0.278^{n} </math>
<language>Scheme</language>
== Polynomfunktion ==
Ein Graph wird zur Gerade wenn beide Achsen logarithmisch eingestellt sind.
<br>Bei Funtionen folgender Gestalt:
* <math>T(n) = c*n^k, k \geq 1</math>
Diese Funtion kann weiter beschrieben werden als:
* <math>T(n) = c_1*n^{k_1} + c_2*n^{k_2} + ... + c_i*n^{k_i}</math>
Daraus ergibt sich folgender Funktionsgraph mit '''normaler''' Achseneinteilung für:<br>
* <math>2*n^{12}+10*x^2+1234*x</math>
<gnuplot>
set xrange [0:10]
set xlabel "n"
set ylabel "T(n)"
plot 2*x**12+10*x**2+1234*x
</gnuplot>
Dieser Graph ist keine Gerade, deshalb müssen wir die logarithmische Achseneinteilung wählen um auf das gewünschte Ergebnis zu kommen.<br>
Funktionsgraph mit '''logarithmischer''' y-Achseneinteilung:
<gnuplot>
set xrange [1:10]
set yrange [1000:1*10**13]
set log y
set xlabel "n"
set ylabel "T(n)"
plot 2*x**12+10*x**2+1234*x
</gnuplot>
Funktionsgraph mit '''logarithmischer''' x- und y-Achseneinteilung:
<gnuplot>
set xrange [1:10]
set yrange [1000:1*10**13]
set log xy
set xlabel "n"
set ylabel "T(n)"
plot 2*x**12+10*x**2+1234*x
</gnuplot>
Bei diesen Graphen handelt es sich um keine Gerade weil eine Summe gebildet wird.<br>
Schließlich kann man davon ausgehen das nicht bei jeder Funktion eine Gerade ensteht.<br>
Deshalb sind andere Untersuchungsmethoden notwendig um auf das gewünschte Ergebnis zu kommen.
Polynomfunktionen bestehen aus mehreren Basisfunktionen der folgenden Form:
* <math>f(x)=c_0*g_0(x)+c_1*g_1(x)+ ... +c_m*g_m(x)</math>
Die Lösung des Problems ergibt sich durch Anwenden der Methode der kleinsten
Fehlerquadrate auf die Polynomfunktion.<br>
Die Methode der kleinsten Fehlerquadrate angewandt auf die Formel:
* <math>F(c_0,c_1,...,c_m)=\sum_{k=1}^{n}(\sum_{k=0}^{m}c_ig_i(x_k)-y_k)^2\rightarrow min</math>
Das heißt die Summe der Abstände (n Messpaare, also n Abstände) zwischen
der gesuchten Funktion und den Messwerten soll minimal werden. Dazu bildet
man die Ableitung und setzt diese Null.
* <math>\frac{\delta F}{\delta c_i}=2\sum_{k=1}^{n}(\sum_{k=0}^{m}c_ig_i(x_k)-y_k)*g_i(x_k)=0</math>
Dazu multipliziert man die Ableitung aus und bringt <math>y_k</math> auf die rechte Seite.
* <math>\sum_{i=0}^{m}(\sum_{k=1}^{n}g_i(x_k)*g_i(x_k))=\sum_{k=1}^{n}y_k*g_j(x_k)</math>
Dabei ist <math>g_j</math> eine der Basisfunktionen zwischen 0 und m. Um eine Lösung für
alle c zu erhalten, trägt man die Formeln in ein lineares Gleichungssystem
ein. Um dieses dann zu lösen, werden für <math>g_j</math> alle Basisfunktionen angenommen.
Um das besser repräsentieren zu können, wählt man eine Darstellung
mit Hilfe von Matrizen
* <math>A=\begin{pmatrix} g_0(x_1) & g_1(x_1) & \cdots & g_m(x_1) \\
g_0(x_2) & g_1(x_2) & \cdots & g_m(x_2) \\
\vdots & \vdots & \cdots & \vdots \\
g_0(x_n) & g_1(x_n) & \cdots & g_m(x_n)\end{pmatrix} </math>
Der Faktor <math>g_j</math> ist die Transpornierte der Matrix A. Daraus ergibt sich die
Form
* <math>A^TA\vec c = A^T \vec y</math>
Damit kann man dieses Gleichungssystem nach <math>\vec c</math> lösen und erhält die Faktoren
für die einzelnen Polynome.
* <math>\vec c=(c_0,c_1,...,c_m)^T</math>
'''Maple-Worksheet''' (Maple 11)
restart:
with(linalg):
with(plots):
x := [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
y := [0, 4, 9, 16, 25, 36, 49, 64, 81, 100];
g := x->x^0, x->x, x->x^2, x->x^3;
n := nops(x);
m := nops([g])-1;
A := matrix(n, m+1, 0):
c := vector(m, 0):
for k to n do
for i to m+1 do
A[k, i] := g[i](x[k]);
od:
od:
evalm(A);
AT := transpose(A):
left := evalm(AT&*A):
right := (AT&*y):
c := evalf(linsolve(left, right));
x:=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
y:=[0, 4, 9, 16, 25, 36, 49, 64, 81, 100]
2 3
g:=x -> 1, x -> x, x -> x , x -> x
n:=10
m:=3
c:=[0.1762237762,2.635198135,0.8671328671,0.008158508158]
h := 0:
for i from 0+1 to m+1 do h := h+c[i]*g[i] od:
pkt := [seq([x[i], y[i]], i = 1 .. n)]:
bild1 := plot(pkt, 0 .. x[n], 0 .. y[n], style = point, symbol = diamond);
bild2 := plot(h(xx), xx = x[1] .. x[n], color = BLACK);
display(bild1, bild2, labels = ['x', 'h(x)']);
== Übungsaufgaben ==
[[Aufgaben]]
== Folien ==
* Hier sind die Folien zur Vorlesung
<document>Hilfsmittel_Mathematik1_v1.pdf</document>