Hilfsmittel Mathematik 1 WS13-14
Inhaltsverzeichnis |
Autoren:
Andre Krause s3ankrau@stud.hszg.de Roman Stange s3rostan@stud.hszg.de
O-Notation
\mathcal{O}(f)=\lbrace t \colon \mathbb{N}\to \mathbb{R}^+ \vert \exists c \in \mathbb{R}^+\exists n_0 \in \mathbb{N} \forall n \ge n_0 t(n) \le c \cdot f(n)\rbrace
Beispiel:
Wenn zwei Funktionen gegeben sind vom Bereich natürliche Zahlen in positiv reelle Zahlen: f,g\colon \mathbb{N} \to \mathbb{R}^+, dann ist f in der Komplexitätsklasse von g, per Definition genau dann, wenn es ein n_0 und eine Konstante c mit der Eigenschaft f(n)\le c \cdot g(n) für alle n \ge n_0.
Mit der obigen Definition wird also verlangt, dass f(n) langfristig unter g(n) liegt. Ab der Stelle n_o dominiert g(n), da alle n, die noch kommen unterhalb von g(n) sind. Dabei spielt es auch keine Rolle, ob f(n) mit anderen Anstiegen bestückt wird, ebenso wenig würde ein Koeffizient vor n^2 der quadratischen Funktion die Sachlage verändern. Man kann also sagen, dass f(n) höchstens von der Komplexität g(n) ist - linear wird dominiert vom quadratischen.
Einordnung der Laufzeitfunktionen
| Notation | Bedeutung | Anschauliche Erklärung | Beispiele für Laufzeiten |
|---|---|---|---|
| f \in \mathcal{O}(1) | f ist beschränkt | f überschreitet einen konstanten Wert nicht (unabhängig vom Wert des Arguments). | Nachschlagen des x-ten Elementes in einem Feld. |
| f \in \mathcal{O}(\log x) | f wächst logarithmisch | f wächst ungefähr um einen konstanten Betrag, wenn sich das Argument verdoppelt. Die Basis des Logarithmus ist dabei egal. | Binäre Suche im sortierten Feld mit x Einträgen |
| f \in \mathcal{O}(\sqrt{x}) | f wächst wie die Wurzelfunktion | f wächst ungefähr auf das Doppelte, wenn sich das Argument vervierfacht | naiver Primzahltest mittels Teilen durch jede ganze Zahl \leq \sqrt{x} |
| f \in \mathcal{O}(x) | f wächst linear | f wächst ungefähr auf das Doppelte, wenn sich das Argument verdoppelt. | Suche im unsortierten Feld mit x Einträgen (Bsp.Lineare Suche) |
| f \in \mathcal{O}(x \log x) | f hat super-lineares Wachstum | |Fortgeschrittenere Algorithmen zum Sortieren von x Zahlen Mergesort, Heapsort | |
| f \in \mathcal{O}(x^2) | f wächst quadratisch | f wächst ungefähr auf das Vierfache, wenn sich das Argument verdoppelt | Einfache Algorithmen zum Sortieren von x Zahlen Selectionsort |
| f \in \mathcal{O}(2^x) | f wächst exponentiell | f wächst ungefähr auf das Doppelte, wenn sich das Argument um eins erhöht | |Erfüllbarkeitsproblem der Aussagenlogik (SAT) mittels exhaustivem Verfahren |
| f \in \mathcal{O}(x!) | f wächst faktoriell | f wächst ungefähr auf das (x+1)-fache, wenn sich das Argument um eins erhöht. | |TSP (mit Enumerationsansatz) |
Approximation von Funktionen
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. Exponentialfunktion)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 aBeispiel: y = a \cdot e^{bx}
| 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 |
Bei physikalischen Experimenten etwa, werden meist Werte für x vorgegeben und solche für y gemessen. Trägt man y gegen x auf, so kann man die Konstante a im Prinzip leicht bestimmen, indem man eine Kurve durch die Messpunkte zeichnet und ihren Schnittpunkt mit der y-Achse bei x=0 abliest (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. 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(a) + \ln(e \cdot bx) = \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.
 Expotentialfunktion ohne logarithmierter y-Achse |  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.
Die lineare Regression ist eine mathematische Hilfsmethode, um eine Gerade, die sich den vorhandenen Messpunkten am besten annähert, zu ermitteln.
Die zugehörige Geradengleichung lautet:
Damit sich die Gerade möglichst nah an den verstreuten Messpunkten befindet, muss der maximale Abstand zu den Wertepunkten minimal sein.
\max\mid T(n) - (a\cdotn+b)\mid \rightarrow minimalSollte 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.
\sum_{n} \mid T(n) - (a\cdotn+b)\mid \rightarrow minimalDas 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 x=0 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.
\sum_{n} (T(n) - (a\cdot n+b))^2 \rightarrow minimalUm nun das Minimum zu erhalten, ist es notwendig, die erste Ableitung gleich 0 zu setzen.
Nach a abgeleitet:
2\codt\sum_{n=1}^{r} (T(n) - (a\cdot n+b))\cdot(-n) \stackrel{!}{=} 0Nach b abgeleitet:
2\codt\sum_{n=1}^{r} (T(n) - (a\cdot n+b))\cdot(-1) \stackrel{!}{=} 0Durch Umformung erhält man anschließend die sogenannte Normalgleichungen.
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)
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) |
| 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.
r ist in diesem Beispiel die Anzahl der Wertepaare, also 6.
\sum_{n=1}^r n \cdot T(n) = (1\cdot10) + (2\cdot16) + (3\cdot12) + (4\cdot18) + (5\cdot8) + (6\cdot14) = 274
\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) = 10 + 16 + 12 + 18 + 8 + 14 = 78
Die berechneten Summen werden nun in die Gleichungen für a und b eingesetzt.
a = \frac{6\cdot274 - 21\cdot78}{6\cdot91 - 21^2} = 0,06
b = \frac{91\cdot78 - 274\cdot21}{6\cdot91 - 21^2} = 12,8
Daraus ergibt sich folgende Regressionsgerade:
f(n) = 0,06\codt n + 12,8
Der Plot der erechneten Regressionsgerade ergibt folgendes Bild:
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) = 2 \cdot \log x + \log 3Geht 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. Dies ist in der Geraden der Funktion T(x) = 3\cdot x^2 (s. vorherige Abbildung)zu erkennen. 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 von 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 Basisfunktion:
h(x) = c_0\cdotg_0(x) + c_1\cdotg_1(x) + ... + c_m\cdotg_m(x_m)anhand von Messwerten vorgeführt und dient gleichzeitig als Beispiel für die im vorigen Abschnitt hergeleitete Normalgleichung.
x: [0, 3, 4, 5];
n: length(x);
y: [2, 3, 4, 8];
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[2,3];
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];
c[2];
h(x):=sum(c[i]*g[i](x), i,1,m);
h(5);
wxplot2d([[discrete, pkt], h(s)], [s,0,x[n]], [style, points, lines], [color, red, blue], [legend, false], [xlabel, "x"], [ylabel, "y"]);
Übungsaufgaben
Text
Lösungen
Text