AuK/Hilfsmittel Mathematik 1 WS13-14

Wiki-Quelltext dieser Seite.

'''<b>Autoren:</b>'''
 Andre Krause s3ankrau@stud.hszg.de
 Roman Stange s3rostan@stud.hszg.de

==Approximation von Funktionen==
[[Bild:S3ankrau_Diagram1.JPG|right|thumb|300px|Palindrom Vergleichsalgorhitmus]]
'''Motivation:'''

Die Erfahrungen und Beobachtungen haben bereits gezeigt, dass bei grafischen Auswertungen der Effizienz (Verhältnis der untersuchten Größe zur Zeit), mit Hilfe der Darstellung in einem karthesischen Koordinatensystem nur selten glatte Funktionsgraphen auftreten (s. Übung 1 - Palindrom-Vergleichsalgorhitmus). Die vielen gesammelten Messpunkte passen mehr oder weniger gut zu einer theoretischen Funktion, die fehlinterpretiert werden kann. Aus diesem Grund wird die optimalste Funktion gesucht, die sich den gegebenen Wertepaaren am genauesten annähert. Diese mathematische Annäherung wird als Approximation bezeichnet. Dafür wendet man mathematische Regeln (z.B. Methode der kleinsten Fehlerquadrate)an, aber auch geeignete Software (z.B. CAS), um die optimale Approximationsfunktion zu ermitteln. 


===Exponentialfunktionen===

<div style="color:black; background-color:lawngreen; border:1px dotted midnightblue;">
Funktionen der Form <math>y = T(n) = a \cdot b^n</math>, mit <math>b\ge 1</math> können in einem Koordinatensystem mit logarithmischen Maßstab für die Ordinantenachse als Gerade <math>z = f(n) = n \cdot \alpha + \beta</math>, mit <math>z= \log y</math>, <math>\alpha = \log b</math> (Anstieg der Geraden) und <math>\beta = \log a</math> (Schnittpunkt mit der <math>y</math>-Achse) dargestellt werden, was sich aus folgender Umformung ergibt:
<math> \log y = f(n) = log(a \cdot b^n) = n \cdot \log b + \log a</math>
</div> 

Beispiel: <math>y = a \cdot e^{bx}</math>

{|class="wikitable" style="border: 2px solid lightgray; margin:10px 10px 1em 1em; padding-right: 10px;"
! colspan="3" style="background-color:lawngreen;"|Wertetabelle für <math> y = 2 \cdot e^x  </math>
|-
| width="100pt" |'''<math>x</math>'''
| width="100pt" |'''<math>y</math>'''
| width="100pt" |'''<math>\ln (y)</math>'''
|-
|0
|2,0
|0,69
|-
|1
|5,4
|1,69
|-
|2
|14,8
|2,69
|-
|3
|40,2
|3,69
|-
|4
|109,2
|4,69 
|}
Bei physikalischen Experimenten etwa, werden meist Werte für <math>x</math> vorgegeben und solche für <math>y</math> gemessen. Trägt man <math>y</math> gegen <math>x</math> auf, so kann man die Konstante <math>a</math> im Prinzip leicht bestimmen, indem man eine Kurve durch die Messpunkte zeichnet und ihren Schnittpunkt mit der y-Achse bei <math>x=0</math> abliest (für <math>x=0</math> ist <math>y = a \cdot e^0 = a</math>). In der Praxis erfordert das allerdings schon einiges zeichnerisches Geschick. Den Wert der Konstanten <math>b</math> aber wird man höchstens grob abschätzen können. Einfacher und genauer sind <math>a</math> und <math>b</math> zu bestimmen, wenn nicht <math>y</math>, sondern der Logarithmus <math>\ln(y)</math> gegen <math>x</math> aufgetragen wird. Aus der Gleichung <math>y = a \cdot e^{bx}</math> wird durch Logarithmieren nämlich <math>\ln(y) = \ln(a \cdot e^{bx}) = \ln(a) + \ln(e \cdot bx) = \ln(a) + bx</math>. Man erhält eine Geradengleichung. Im Diagramm ergibt sich eine Gerade mit der Steigung b, welche die Ordinate für <math>x=0</math> im Punkt <math>\ln(a)</math> schneidet. Die Gerade ist einfacher zu zeichnen, und ihre Steigung durch ein Steigungsdreieck leicht zu bestimmen. 
{|
|[[Bild:Visvitalis_Graph_exp_01a.png|thumb|none|250px|Expotentialfunktion ohne logarithmierter y-Achse]]
|[[Bild:Visvitalis_Graph_exp_01b.png|thumb|none|250px|Expotentialfunktion mit logarithmierter y-Achse]]
|}
====Lineare Regression====

Im vorigen Abschnitt wurde die Ermittlung der gesuchten Gerade durch Einsetzen von Wertepaaren in ein Koordinatensystem mit logarithmischer y-Achse behandelt. Diese Methode ist jedoch nicht hundertprozentig genau. Deshalb ist es notwendig, die approximierte Gerade durch die so genannte lineare Regression näher zu bestimmen.

<div style="color:black; background-color:lawngreen; border:1px dotted midnightblue;">
Die lineare Regression ist eine mathematische Hilfsmethode, um eine Gerade, die sich den vorhandenen Messpunkten am besten annähert, zu ermitteln.
</div>

Die zugehörige Geradengleichung lautet:

<div><math>y = f(n) = a \cdot n + b</math>
(a steht für die Steigung der Geraden, b für den Schnittpunkt mit der y-Achse)</div>

Damit sich die Gerade möglichst nah an den verstreuten Messpunkten befindet, muss der maximale Abstand zu den Wertepunkten minimal sein.

<math>\max\mid T(n) - (a\cdotn+b)\mid \rightarrow minimal</math>

Sollte es jedoch den Fall geben, dass es ein oder mehrere Wertepaare gibt, die sich relativ weit von den übrigen befinden, wird die gesuchte Regressionsgerade sehr ungenau. Daher wird die gegebene Gleichung folgendermaßen angepasst.

<math>\sum_{n} \mid T(n) - (a\cdotn+b)\mid \rightarrow minimal</math>

Das bedeutet, dass nun die Summe aller Abstände minimal sein soll. Dadurch verlieren die größeren Abstände, die vorher ein Problem hätten darstellen können, an Gewichtung. Hieraus entsteht aber ein neues Problem: Zur Ermittlung des Minimums ist die 1. Ableitung der Summe nötig. Die Betragsfunktion ist für <math>x=0</math> jedoch nicht differenzierbar.

Zur Eliminierung dieses Problems wird die Methode der kleinsten Fehlerquadrate nach Gauss genutzt. Dadurch wird der Umstand der Differenzierbarkeit gelöst, das Minimum aber nicht beeinflusst.

<math>\sum_{n} (T(n) - (a\cdot n+b))^2 \rightarrow minimal</math>

Um nun das Minimum zu erhalten, ist es notwendig, die erste Ableitung gleich 0 zu setzen.

Nach a abgeleitet:
<math>2\codt\sum_{n=1}^{r} (T(n) - (a\cdot n+b))\cdot(-n) \stackrel{!}{=} 0</math>

Nach b abgeleitet:
<math>2\codt\sum_{n=1}^{r} (T(n) - (a\cdot n+b))\cdot(-1) \stackrel{!}{=} 0</math>

Durch Umformung erhält man anschließend die sogenannte Normalgleichungen.

<math>2\codt\sum_{n=1}^{r} (T(n) - (a\cdot n+b))\cdot(-n) = 2\codt\sum_{n=1}^{r} (T(n) - (a\cdot n+b))\cdot(-1)</math><br><br>
<math>a \sum_{n=1}^{r}n^2 + b \sum_{n=1}^{r}n = \sum_{n=1}^{r}n \cdot T(n)</math><br><br>
<math>a \sum_{n=1}^{r}n + r \cdot b = \sum_{n=1}^{r}T(n)</math><br><br>

Für die Geradengleichung wird nun nach <math>a</math> bzw. nach <math>b</math> umgestellt.<br><br>
<math>a \sum_{n=1}^{r}n + r \cdot b = \sum_{n=1}^{r}T(n)</math><br><br>
<math>r \cdot b = \sum_{n=1}^{r}T(n) - a \sum_{n=1}^{r}n</math><br><br>
<math>b = \frac{\sum \limits _{n=1}^{r}T(n) - a \sum \limits _{n=1}^{r}n}{r}</math><br><br>
<math>a \sum_{n=1}^{r}n^2 + \left(\frac{\sum \limits _{n=1}^{r}T(n) - a \sum \limits _{n=1}^{r}n}{r}\right) \cdot \sum_{n=1}^{r}n = \sum_{n=1}^{r}n \cdot T(n)</math><br><br>
<math>\frac{r \cdot a \sum \limits _{n=1}^{r}n^2 + \sum \limits _{n=1}^{r}n \cdot \left(\sum \limits _{n=1}^{r}T(n) - a \sum \limits _{n=1}^{r}n\right)}{r} = \sum_{n=1}^{r}n \cdot T(n)</math><br><br>
<math>r \cdot a \sum \limits _{n=1}^{r}n^2 + \sum \limits _{n=1}^{r}n \cdot \left(\sum \limits _{n=1}^{r}T(n) - a \sum \limits _{n=1}^{r}n\right) = r \cdot \sum_{n=1}^{r}n \cdot T(n)</math><br><br>
<math>r \cdot a \sum \limits _{n=1}^{r}n^2 + \sum \limits _{n=1}^{r}n \cdot \sum \limits _{n=1}^{r}T(n) - a {\left(\sum \limits _{n=1}^{r}n\right)}^2 = r \cdot \sum_{n=1}^{r}n \cdot T(n)</math><br><br>
<math>r \cdot a \sum \limits _{n=1}^{r}n^2 - a {\left(\sum \limits _{n=1}^{r}n\right)}^2 = r \cdot \sum_{n=1}^{r}n \cdot T(n) - \sum \limits _{n=1}^{r}n \cdot \sum \limits _{n=1}^{r}T(n)</math><br><br>
<math>a \cdot \left(r \cdot \sum \limits _{n=1}^{r}n^2 - {\left(\sum \limits _{n=1}^{r}n\right)}^2\right) = r \cdot \sum_{n=1}^{r}n \cdot T(n) - \sum \limits _{n=1}^{r}n \cdot \sum \limits _{n=1}^{r}T(n)</math><br><br>

Daraus ergeben sich die Formeln für <math>a</math> und <math>b</math>. Mit den gegebenen Messwerten kann anschließend die Regressionsgerade berechnet werden.<br><br>
<div style="color:black; background-color:lawngreen; border:1px dotted midnightblue;">
<math>a = \frac{r \cdot \left(\sum \limits _{n=1}^{r}n \cdot T(n)\right) - \sum \limits _{n=1}^{r}n \cdot \sum \limits _{n=1}^{r}T(n)}{r \cdot \sum \limits _{n=1}^{r}n^2 - {\left(\sum \limits _{n=1}^{r}n\right)}^2}</math>
</div><br>
<div style="color:black; background-color:lawngreen; border:1px dotted midnightblue;">
<math>b = \frac{\left(\sum \limits _{n=1}^{r}n^2\right) \cdot \left(\sum \limits _{n=1}^{r}T(n)\right) - \left(\sum \limits _{n=1}^{r}n \cdot T(n)\right)\cdot \sum \limits _{n=1}^{r}n}{r \cdot \sum \limits _{n=1}^{r}n^2 - {\left(\sum \limits _{n=1}^{r}n\right)}^2}</math>
</div>

====Beispiel====
Mit gegebenen Wertepaaren kann nun die Regressionsgerade durch Einsetzen in die im vorigen Abschnitt hergeleiteten Formeln berechnet werden.
Für dieses Beispiel werden folgende Wertepaare angenommen:

{|class="wikitable" style="border: 2px solid lightgray; margin:10px 10px 1em 1em; padding-right: 10px;"
! colspan="2" style="background-color:lawngreen;"|Wertepaare
|-
| width="100pt" |'''<math>n</math>'''
| width="100pt" |'''<math>T(n)</math>'''
|-
|1
|10
|-
|2
|16
|-
|3
|12
|-
|4
|18
|-
|5
|8
|-
|6
|14 
|}

Nun werden die einzelnen Summen berechnet, um die Werte später besser in die Gleichung einsetzen zu können.

<math>r</math> ist in diesem Beispiel die Anzahl der Wertepaare, also 6.

<math>\sum_{n=1}^r n \cdot T(n) = (1\cdot10) + (2\cdot16) + (3\cdot12) + (4\cdot18) + (5\cdot8) + (6\cdot14) = 274</math><br><br>
<math>\sum_{n=1}^r n = 1 + 2 + 3 + 4 + 5 + 6 = 21</math><br><br>
<math>\sum_{n=1}^r n^2 = 1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2 = 91</math><br><br>
<math>\sum_{n=1}^r T(n) = 10 + 16 + 12 + 18 + 8 + 14 = 78</math><br><br>

Die berechneten Summen werden nun in die Gleichungen für <math>a</math> und <math>b</math> eingesetzt.

<math>a = \frac{6\cdot274 - 21\cdot78}{6\cdot91 - 21^2} = 0,06</math><br><br>
<math>b = \frac{91\cdot78 - 274\cdot21}{6\cdot91 - 21^2} = 12,8</math><br><br>

Daraus ergibt sich folgende Regressionsgerade:<br><br>

<math>f(n) = 0,06\codt n + 12,8</math><br><br>

Der Plot der erechneten Regressionsgerade ergibt folgendes Bild:

[[Bild:S3ankrau_Plot_fertige_regressionsgerade.JPG|800px]]

===Polynomfunktionen===
Im Abschnitt über die Approximation von Exponentialfunktionen wurde bereits festgestellt, dass man ein sehr gutes Ergebnis erreicht, wenn die y-Achse logarithmiert wird. Es wäre also eine Überlegung wert, dies auch auf Polynomfunktionen anzuwenden. Im folgenden wird die Funktion <math>f(x) = 3\cdot x^2</math> mit einer logarithmierten y-Achse geplottet.

[[Bild:S3ankrau_Plot_polynom1.JPG|800px]]

Wie man an dieser Abbildung erkennen kann, führt allein die Logarithmierung der y-Achse nicht zu einer Geraden.

[[Bild:S3ankrau_Plot_polynom2.JPG|800px]]

Erst durch Logarithmieren der y- und der x-Achse entsteht eine Gerade. Dies wird deutlich, wenn man sich folgende Rechnung anschaut:
<math>T(x) = 3\cdot x^2</math> wird logarithmiert zu

<math>z = f(\log x) = a \cdot \log x + b</math>, mit <math> z = \log y, a = 2</math> und <math>b = \log 3</math>, d.h.

<math>\log y = f(x) = \log(3\cdot x^2) = 2 \cdot \log x + \log 3</math>

Geht man wie bei den Exponentialfunktionen genauso davon aus, dass durch Einsetzen der Wertepaare eine Gerade entsteht, ergibt der Schnittpunkt mit der y-Achse für <math> n = 1</math> durch <math> \log 1 = 0</math> den konstanten Faktor <math>c</math> an. Aus dem Anstieg ist der Exponent <math>k</math> ablesbar. Dies ist in der Geraden der Funktion <math>T(x) = 3\cdot x^2</math> (s. vorherige Abbildung)zu erkennen. Das gilt jedoch nicht für alle Polynomfunktionen, wie folgendes Beispiel zeigt:

[[Bild:S3ankrau_Plot_polynom3.JPG|800px]]

Es darf also nicht immer davon ausgegangen werden, dass auch tatsächlich eine Gerade entsteht. Das ist auf die Summen in der Funktion <math>f(x) = 3x^5 + 5x^4 + 12x^3 + 25x^2</math> zurückzuführen, die durch Logarithmierung nicht in einen linearen Ausdruck umgewandelt werden können.

====Approximation von Polynomfunktionen====
Bei dieser Betrachtung wird die allgemeine Form der Polynomfunktionen folgender Gestalt genutzt:

<math>geg: (x_1, y_1), (x_2, y_2), (x_3, y_3), ..., (x_n, y_n)|ges: c_o, c_1, ..., c_m</math><br><br>

<math>f(c_0, c_1,...,c_m,x) = \sum_{i=0}^{m} c_i g_i(x)</math>, mit Basisfunktionen <math>g_i : x \mapsto x^i</math><br><br>

Genau wie bei den Exponentialfunktionen ist es auch hier sinnvoll, die Methode der kleinsten Fehlerquadrate anzuwenden. Damit können die gesuchten Koeffizienten <math>c_i</math> für <math>i = 0, 1,..., m</math> ermittelt werden.

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

Genau wie bei den Exponentialfunktionen wird also die Summe der Abstände zwischen den Wertepaaren und der gesuchten Regressionsgerade minimiert. Dafür muss folgendes gelten:

<math> \frac{\partial F}{\partial c_i} = 2\sum_{k=1}^{n} \left(\sum_{i=0}^{m} c_i g_i(x_k) - y_k\right)g_i(x_k) \stackrel{!}{=}0</math><br><br>

Das heißt, die partiellen Ableitungen für alle <math>c_i</math> müssen gleich 0 sein.

<math>2 \cdot g_j(x_k) \sum_{k=1}^{n}\left(c_og_0(x_k) + c_1g_1(x_k) + ... + c_ig_i(x_k) - y_k\right) \stackrel{!}{=} 0</math><br><br>
<math>2 \cdot \sum_{k=1}^{n}\left(c_og_0(x_k)g_j(x_k) + c_1g_1(x_k)g_j(x_k) + ... + c_ig_i(x_k)g_j(x_k)\right) - 2 \cdot \sum_{k=1}^{n}y_kg_j(x_k) \stackrel{!}{=} 0</math><br><br>
<math>\sum_{k=1}^{n}\left(c_og_0(x_k)g_j(x_k) + c_1g_1(x_k)g_j(x_k) + ... + c_ig_i(x_k)g_j(x_k)\right) = \sum_{k=1}^{n}y_kg_j(x_k)</math><br><br>

Nach Umformung lautet die Normalengleichung für <math> 0 \leq j \leq m</math>:

<math>\sum_{i=0}^{m}\left(\sum_{k=1}^{n}\left(g_i(x_k) g_j(x_k) \right)\right) c_i = \sum_{k=1}^{n}y_k\cdot g_j(x_k)</math><br><br>

Diese Gleichung kann auch in folgender Form dargestellt werden:

<math>
\vec{y} =
\begin{pmatrix}
y_1\\ y_2\\ \vdots \\ y_n
\end{pmatrix}</math><br><br>

<math>
\vec{c} =
\begin{pmatrix}
c_0\\ c_1\\ \vdots \\ c_m
\end{pmatrix}</math><br><br>

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

<div style="color:black; background-color:lawngreen; border:1px dotted midnightblue;">
<math>A^T\cdot A\cdot\vec{c} = A^T\cdot \vec{y}</math>
</div>

Der Vektor <math>\vec{c}</math> enthält die gesuchten Koeffizentien. Diese können durch lösen des genannten Gelichungssystems bestimmt werden.

<language>Scheme</language>
====Approximation von Basisfunktionen====
Anhand folgendem Maxima-Worksheet wird die Bestimmung der Koeffizienten der Basisfunktion:

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

anhand von Messwerten vorgeführt und dient gleichzeitig als Beispiel für die im vorigen Abschnitt hergeleitete Normalgleichung.

<code id="525f927565726">x: [1, 2, 6, 7];

n: length(x);

y: [2, 3, 4, 9];

pkt: makelist([x[i],y[i]],i,1,n);

g: [lambda([x], 1), lambda([x], x), lambda([x], 1/(x-9))];

m: length(g);

for k:1 thru n do
  for i:1 thru m do
    a[k,i]:= g[i](x[k]);

A: genmatrix(a, n, m);

AT: transpose(A);

AT.A.c = AT.y;

(invert(AT.A).AT.A).c = float(invert(AT.A).(AT.y));

c_matrix: float(invert(AT.A).(AT.y));

matrix_size(c_matrix);

for i:1 thru m step 1 do
  c[i]: c_matrix[i][1];

h(x):=sum(c[i]*g[i](x), i,1,m);

wxplot2d([[discrete, pkt], h(s)], [s,0,x[n]],
[style, points, lines],
[color, red, blue], [legend, false],
[xlabel, "x"], [ylabel, "y"]);
</code>

==Übungsaufgaben==
Text

===Lösungen===
Text