Hilfsmittel Mathematik 1 WS13-14

Aus ProgrammingWiki

Autoren:

Andre Krause s3ankrau@stud.hszg.de
Roman Stange s3rostan@stud.hszg.de

Inhaltsverzeichnis

1 Approximation von Funktionen
- 1.1 Exponentialfunktionen
  - 1.1.1 Lineare Regression
  - 1.1.2 Beispiel
- 1.2 Polynomfunktionen
  - 1.2.1 Approximation mit Polynomfunktionen
  - 1.2.2 Approximation von Basisfunktionen
2 Übungsaufgaben
- 2.1 Lösungen

Approximation von Funktionen

Palindrom Vergleichsalgorithmus

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-Vergleichsalgorithmus). Die vielen gesammelten Messpunkte passen mehr oder weniger gut zu einer theoretischen Funktion, die fehlinterpretiert werden kann. Aus diesem Grund wird die optimale 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

Funktionen der Form $y = T(n) = a \cdot b^n$ , mit $b\ge 1$ können in einem Koordinatensystem mit logarithmischen Maßstab für die Ordinantenachse als Gerade $z = f(n) = n \cdot \alpha + \beta$ , mit $z= \log y$ , $\alpha = \log b$ (Anstieg der Geraden) und $\beta = \log a$ (Schnittpunkt mit der $y$ -Achse) dargestellt werden, was sich aus folgender Umformung ergibt: $\log y = f(n) = log(a \cdot b^n) = n \cdot \log b + \log a$

Beispiel:

Bei physikalischen Experimenten etwa, werden meist Werte für $x$ vorgegeben und solche für $y$ gemessen. In Wertetabellen sammelt man die Ergebnisse. Trägt man $y$ gegen $x$ auf, so kann man die Konstante $a$ prinzipiell leicht bestimmen, indem man eine Kurve durch die Messpunkte zeichnet und ihren Schnittpunkt mit der y-Achse bei $x=0$ abliest. In der Praxis erfordert das allerdings schon einiges zeichnerisches Geschick.
Für $x=0$ ist $y = a \cdot e^0 = a$ .

In der Praxis erfordert das allerdings schon einiges zeichnerisches Geschick. Den Wert der Konstanten $b$ aber wird man höchstens grob abschätzen können.

Wertetabelle für $y = 2 \cdot e^x$
$x$	$y$	$\ln (y)$
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

Einfacher und genauer sind $a$ und $b$ zu bestimmen, wenn nicht $y$ , sondern der Logarithmus $\ln(y)$ gegen $x$ aufgetragen wird. Aus der Gleichung $y = a \cdot e^{bx}$ wird durch Logarithmieren nämlich

$\ln(y) = \ln(a \cdot e^{bx})$
$\ln(y) = \ln(a) + bx \cdot \ln(e)$
$\ln(y) = \ln(a) + bx$

Man erhält eine Geradengleichung. Im Diagramm ergibt sich eine Gerade mit der Steigung $b$ , welche die Ordinate für $x=0$ im Punkt $\ln(a)$ schneidet. Die Gerade ist einfacher zu zeichnen, und ihre Steigung durch ein Steigungsdreieck leicht zu bestimmen.

$b = \frac {\Delta \ln y}{\Delta x}$

Expotentialfunktion ohne logarithmierter y-Achse

Expotentialfunktion mit logarithmierter y-Achse

Expotentialfunktion mit Anstieg $b$

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.

Die zugehörige Geradengleichung lautet:

(a steht für die Steigung der Geraden, b für den Schnittpunkt mit der y-Achse)

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

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.

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 an der Stelle $x=0$ ist 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.

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

Nach a abgeleitet: $\frac{\partial}{\partial a} = 2\codt\sum_{n=1}^{r} (T(n) - (a\cdot n+b))\cdot(-n) \stackrel{!}{=} 0$

Nach b abgeleitet: $\frac{\partial}{\partial b} = 2\codt\sum_{n=1}^{r} (T(n) - (a\cdot n+b))\cdot(-1) \stackrel{!}{=} 0$

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

$= a \sum_{n=1}^{r}n^2 + b \sum_{n=1}^{r}n = \sum_{n=1}^{r}n \cdot T(n)$

$= a \sum_{n=1}^{r}n + r \cdot b = \sum_{n=1}^{r}T(n)$

Für die Geradengleichung wird nun nach $a$ bzw. nach $b$ umgestellt.

$= a \sum_{n=1}^{r}n + r \cdot b = \sum_{n=1}^{r}T(n)$

$= r \cdot b = \sum_{n=1}^{r}T(n) - a \sum_{n=1}^{r}n$

$= b = \frac{\sum \limits _{n=1}^{r}T(n) - a \sum \limits _{n=1}^{r}n}{r}$

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

$= \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)$

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

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

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

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

Daraus ergeben sich die Formeln für $a$ und $b$ . Mit den gegebenen Messwerten kann anschließend die Regressionsgerade berechnet werden.

$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}$

$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}$

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:

Wertepaare
$n$	$T(n)$
0	0
1	1
2	3
3	2.5
4	4
5	8
6	6

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

$r$ ist in diesem Beispiel die Anzahl der Wertepaare, also 7.

$\sum_{n=1}^r n \cdot T(n) = (1\cdot1) + (2\cdot3) + (3\cdot2.5) + (4\cdot4) + (5\cdot8) + (6\cdot6) = 106.5$

$\sum_{n=1}^r n = 1 + 2 + 3 + 4 + 5 + 6 = 21$

$\sum_{n=1}^r n^2 = 1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2 = 91$

$\sum_{n=1}^r T(n) = 1 + 3 + 2.5 + 4 + 8 + 6 = 24.5$

Die berechneten Summen werden nun in die Gleichungen für $a$ und $b$ eingesetzt.

$a = \frac{7\cdot106.5 - 21\cdot24.5}{7\cdot91 - 21^2} = 1.18$

$b = \frac{91\cdot24.5 - 106.5\cdot21}{7\cdot91 - 21^2} = -0.04$

Daraus ergibt sich folgende Regressionsgerade:

$f(n) = 1.18\cdot n - 0.04$

Der Plot der errechneten Regressionsgerade ergibt folgendes Bild:

An der grafischen Darstellung kann man erkennen, dass die Funktionsgerade nicht durch den Nullpunkt des Koordinatensystems geht. Bei linearen Aufwandsfunktionen ist dies aber von Relevanz, da bei der Problemgröße = 0 kein Rechenaufwand vorliegt. Verläuft die Gerade nicht durch den Koordinatenursprung, kann es zu Falschinterpretationen kommen.

Dieses Problem kann durch die Überlegung, dass bei einer Geraden, die durch den Ursprung führt, $b=0$ ist, beseitigt werden. Die veränderte Gleichung lautet:

Die Methode der kleinsten Fehlerquadrate angewandt auf die Geradengleichung: $f(n)=a \cdot n$

Abgeleitet nach $a$ :
$\frac{d}{da}\left(2\codt\sum_{n=1}^{r} (T(n) - (a\cdot n))\cdot(-n)\right) \stackrel{!}{=} 0$

Anschließend wird diese Gleichung vereinfacht und nach $a$ umgestellt:
$a \sum_{n=1}^{r}n^2 = \sum_{n=1}^{r}n \cdot T(n)$

$a = \frac{\sum \limits_{n=1}^{r}n \cdot T(n)}{\sum \limits_{n=1}^{r}n^2}$

Nun werden die obigen Wertepaare wieder eingesetzt um das $a$ zu ermitteln:

$a=\frac{106.5}{91} = 1.17$

Die dazu gehörige Geradengleichung lautet: $f(n) = 1.17 \cdot n$

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 $f(x) = 3\cdot x^2$ mit einer logarithmierten y-Achse geplottet.

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

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

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

$\log y = f(x) = \log(3\cdot x^2)$

$= \log 3 + \log(x^2)$

$= 2 \cdot \log x + \log 3$

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 $n = 1$ durch $\log 1 = 0$ den konstanten Faktor $c$ an. Aus dem Anstieg ist der Exponent $k$ ablesbar. Das gilt jedoch nicht für alle Polynomfunktionen, wie folgendes Beispiel zeigt:

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

Approximation mit Polynomfunktionen

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

$geg: (x_1, y_1), (x_2, y_2), (x_3, y_3), ..., (x_n, y_n)|ges: c_o, c_1, ..., c_m$

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

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

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

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:

$\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$

Das heißt, die partiellen Ableitungen für alle $c_i$ müssen gleich 0 sein.

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

${= 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}$

$= \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)$

Nach Umformung lautet die Normalengleichung für $0 \leq j \leq m$ :

$= \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)$

Diese Gleichung kann auch in folgender Form dargestellt werden:

$\vec{y} = \begin{pmatrix} y_1\\ y_2\\ \vdots \\ y_n \end{pmatrix}$

$\vec{c} = \begin{pmatrix} c_0\\ c_1\\ \vdots \\ c_m \end{pmatrix}$

A = $\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}$

$A^T\cdot A\cdot\vec{c} = A^T\cdot \vec{y}$

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

Approximation von Basisfunktionen

Anhand folgendem Maxima-Worksheet wird die Bestimmung der Koeffizienten der Approximationsfunktion:

$h(x) = c_0\cdot g_0(x) + c_1\cdot g_1(x) + ... + c_m\cdot g_m(x_m)$

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

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

Maxima_Worksheet.zip (0.1 MB)

Übungsaufgaben

1. Exponentialfunktionen

Lassen Sie sich für die Funktion $4\cdot 12^x$ den zugehörigen Graph plotten.

Verwenden Sie dafür das kostenlose Programm gnuplot, welches Sie unter folgendem Link downloaden können:

Download-Page gnuplot

Nach der Installation ist die wgnuplot.exe im Ordner bin zu starten.

Machen Sie sich mit dem Tool vertraut. Dieses Tutorial eignet sich dafür sehr gut.

Verwenden Sie beim Plotten der oben genannten Funktion einmal die normale Achseneinteilung und zum anderen die logarithmierte y-Achse mit dem Wertebereich $x = 6..10$ .

Berechnen Sie für folgende Wertepaare die zugehörige Regressionsgerade. Nutzen Sie dafür die hergeleiteten Gleichungen für a und b. Anschließend lassen Sie sich diese Gerade in gnuplot ausgeben.

Wertepaare
$n$	$T(n)$
1	4
2	6
3	10
4	5
5	12
6	9

(Optional können Sie eine .dat Datei mit den Wertepaaren anlegen und diese zusätzlich Plotten lassen).

2. Polynomfunktionen

Lassen Sie sich, ähnlich wie im oberen Abschnitt, die Funktion $12\cdot x^3 +4$ in gnuplot darstellen.

Dies soll einmal mit normaler Achseneinteilung, einmal mit logarithmierter y-Achse und einmal mit logarithmierter y- und x-Achse durchgeführt werden.

Der Wertebereich soll hierbei für $x = 1..20$ gelten.

Anschließend nutzen Sie Maxima, um die Koeffizienten $c_i$ der Approximationsfunktion

$h(x) = c_0\cdot g_0(x) + c_1\cdot g_1(x) + ... + c_m\cdot g_m(x_m)$

zu berechnen.

Folgende Wertepaare sind gegeben:

Wertepaare
$x$	$y$
3	1
4	3
5	7
7	8
10	11

Die Basisfunktionen lauten:

$g := 1, x \rightarrow x+2, x \rightarrow \frac{1}{12-x}$

Nutzen Sie dazu das vorgegebene Maxima-Worksheet aus dem Abschnitt Approximation von Basisfunktionen.

Lösungen