AuK/Hilfsmittel Mathematik 1 SS09

Wiki-Quelltext dieser Seite.

'''<b>Autoren:</b>'''
 Michael Gäbler  - simigaeb@stud.hs-zigr.de
 Daniel Glaser 

== Approximation von Funktionen ==

<b> Was bedeutet Approximation? </b>

Approximation bezeichnet ein Näherungsverfahren im mathematischen Sinn.
Dabei ist Sie ein Hilfsmittel, die computergesteuerte Lösungsverfahren beschleunigen oder erst möglich machen kann.


Abbild eines Näherungsverfahrens mit gegebenen Messwerten:

[[Bild:Test2.jpg]]


In diesem Wiki-Thema geht es also darum, bei gegebenen Messpunkten, eine Funktion mithilfe eines Näherungsverfahrens zu ermitteln. <br>
Was es dabei für Möglichkeiten gibt und wie man es rechnerisch ausrechnen kann, dass soll der folgende Text klären.



== Exponentialfunktionen ==

Bei der Analyse von Algorithmen führen diese immer zu Kurven. Dabei tritt beim Näherungsverfahren eine Punktmenge im Kartesischen Koordinatensystem auf, die einer Exponentialfunktion angenähert werden kann. Um jedoch den Aufwand eines Algorithmus exakt bestimmen zu können, wird eine Gerade benötigt. Diese besitzt einen exakten Anstieg bzw. eine exakte Funktion. <br>
Damit eine Exponentialfunktion als Gerade dargestellt werden kann, wird diese in ein kartesisches Koordinatensystem mit einer logarithmischen y-Achse überführt.


Diese Funktionen besitzen im Allgemeinen folgende Form:

      <math> y = T \left(n \right) = a \cdot b^n,  </math> mit <math> b \geq 1 </math>
 

Der konstante Faktor a ist dabei der Schnittpunkt mit der y-Achse und b ist der Anstieg der Funktion.


Nach einer Umformung dieser Allgemeinen Funktion ergibt sich die Gleichung: 

   <math> log\ y = f \left(n \right) = log\ \left(a \cdot b^n \right) = n \cdot log\ b + log\ a </math>


Aus dieser Gleichung wird die Funktion als Gerade <math> z = f \left(n \right) = n \cdot \alpha + \beta, </math> mit <math> z = log\ y, \ \alpha = log\ b </math> (ist der Anstieg der Geraden) und <math> \beta =  log\ a\ </math>(Ist der Schnittpunkt mit der y-Achse), dargestellt. 


=== Praxis ===
<br>
Wie geht man nun in der Praxis vor?<br>

In der Praxis macht man dies genau umgekehrt. Zuerst zeichnet man die ermittelten Daten der Wertepaare in ein Koordinatensystem mit logarithmisch eingeteilter y-Achse ein. <br> Wenn sich dabei eine Gerade ergibt, so kann daraus die Funktion <math> y = T \left(n \right) = a \cdot b^n </math> bestimmt werden. 


Mit Hilfe von <b> Gnuplot </b> kann man diese Funktionen grafisch darstellen. 

Beispiel: 

Darstellung der Funktionen <math> T \left(n \right)= 10 \cdot 2^n; \ T \left(n \right)=10000 \cdot 2^n </math> und <math> T \left(n \right)=10^n </math>

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

== Effizienz von Algorithmen: Exponentieller Aufwand ==

Des Weiteren stellen Exponentielle Funktionen mit der Form: 
                        
               <math> T= f \left(x \right) = a^b^ \cdot ^x </math> 

in einem kartesischen Koordinatensystem mit einer logarithmischen y-Achse eine Gerade dar.   
<br><br>
Beispiel:<br>
Darstellung der Funktionen: <math> T \left(x \right)= exp x; \ T \left(x \right)=exp 4^ \cdot ^x; \ T \left(x \right)=3^x; \ T \left(x \right)=10 \cdot 3^x; \ T \left(x \right)=10^2^ \cdot ^x </math>

<gnuplot>
set logscale y
set xlabel "x"
set ylabel "T(x)"
set ytics(1,10,100,1000,10000,100000,1000000,10000000,1e+8,1e+9)
plot [x=0:5]exp(x),exp(4*x), 3**x, 10*3**x, 10**(2*x)
</gnuplot>

== Lineare Regression ==

Im Logarithmischen Koordinatensystem ist es viel einfacher eine Gerade anhand der eingetragenen Punkte zu verlegen als eine Exponentialfunktion im normalen Koordinatensystem zu bestimmen. 

=== Definition: ===

 Als Lineare Regression bezeichnet man die mathematische Methode zur Bestimmung einer Geraden anhand der verstreuten Messpunkte. 
Dabei wird die Gerade <math> y = f \left(n \right) = a \cdot n+b </math> gesucht. <br>
Ziel der Linearen Regression ist es dabei, die Gerade so zu bestimmen, dass der maximale Abstand zwischen der Geraden und den Messpunkten möglichst klein ist. 


=== Herleitung der Formeln für die Lineare Regression ===


Bei der Herleitung geht man wie folgt vor: 

 <math>max|T \left(n \right)- \left(a \cdot n+b \right)| \rightarrow minimal</math>


Durch diese Formel besteht die Gefahr, dass wenn nur ein einziger Messpunkt erheblich daneben liegt, die Gerade sehr ungenau wird. 
Da es Allerdings für jeden Messpunkt gelten muss, so wird die gesuchte Funktion als Summe der Abstände der einzelnen Messpunkte dargestellt:

 <math>\sum \limits _{n} {|T \left(n \right)- \left(a \cdot n+b \right)|} \rightarrow minimal </math>


Durch diese Formel kommt allerdings das Problem auf, dass zur Bestimmung des Minimums die erste Ableitung benötigt wird. Allerdings ist die Betragsfunktion an der Stelle x = 0 nicht differenzierbar.


==== Methode der kleinsten Fehlerquadrate ====


Bei der <b> Methode der kleinsten Fehlerquadrate </b> von Gauss, wird die Formel Quadriert. Dadurch ist diese Differenzierbar, aber die Suche nach dem Minimum wird dadurch nicht beeinflusst.

 <math>\sum \limits _{n}{(T \left(n \right)- \left(a \cdot n+b \right))^{2}} \rightarrow minimal </math>

Um das Minimum zu bestimmen, wird nun die erste Ableitung gebildet.
<math>f' \left(x \right)=0</math><br><br>
Da man das Minimum nach a und b benötigt, so muss jeweils nach a und b abgeleitet werden. 
<br><br>
Ableitung nach a:

<math>2 \cdot \sum \limits _{i=1}^r {\left(T \left(i \right)-a \cdot i-b \right) \left(-i \right)} \rightarrow 0 </math>
<br><br>
Ableitung nach b:

<math>2 \cdot \sum \limits _{i=1}^r {\left(T \left(i \right)-a \cdot i-b \right) \left(-1 \right)} \rightarrow 0 </math>


Durch Vereinfachung erhält man die sogennante Normalengleichung:


<math>a \cdot \sum \limits _{i=1}^r {i^{2}+b} \cdot \sum \limits _{i=1}^r {i} = \sum \limits _{i=1}^r {i+T \left(i \right)}</math>


<math>a \cdot \sum \limits _{i=1}^r {i+r \cdot b} = \sum \limits _{i=1}^r {i} = \sum \limits _{i=1}^r {T \left(i \right)}</math>


Durch Umstellen nach a bzw. b erhält man nun die gewünschten Parameter für die Regressionsgerade: 


<math>a \cdot \sum \limits _{i=1}^r {i+r \cdot b} = \sum \limits _{i=1}^r {i} = \sum \limits _{i=1}^r {T \left(i \right)}</math>


<math>r \cdot b = \sum \limits _{i=1}^r {T \left(i \right)-a \cdot \sum \limits _{i=1}^r {i}</math>


<math>b=\frac{\sum \limits _{i=1}^r {T \left(i \right)-a} \cdot \sum \limits _{i=1}^r {i}} r</math>


<math>a \cdot \sum \limits _{i=1}^r {i^{2}}+ \left(\frac{\sum \limits _{i=1}^r {T \left(i \right)-a} \cdot \sum \limits _{i=1}^r {i}}r \right)\cdot \sum \limits _{i=1}^r {i} = \sum \limits _{i=1}^r {i \cdot T \left(i \right)}</math>


<math>\frac{r \cdot a \cdot \sum \limits _{i=1}^r {i^{2}} + \sum \limits _{i=1}^r {i \cdot \left(\sum \limits _{i=1}^r {T \left(i \right)-a} \cdot \sum \limits _{i=1}^r {i} \right)}}r = \sum \limits _{i=1}^r {i \cdot T \left(i \right)</math>


<math>r \cdot a \cdot \sum \limits _{i=1}^r {i^{2}} + \sum \limits _{i=1}^r {i \cdot \left(\sum \limits _{i=1}^r {T \left(i \right)-a} \cdot \sum \limits _{i=1}^r {i} \right) = r \cdot \sum \limits _{i=1}^r {i \cdot T \left(i \right)}</math>


<math>a \cdot \left(r \cdot \sum \limits _{i=1}^r {i^{2}}- \left(\sum \limits _{i=1}^r {i} \right)^{2} \right) = r \cdot \sum \limits _{i=1}^r {i \cdot T \left(i \right) - \sum \limits _{i=1}^r {i \cdot \sum \limits _{i=1}^r {T \left(i \right)}</math>


 

Daraus entstehen folgende Endformeln:

 <math>a=\frac{r \cdot \left(\sum \limits _{i=1}^r {i \cdot T \left(i \right)} \right)- \left(\sum \limits _{i=1}^r {i} \right) \cdot \left(\sum \limits _{i=1}^r {T \left(i \right)} \right)}{r \cdot \sum \limits _{i=1}^r {i^{2}}- \left(\sum \limits _{i=1}^r {i} \right)^{2}}</math>



 <math>b=\frac{ \left(\sum \limits _{i=1}^r {i^{2}} \right) \cdot \left(\sum \limits _{i=1}^r {T \left(i \right)} \right)- \left(\sum \limits _{i=1}^r {i \cdot T \left(i \right)} \right) \cdot \sum \limits _{i=1}^r {i}}{r \cdot \sum \limits _{i=1}^r {i^{2}}- \left(\sum \limits _{i=1}^r {i} \right)^{2}}</math>



Anhand verschiedener Messpunkte kann nun die Funktion bestimmt werden, damit eine Gerade entsteht.

=== Beispiel ===

Um dies zu verdeutlichen, folgt nun ein Beispiel:

'''Beispielrechnung:'''

Folgende Messwerte sind gegeben:


T(1) = 8

T(2) = 3

T(3) = 5 

T(4) = 7

T(5) = 9


Nun werden die verschiedenen Größen für a und b berechnet.


Vorgehensweise, um Summen, z.B.:<math>\sum \limits _{i=1}^r {i \cdot T \left(i \right) </math> ausrechnen zu können:

r ist die Anzahl der Messwerte. 
Daher ist r = 5

i gibt den Startwert an. i ist im Beispiel 1, daher wird die Formel wie folgt ausgerechnet:

<math>\sum \limits _{i=1}^r {i \cdot T \left(i \right)= \left(1 \cdot 8 \right) + \left(2 \cdot 3 \right) + \left(3 \cdot 5 \right) + \left(4 \cdot 7 \right) + \left(5 \cdot 9 \right) = 102 </math>

<math>\sum \limits _{i=1}^r {i} = 1+2+3+4+5 = 15  </math>

<math>\sum \limits _{i=1}^r {T \left(i \right)= 8+3+5+7+9 = 32 </math>

<math>\sum \limits _{i=1}^r {i^{2}}= 1^2 + 2^2 + 3^2 + 4^2 + 5^2 = 55 </math>

<math> \left(\sum \limits _{i=1}^r {i} \right)^{2}= \left(1+2+3+4+5 \right)^2 = 225 </math>


Nun werden die berechneten Größen in die Formeln für a und b eingesetzt:


<math>\frac{ \left(5 \cdot 102 \right)- \left(15 \cdot 32 \right)}{ \left(5 \cdot 55 \right)-225}= \frac {30}{50} = 0,6</math>


<math>\frac{ \left(55 \cdot 32 \right)- \left(102 \cdot 15 \right)}{ \left(5 \cdot 55 \right)-225}= \frac {230}{50} = 4,6</math>


Parameter für die Regressionsgerade im kartesischen Koordinatensystem:


<math>a=0,6</math>

<math>b=4,6</math>


Die Regressionsgerade lautet: <math>f(n)=0,6n + 4,6</math>

Diese kann man nun einfach mithilfe von Gnuplot zeichnen:

<gnuplot>
set xlabel "n"
set ylabel "T(n)"
plot [n=0:5] 0.6*n+4.6
</gnuplot>

== Polynomfunktion ==

Was entsteht, wenn eine <b> Potenzfunktion </b> in der Form <math>T \left(n \right) = c \cdot n^k, \ k \geq 1, </math>
z.B. <math> T \left(n \right)=10n^2 </math> in einem Koordinatensystem mit logarithmisch eingeteilter y-Achse dargestellt wird?

Es entsteht eine Kurve.


<b>Polynome des Grades:</b>

- 0 werden konstante Funktionen genannt. z.B.: <math> T \left(n \right) = - 1 </math> <br>
- 1 werden lineare Funktionen genannt. z.B.: <math> T \left(n \right) = 3n + 5 </math><br>
- 2 werden quadratische Funktionen genannt. z.B.: <math> T \left(n \right) = - 3n^2 - 4n + 1 </math> <br>
- 3 werden kubische Funktionen genannt. z.B.: <math> T \left(n \right) = 4n^3 - 2n^2 + 7n + 2 </math><br>
- 4 werden quartische Funktionen genannt. z.B.: <math> T \left(n \right) = 6n^4 - n^3 + 4n + 2 </math>




In der folgenden Rechnung soll nachgewiesen werden, dass nur dann eine Gerade entsteht, wenn beide Achsen logarithmisch eingestellt sind. 

Dabei wird aus:
  
<math> z = f \left( log\ n\ \right) = \alpha \cdot log\ n + \beta , </math> mit <math> z = log\ y, \ \alpha = k </math> und <math> \beta = log\ c </math>


Daraus folgt:
<math> log\ y = f \left(n \right) = log\ \left(c \cdot n^k \right) = k \cdot log\ n + log\ c, \</math> für <math> n>0 </math> 


Nun zeichnet man wiederum die ermittelten Daten der Wertepaare in das Koordinatensystem ein. 

Der Schnittpunkt der Gerade mit der y-Achse gibt bei n=1 wegen log 1 = 0 den konstanten Faktor c an. 
Der Exponent k ist der Anstieg der Geraden.

Der Graph wird also tatsächlich zu einer Geraden, wenn beide Achsen logarithmisch eingestellt sind.



Um den Unterschied grafisch zu sehen, folgen nun ein paar Potenzfunktionen mit logarithmischer y-Achse:

<gnuplot>
set title 'Schaubild der Potenzfunktionen mit logarithmischer y-Achse:'
set xlabel "n"
set ylabel "T(n)"
set logscale y
set ytics (1, 10, 100,1000, 10000, 100000, 100000,1000000)
plot [n=1:10] 10*n**2, 100*n**3, 100*n**4    
</gnuplot>



Und nun mit logarithmischer x-und y-Achse:

<gnuplot>
set title 'Schaubild der Potenzfunktionen mit logarithmischer x und y-Achseneinteilung:'
set xlabel "n"
set ylabel "T(n)"
set logscale x
set logscale y
set ytics (1, 10, 100,1000, 10000, 100000, 100000,1000000)
plot [n=1:10] 10*n**2, 100*n**3, 100*n**4    
</gnuplot>


Wie sieht das ganz nun bei <b> Polynomfunktionen </b> aus:

<gnuplot>
set title 'Schaubild einer Polynomfunktion mit logarithmischer x und y-Achseneinteilung:'
set xlabel "n"
set ylabel "T(n)"
set logscale y
set logscale x
set ytics (1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 1e+10, 1e+11, 1e+12, 1e+13)
plot [n=1:10] 2*n**12+10*n**2+1234*n   
</gnuplot>


Bei diesen Graphen handelt es sich um keine Gerade, weil eine Summe gebildet wird.

Schließlich kann man davon ausgehen das nicht bei jeder Funktion eine Gerade entsteht.

Deshalb sind andere Untersuchungsmethoden notwendig um auf das gewünschte Ergebnis zu kommen.

== Approximation von Polynomfunktionen ==

Damit bei Polynomfunktionen eine Gerade entstehen kann, muss ein Näherungsverfahren angewendet werden. 

Polynomfunktionen bestehen aus mehreren Basisfunktionen der folgenden Form: 


<math>f \left(x \right)=c_0 \cdot g_0 \left(x \right)+c_1 \cdot g_1 \left(x \right)+ ... +c_m \cdot g_m \left(x \right)</math>

	 
Ziel ist es, die Methode der kleinsten Fehlerquadrate auf Polynomfunktionen der Form: 

<math> f \left(c_0, \ c_1, \ ... \ , \ c_m, \ x \right)=\sum \limits _{i=0}^m {c_i g_i \left(x \right),</math> mit Basisfunktionen <math> g_i \ : \ x\rightarrow x^i, </math> anzuwenden.


Nun werden die Koeffizienten <math> c_i </math> für <math> i = 0, \ 1, \ ... \ ,\ m </math> gesucht.
 
Dabei wird die Methode der kleinsten Fehlerquadrate angewendet auf die Formel:


<math>F \left(c_0 , \ c_1 , \ ... \ , \ c_m \right)=\sum \limits _{k=1}^n {\left(\sum \limits _{i=0}^m {c_i g_i \left(x_k \right)-y_k \right)^2\rightarrow min</math>


Das bedeutet, dass die Summe der Abstände zwischen der gesuchten Funktion und den Messwerten minimal sein soll. Dazu bildet man die Ableitung für sämtliche <math> c_i </math> und setzt diese gleich null.


<math>\frac{\delta F}{\delta c_i}=2\sum \limits _{k=1}^n {\left(\sum \limits _{i=0}^m {c_ig_i \left(x_k \right)-y_k \right) \cdot g_i \left(x_k \right)=0</math>


Nun multipliziert man die Ableitung aus und bringt <math> y_k </math> auf die rechte Seite.

Die Normalengleichungen für 0 ≤ j ≤ m lauten:


<math>\sum \limits _{i=0}^m { \left(\sum \limits _{k=1}^n {c_ig_i \left(x_k \right) \cdot g_j \left(x_k \right) \right)=\sum \limits _{k=1}^n {y_k \cdot g_j \left(x_k \right)}</math>



<math> g_j </math> geben Basisfunktionen zwischen 0 und m an. Nun trägt man die Formeln in ein lineares Gleichungssystem ein. 
Dabei erhält man für alle c (=konstante Faktoren) eine Lösung. 

Um dieses Gleichungssystem zu lösen, werden für <math> g_j </math> alle Basisfunktionen angenommen. 


Um das veranschaulichen zu können, benutzt man Matrizen:

Mit <math> \vec y = \left(y_1,...,y_n \right)^T </math>  und der Matrix:


<math>A=\begin{pmatrix} g_0 \left(x_1 \right) & g_1 \left(x_1 \right) & \cdots & g_m \left(x_1 \right) \\
                          g_0 \left(x_2 \right) & g_1 \left(x_2 \right) & \cdots & g_m \left(x_2 \right) \\
                          \vdots & \vdots & \cdots & \vdots \\
                          g_0 \left(x_n \right) & g_1 \left(x_n \right) & \cdots & g_m \left(x_n \right)\end{pmatrix} </math>


ergibt sich die Normalgleichung in der Form:

<math>A^TA\vec c = A^T \vec y</math>

Der reellwertige Vektor <math>\vec c= \left(c_0, \ c_1, \ ... \ , \ c_m \right)^T</math> bezeichnet die gesuchten Koeffizienten. 


Dadurch kann man dieses Gleichungssystem lösen und als Ergebnis erhält man die Faktoren für die einzelnen Polynome. 


Um die Koeffizienten der wählbaren Basisfunktionen bestimmen zu können, bedient man sich dem Computerprogramm „Maple“.

== Approximation mit Basisfunktionen (Mithilfe von Maple) ==


Für die Approximationsfunktion h sind die Koeffizienten: <math> c_0, \ c_1, \ ...  \ , \ c_m </math> gesucht.


<math> h \left(x \right) = c_0 \cdot g_0 \left(x \right) + c_1 \cdot g_1 \left(x \right) + ... + c_m \cdot g_m \left(x_m \right) </math>


Die Approximationsfunktion h soll die aus den Messwerten entstehende Funktion nach der Methode der kleinsten Fehlerquadrate annähern. 

Dabei sind die Funktionen <math> g_i </math> beliebige Basisfunktionen. 


Wie funktioniert diese Approximation?

Um die Approximationsfunktion zu bestimmen ist immer folgendes gegeben: <br><br>
- Die Messwerte von x und y <br>
- Die Basisfunktionen <math> g_0, \ g_1, \ ... \ , \ g_m </math>


Gesucht sind die Koeffizienten <math> c_0, \ c_1, \ ... \ , \ c_m </math>

Mithilfe von Maple kann man die Koeffizienten bestimmen lassen.



'''Maple-Worksheet''' (Maple 13)

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

 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)']);


Wenn man dies in Maple eingibt, so werden folgende Koeffizienten ausgegeben: 

                      
                 c:=[0.1762237762,2.635198135,0.8671328671,0.008158508158]

== Übungsaufgaben ==

[[Aufgaben]]


'''Lösungen'''

<document>Loesungen.pdf</document>



== Literatur ==
* Christian Wagenknecht ''Algorithmen und Komplexität.'' Fachbuchverlag Leipzig, 2003, ISBN 3-446-22314-2, Seite 37 - 44



== Folien ==

* Archivierte Folien vergangener Vorlesungen:
<document>Hilfsmittel_Mathematik1_v1.pdf</document>