Hilfsmittel Mathematik 1 SS09

Autoren

Michael Gäbler, Daniel Glaser

Approximation von Funktionen

Was bedeutet Approximation?

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

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.

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:

y = T(n) = a * b^n , mit b \geq 1

Der konstante Faktor a ist dabei der Schnittpunkt mit der y-Achse.

Nach einer Umformung dieser Allgemeinen Funktion ergibt sich die Gleichung:

Aus dieser Gleichung wird die Funktion als Gerade z = f(n) = n * α + β, mit z = log y, α = log b (ist der Anstieg der Geraden) und β = log a (Ist der Schnittpunkt mit der y-Achse), dargestellt.

Wie geht man nun in der Praxis vor?

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. Wenn sich dabei eine Gerade ergibt, so kann daraus die Funktion y = T(n) = a*b^n bestimmt werden. Dabei ist der Anstieg log b die Basis b und der konstante Faktor a der Schnittpunkt mit der y-Achse.

Mit Hilfe von Gnuplot kann man diese Funktionen grafisch darstellen.

Beispiel:

Darstellung der Funktionen T(n)= 10*2^n; T(n)=10000*2^n; und T(n)=10^n

Effizienz von Algorithmen: Exponentieller Aufwand

Des Weiteren stellen Exponentielle Funktionen mit der Form:

in einem kartesischen Koordinatensystem mit einer logarithmischen y-Achse eine Gerade dar.

Beispiel: Darstellung der Funktionen: T(x)=exp x; T(x)=exp 4^*^x; T(x)=3^x; T(x)=10*3^x; T(x)=10^2^*^x

Lineare Reggression

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

Als Lineare Regression bezeichnet man die mathematische Methode zur Bestimmung einer Geraden im logarithmischen Koordinatensystem, anhand der verstreuten Messpunkte. Dabei wird die Gerade y = f(n) = a*n+b gesucht. 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.

Bei der Linearen Regression geht man wie folgt vor:

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:

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.

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

Um das Minimum zu bestimmen, wird nun die erste Ableitung gebildet.

Da man das Minimum nach a und b benötigt, so muss jeweils nach a und b abgeleitet werden.

Ableitung nach a:

Ableitung nach b:

Durch Vereinfachung erhält man die sogennante Normalengleichung:

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

Somit erhält man die Parameter a und b für die Regressionsgerade:

Beispielrechnung:

folgende Meßwerte:

T(1)=3

T(2)=6

T(3)=7

T(4)=9

T(5)=11

In die Gleichung für a und b einsetzen!

Parameter für die Regressionsgerade im kartesischen Koordinatensystem.

Würde man die folgenden Messpunkte im logarithmischen Koordinatensystem als ansteigende Gerade erkennen so wäre die Gleichung zur Exponentialfunktion dieser Geraden

Wobei dan aber gelten muß : b=log (das a von der Regressionsgeraden oben)

dabei ergibt sich für unser Beispiel folgende Exponentialfunktion:

Polynomfunktion

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

Antwort: Es entsteht eine Kurve (Parabel).

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

Dabei wird aus:

z = f(log n) = α * log n + β, mit z = log y, α = k und β = log c.

Daraus folgt: log y = f(n) = log (c*n^k) = k * log n + log c, für n>0.

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

Der Anstieg mit der y-Achse bei n=1 gibt 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.

Ein Graph wird zur Gerade wenn beide Achsen logarithmisch eingestellt sind.
Bei Funtionen folgender Gestalt:

• T(n) = c*n^k, k \geq 1

Diese Funtion kann weiter beschrieben werden als:

• T(n) = c_1*n^{k_1} + c_2*n^{k_2} + ... + c_i*n^{k_i}

Daraus ergibt sich folgender Funktionsgraph mit normaler Achseneinteilung für:

• 2*n^{12}+10*x^2+1234*x

Dieser Graph ist keine Gerade, deshalb müssen wir die logarithmische Achseneinteilung wählen um auf das gewünschte Ergebnis zu kommen.
Funktionsgraph mit logarithmischer y-Achseneinteilung:

Funktionsgraph mit logarithmischer x- und y-Achseneinteilung:

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 ensteht.
Deshalb sind andere Untersuchungsmethoden notwendig um auf das gewünschte Ergebnis zu kommen.

Polynomfunktionen bestehen aus mehreren Basisfunktionen der folgenden Form:

• f(x)=c_0*g_0(x)+c_1*g_1(x)+ ... +c_m*g_m(x)

Die Lösung des Problems ergibt sich durch Anwenden der Methode der kleinsten Fehlerquadrate auf die Polynomfunktion.
Die Methode der kleinsten Fehlerquadrate angewandt auf die Formel:

• F(c_0,c_1,...,c_m)=\sum_{k=1}^{n}(\sum_{k=0}^{m}c_ig_i(x_k)-y_k)^2\rightarrow min

Das heißt die Summe der Abstände (n Messpaare, also n Abstände) zwischen der gesuchten Funktion und den Messwerten soll minimal werden. Dazu bildet man die Ableitung und setzt diese Null.

• \frac{\delta F}{\delta c_i}=2\sum_{k=1}^{n}(\sum_{k=0}^{m}c_ig_i(x_k)-y_k)*g_i(x_k)=0

Dazu multipliziert man die Ableitung aus und bringt y_k auf die rechte Seite.

• \sum_{i=0}^{m}(\sum_{k=1}^{n}g_i(x_k)*g_i(x_k))=\sum_{k=1}^{n}y_k*g_j(x_k)

Dabei ist g_j eine der Basisfunktionen zwischen 0 und m. Um eine Lösung für alle c zu erhalten, trägt man die Formeln in ein lineares Gleichungssystem ein. Um dieses dann zu lösen, werden für g_j alle Basisfunktionen angenommen. Um das besser repräsentieren zu können, wählt man eine Darstellung mit Hilfe von Matrizen

• A=\begin{pmatrix} g_0(x_1) & g_1(x_1) & \cdots & g_m(x_1) \\ g_0(x_2) & g_1(x_2) & \cdots & g_m(x_2) \\ \vdots & \vdots & \cdots & \vdots \\ g_0(x_n) & g_1(x_n) & \cdots & g_m(x_n)\end{pmatrix}

Der Faktor g_j ist die Transpornierte der Matrix A. Daraus ergibt sich die Form

• A^TA\vec c = A^T \vec y

Damit kann man dieses Gleichungssystem nach \vec c lösen und erhält die Faktoren für die einzelnen Polynome.

• \vec c=(c_0,c_1,...,c_m)^T

Maple-Worksheet (Maple 11)

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));
                      x:=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
                  y:=[0, 4, 9, 16, 25, 36, 49, 64, 81, 100]
                                           2        3
                  g:=x -> 1, x -> x, x -> x , x -> x 
                                    n:=10
                                     m:=3

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

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

Übungsaufgaben

Aufgaben

Folien

• Hier sind die Folien zur Vorlesung