| Autor |
Beitrag |
    
Ueps (Ueps)
Neues Mitglied
Benutzername: Ueps
Nummer des Beitrags: 1
Registriert: 01-2005
| | Veröffentlicht am Samstag, den 22. Januar, 2005 - 11:19: | 
|
Hallo,
ich studiere Wirtschaftsinformatik und bin zwar in Mathe immer sehr gut gewesen, aber im Moment komm ich einfach auf keine Lösung bei meinem Problem.
Für eine Anwendung sollte ich aus beliebig vielen Punkten eine Funktion erzeugen, mit Hilfe dieser Funktion sollen die Punkte im nachhinein wieder genau (exakt) die alten Werte annehmen.
Hab mir hierzu diverse Interpolationsverfahren angeschaut, aber 1. ist das eine Nummer zu hoch für meine alten Mathe-Abi Kenntnisse und 2. wie stelle ich da sicher das ich auch exakt! die gewünschten Punkte wieder erhalte? Bei den Punkten handelt es sich um Ganzzahlige Werte (Integer).
Bsp.
x-Achse:
0,1,2,3,4,5,6,7,8....
y-Achse:
0,8,15,22,0,8,15,3,4.....
Wie kann ich nun eine Funktion f(x) realisieren, die mir z.B. für f(2) = 15 liefert?
Bitte habt verständnis für meine geringes Matheniveau, aber das Gymnasium ist lange her und als WI-ler kämpf ich grad noch mit anderen Problemen bei meinem Projekt.
Gruß,
Tobi |
Friedrichlaher (Friedrichlaher)
Senior Mitglied
Benutzername: Friedrichlaher
Nummer des Beitrags: 2591
Registriert: 02-2002
| | Veröffentlicht am Samstag, den 22. Januar, 2005 - 11:53: |
|
Hallo, Tobi,
das
ist allerdings wirklich eine sehr "wilde" Funktion.
Meist
handelt es sich, wenn es Aufgaben aus der Praxis
sind ja um, mit Fehlern behaftete, Mess/Erhebungs Werte,
und man sollte wenigstens eine ungefähre Vorstellung
von der Art der Funktion haben, deren Paramter
dann so gewählt werden, daß die Kurve sich
möglichst gut an die Punkte "schmiegt". ("Least Square" Methode )
Eine exakte Übereinstimmung wird kaum erzielbar
sein.
Exakte Übereinstimmung ergibt sich aber
wenn man fü n Punkte ein Polynom (m=n-1)ten Grades ansetzt:
f(x) = am*xm+am-1*xm-1+am-2*xm-2...+a1*x+a0
und dann
das Gleichungssystem
f(0) = y0
f(1) = y1
...
aufstellt ( in obiges Polynom die x Werte 0,1,.. einsetzen ) und ( nach den Unbekanten ai )löst.
Wenn das Erlernen der Mathematik einigermaßen ihre Erfindung wiederspiegeln soll, so muß es einen Platz für Erraten, für plausibles Schließen haben.
[Aus dem Vorwort zu "Mathematik und plausibles Schliessen, Bd. 1 Induktion und Analogie in der Mathematik" von Georg Pólya]
|
Orion (Orion)
Senior Mitglied
Benutzername: Orion
Nummer des Beitrags: 966
Registriert: 11-2001
| | Veröffentlicht am Samstag, den 22. Januar, 2005 - 14:35: |
|
Hallo Tobi,
Das folgende Verfahren geht auf Newton zurück.
Ich zeige es am Beispiel von 4 Punkten:
(0,0) , (1,8) , (2,15), (3,22).
Es gibt genau eine Polynomfunktion 3. Grades,
(1) f(x) = a + bx + cx2 + dx3
deren Graph (eine kubische Parabel) durch diese Punkte verläuft. Statt (1) macht man praktischerweise
den Ansatz
(2) f(x) =
A + B(x-0) + C(x-0)(x-1) +
+D(x-0)(x-1)(x-2)
Damit kann man die Koeffizienten A,B,C,D rekursiv
berechnen (als Informatiker wird Dir das sicher sympatisch sein):
f(0)=0 <=> A = 0
f(1)=8 <=> A+B=8 => B = 8
f(2) = 15 <=> A + 2B + 2C = 15 =>
C = - 1/2
f(3) = 22 <=> A + 3B + 6C + 6D = 22
=> D = 2/3
Also
f(x) = 8x - (1/2)x(x-1) + (2/3)x(x-1)(x-2)
Das kann man nun noch ausmultiplizieren und nach
Potenzen von x ordnen.
Allgemein : sind (x0,y0),...,(xn,yn) die
gegebenen Punkte (wobei yi ‡ yk für
i ‡ k), so macht man den Ansatz
f(x) = A0 + A1(x-x0) + A2(x-x0)(x-x1)
+ ... + An(x-x0)(x-x1)*...*(x-xn-1)
und bestimmt der Reihe nach A0 = y0 ,
A1 = (y1-y0)/(x1-x0), ....
mfG Orion
|
Christian_s (Christian_s)
Senior Mitglied
Benutzername: Christian_s
Nummer des Beitrags: 1715
Registriert: 02-2002
| | Veröffentlicht am Samstag, den 22. Januar, 2005 - 14:56: |
|
Hallo Tobi
Man kann auch das sogenannte Langrange'sche Interpolationspolynom benutzen. Mit den Bezeichnungen von Orion erhält man das Polynom f mit
f(x)=Sn i=1yi*P(x-xj)/(xi-xj), wobei das Produkt über j=1,..,n läuft mit j¹i.
Du kannst sofort nachrechnen, dass dann f(xk)=yk gilt für k=1,..,n.
Für die Praxis ist aber wohl das von Orion angegebene Verfahren von Newton das bessere.
MfG
Christian |
Ueps (Ueps)
Neues Mitglied
Benutzername: Ueps
Nummer des Beitrags: 2
Registriert: 01-2005
| | Veröffentlicht am Mittwoch, den 02. Februar, 2005 - 15:15: |
|
Danke für eure Antworten.
Ich hab die verschiedenen Versionen mal versucht und dass klappt auch. Was mich jedoch noch interssieren würde:
Für eine Funktion für n-Punkte bräuchte man ja folglich (nach dem Beispiel von Orion) eine Polynomfunktion (n-1)ten Grades, oder?
Angenommen ich hätte 100 Punkte, Ziel meiner Überlegungen war es, eine Funktion zu bekommen, die möglichst "klein" ist und mir zu jedem x Wert den passenden y-Wert der Punkte liefert. Aber so wäre die Funktion genauso lang wie die Anzahl der Punkte.
Vielleicht beschreib ich mein Problem mal noch genauer.
Ich habe 16 verschiedene Zeichen. Die Zeichen können unterschiedlich hintereinander gereit werden und auch beleib oft vorkommen. Sagen wir mal insgesamt sollen 5000 Zeichen aneinander gereiht werden.
Diesen Sachverhalt wollte ich nun mit möglichst geringem Aufwand reproduzieren. D.h. wenn die Positionen der einzelnen Zeichen bekannt sind, will ich die Position des Zeichens in der Kette (y-Wert) und die Nummer des Zeichens (Aktuelle Wiederholung) als Punkt ansehen und aus diesen Punkten quasi pro Zeichen eine Funktion generieren.
Bsp:
ABCDDDDDAAAABBBEDDEADEEFA
Zeichen A hätte also die Punkte:
(1,1) (2,9) (3,10) (4,11) (4,12) (5,20) (6,25)
Also wär die z.B. die Polynomfunktion 6ten Grades geeignet, aber in dem Fall genauso lang oder länger als sich die Punkte einzeln zu "merken".
Hoffe das war jetzt nicht zu konfus? |
Orion (Orion)
Senior Mitglied
Benutzername: Orion
Nummer des Beitrags: 974
Registriert: 11-2001
| | Veröffentlicht am Mittwoch, den 02. Februar, 2005 - 15:39: |
|
Toby,
Müsste es nicht heissen
(1,1),(2,9),(3,10),(4,11),(5,12),(6,20),(7,25) ?
mfG Orion
|
Friedrichlaher (Friedrichlaher)
Senior Mitglied
Benutzername: Friedrichlaher
Nummer des Beitrags: 2618
Registriert: 02-2002
| | Veröffentlicht am Mittwoch, den 02. Februar, 2005 - 15:46: |
|
auweh, Tobi, als digitales Kompressionsverfahren
ist das natürlich total ungeeignet. Google nach
kompressions.
Wenn das Erlernen der Mathematik einigermaßen ihre Erfindung wiederspiegeln soll, so muß es einen Platz für Erraten, für plausibles Schließen haben.
[Aus dem Vorwort zu "Mathematik und plausibles Schliessen, Bd. 1 Induktion und Analogie in der Mathematik" von Georg Pólya]
|
Murray (Murray)
Erfahrenes Mitglied
Benutzername: Murray
Nummer des Beitrags: 243
Registriert: 10-2001
| | Veröffentlicht am Mittwoch, den 02. Februar, 2005 - 18:09: |
|
Hallo Tobi,
Du kannst Dir mal das LZW-Verfahren anschauen, wenn Du Deine Daten nicht unbedingt in ein Polynom packen mußt.
http://informatik.uibk.ac.at/users/c70301/teaching/ss2003/material/compress/stolz.pdf
Dein Alphabet ist dann nur 16 Zeichen groß, nicht 256 wie in diesem Beispiel und wenn Du nur die Positionen von "A" speichern muß, dann könntest Du Dein Alphabet auf zwei Zeichen kürzen.
Bsp:
ABCDDDDDAAAABBBEDDEADEEFA
1000000011110000000100001
Die letzte Zeile kann man nun noch mittels LZW verkürzen (siehe Doku).
Onkel Murray |
Ueps (Ueps)
Neues Mitglied
Benutzername: Ueps
Nummer des Beitrags: 3
Registriert: 01-2005
| | Veröffentlicht am Donnerstag, den 10. Februar, 2005 - 13:45: |
|
Hi,
@Orion: ja da hab ich mich wohl vertippt es müsste
(1,1),(2,9),(3,10),(4,11),(5,12),(6,20),(7,25) heissen!
@Murray: ja das ginge natürlich, wenn es denn nur die Position vom A wäre.
Von LZW hab ich natürlich auch schon mal was gehört, mich aber gefragt ob es nicht auch möglich wäre, aus n-Punkten eine Funktion zu erstellen, die eben in der Summe kleiner an Bytes ist, als die Punkte normal aufzuschreiben. Da ja die 16 verschiedenen Zeichen 0-F in "regelmäßigen" abstanänden auftauchen und sich so eine evtl. vorhandene Struktur mittels einer kürzeren Formel beschreiben lässt.
z.B. man hat eine Datei die nur aus AAAAAAAAAA... besteht. Der Abstand von einem A zum anderen beträgt genau 1. Also wäre die funktion f(a) = a
2. Beispiel:
ABABABABABABABABAB....
f(a) = 2a
f(b) = 2b+1
Die Funktionen wären kürzer wenn die Datei z.B. mehrere MByte groß wäre.
So gesehen hab ich überlegt ob andere Zusammenhänge die nicht so trivial erscheinen, mathematisch erfassbar sind, wenn alle "Punkte" bekannt sind.
War nur mal eine Vermutung, wie es scheint wohl eine falsche.
Gruß,
Tobi
(Beitrag nachträglich am 10., Februar. 2005 von ueps editiert)
(Beitrag nachträglich am 10., Februar. 2005 von ueps editiert) |
|
