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.

Abbild eines Näherungsverfahrens mit gegebenen Messwerten:

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 \left(n \right) = a \cdot 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 \left(n \right) = n \cdot \alpha + \beta , mit z = log\ y\ , \alpha = log\ b\ (ist der Anstieg der Geraden) und \beta = 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 \left(n \right) = a \cdot b^n bestimmt werden.

Mit Hilfe von Gnuplot kann man diese Funktionen grafisch darstellen.

Beispiel:

Darstellung der Funktionen T \left(n \right)= 10 \cdot 2^n; T \left(n \right)=10000 \cdot 2^n und T \left(n \right)=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 \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

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.

Als Lineare Regression bezeichnet man die mathematische Methode zur Bestimmung einer Geraden anhand der verstreuten Messpunkte. Dabei wird die Gerade y = f \left(n \right) = a \cdot 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:

Daraus entstehen folgende Endformeln:

Anhand verschiedener Messpunkte kann nun die Funktion bestimmt werden, damit eine Gerade entsteht. 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.:\sum \limits _{i=1}^r {i \cdot T \left(i \right) 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:

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

Parameter für die Regressionsgerade im kartesischen Koordinatensystem:

Die Regressionsgerade lautet: f(n)=0,6n + 4,6

Diese kann man nun einfach mithilfe von Gnuplot zeichnen:

Polynomfunktion

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

Es entsteht eine Kurve.

Polynome des Grades:

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

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

Dabei wird aus:

z = f \left( log\ n\ \right) = \alpha \cdot log\ n\ + \beta , mit z = log\ y, \ \alpha = k und \beta = log\ c\ .

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

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:

Und nun mit logarithmischer x-und y-Achse:

Wie sieht das ganz nun bei Polynomfunktionen aus:

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:

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

f(c_0,c_1,...,c_m,x)=\sum_{i=0}^{m}c_ig_i(x), mit Basisfunktionen gi:x\rightarrow x^i

anzuwenden.

Nun werden die Koeffizienten c_i , für i = 0,1,...,m gesucht.

Dabei wird die Methode der kleinsten Fehlerquadrate angewendet auf die Formel:

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 c_i und setzt diese gleich null.

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

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

g_j 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 g_j alle Basisfunktionen angenommen.

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

Mit \vec y = (y_1,...,y_n)^T und der Matrix:

ergibt sich die Normalgleichung in der Form:

Der reellwertige Vektor \vec c=(c_0,c_1,...,c_m)^T 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: c_0,c_1,...,c_m gesucht.

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

Dabei sind die Funktionen g_i beliebige Basisfunktionen.

Wie funktioniert diese Approximation?

Um die Approximationsfunktion zu bestimmen ist immer folgendes gegeben:

- Die Messwerte von x und y
- Die Basisfunktionen g_0, g_1,...,g_m

Gesucht sind die Koeffizienten c_0,c_1,...,c_m

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

Folien

• Hier sind die Folien zur Vorlesung