AuK/Hilfsmittel Mathematik 1 SS09

Wiki-Quelltext dieser Seite.

== Exponentialfunktionen und Lineare Regression [Igor Geiger] ==

Bei der Analyse von Algorithmen zur Bestimmung des Mittleren 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 exponentiäl 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 nicht der 
durchschnittliche Aufwand des Algorithmus exakt bestimmen da man dazu einen exakten Anstieg braucht.
Dazu würd die entstandene Exponentialfunktion in ein Kartesiches Koordinatensystem mit einer 
logarithmischen y-Achse überführt.

Daher was 1 in der Normalen y-Achse wahr ist jetzt 10 in der neuen Achse,den der Logarithmus zur Basis 10 von 10 ist 1 usw.

Darstellung von <math> T(n)=10*2^n </math> im neuen System nach Gnuplot.
Im  Normalen System würde dies der Logarithmierung der ursprünglichen Funktion entsprechen:
<math>T(n)=log(T(n))</math>
<math>=log(2)*n+log(10)</math>

Darstellung von <math>T(n)=10*2^n</math> im logarithmischen System:

<gnuplot>
set logscale y
set ytics(1,10,100,1000,10000,100000,1000000,10000000)
plot [n=0:8] 10*2**n
</gnuplot>

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}^{r}(T(i)-a*i-b)(-i)->0 </math>

Ableitung nach b:

<math>2*\sum_{i}^{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>

== 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>

Funktionsgraph mit '''logarithmischer''' Achseneinteilung:

<gnuplot>
set log x
set log y
set xlabel "n"
set ylabel "T(n)"
plot 2*x**12+10*x**2+1234*x
</gnuplot>