Approximation von Meßwerten durch eine beliebige Funktion

Jester

@Krösus:http://www.c-plusplus.net/forum/viewtopic.php?t=56799&start=0 gleich im ersten Beitrag steht's... zumindest vermute ich, daß es daran liegt

Winn

Ich kann WebFritzi verstehen, denn ich verstehe auch nicht wirklich was Du beabsichtigst...

Also ich beiße mich schon an der Betreffzeile, denn "Approximation von Meßwerten durch eine beliebige Funktion" schließt sich in sich schon aus, denn Du möchtest ja eigentlich durch eine Approximation "Meßwerte" berechnen, die wohl anscheinend "zwischen" den gemessenen Meßwerten oder "auf" der Zeit Koordinate liegen - und das geht ja nicht mit einer "beliebigen Funktion" ?!

Präsesieren wir weiter... in der Numerik gibt es die Approximation und die Interpolation.

Approximation - Entwicklung einer Funktion die möglichst glatt (differenzierbar möglichst), mit einer möglichst kleinen Abweichung von den gemessenen Werten, verläuft. Und dadurch einem möglichen Abbild der unbekannten Funktion entspricht auf die die Meßwerte beruhen.
Da gibt es die:

Fourierreihen, Verfahren von Runge
Orthogonale Polynome, Tschebyscheff oder Legendre Polynome

Interpolation - Entwicklung einer Funktion die Werte zwischen Meßwerten möglichst genau widergeben, ohne dabei die eigentliche Funktion zu kennen auf die die Meßwerte beruhen.

Lagrange Interpolation
Newton Interpolation
Rationale Interp.
Spline
Bezier

Spontan würde ich Dir eher zu der Interpolation raten, da die Approximation mit steigender Anzahl von Meßwerten komplexer wird, das gilt sicherlich auch für die Interpolation, aber aus einem Bauchgefühl herraus traue ich der Interpolation mehr und das auch, weil sie wesentlich einfacher in einer Programmiersprache umzusetzen ist. Jedem aber so wie es einem gefällt

fubar

Winn schrieb:

Da gibt es die:

Fourierreihen, Verfahren von Runge

Orthogonale Polynome, Tschebyscheff oder Legendre Polynome

Die IMHO alle auf diskreter/kontinuierlicher Gaussapproximation basieren!
Dabei können die Ansatzfunktionen aber beliebig gewählt werden (Tschebyscheff-, Laguerre- oder Legendre-Polynome [...] bieten halt den Vorteil, daß das Normalgleichngssystem eine sehr einfache Gestalt hat (da die Funktionen orthogonal sind), was übrigens auch für die Fouriertransformation gilt...).

Winn schrieb:

Interpolation - Entwicklung einer Funktion die Werte zwischen Meßwerten möglichst genau widergeben, ohne dabei die eigentliche Funktion zu kennen auf die die Meßwerte beruhen.

Vielleicht sollte man noch dazu sagen, daß bei Interpolation stets f(x_i)=y_i gilt, was natürlich bei der Approximation nicht der Fall ist!
Man versucht Polynome zu finden, die die Meßpunkte _genau_ treffen...

Winn schrieb:

Spontan würde ich Dir eher zu der Interpolation raten, da die Approximation mit steigender Anzahl von Meßwerten komplexer wird, das gilt sicherlich auch für die Interpolation, aber aus einem Bauchgefühl herraus traue ich der Interpolation mehr und das auch, weil sie wesentlich einfacher in einer Programmiersprache umzusetzen ist.

Von Interpolation würde ich dir auf jeden Fall abraten:

Krösus schrieb:

... ~ 9000, Stützstellen ...

Bei so einer "Datenwolke" würde ich auf jeden Fall zu diskreter GA raten!
Nach Wahl der Anstzfunktionen phi_i stellst du das NGS auf und berechnest so die Koeffizienten alpha_i, sodaß deine Gesuchte Funktion y=sum(alpha_i*phi_i) herauskommt.

Winn

fubar schrieb:

Winn schrieb:

Interpolation - Entwicklung einer Funktion die Werte zwischen Meßwerten möglichst genau widergeben, ohne dabei die eigentliche Funktion zu kennen auf die die Meßwerte beruhen.

Vielleicht sollte man noch dazu sagen, daß bei Interpolation stets f(x_i)=y_i gilt, was natürlich bei der Approximation nicht der Fall ist!
Man versucht Polynome zu finden, die die Meßpunkte _genau_ treffen...

Schwachsinn ! Warum soll bei der Interpolation stets f(x_i)=y_i sein ? Spline Funktionen dürften wohl schon per Definition nicht so sein, wie Du behauptet hast...

fubar schrieb:

Winn schrieb:

Spontan würde ich Dir eher zu der Interpolation raten, da die Approximation mit steigender Anzahl von Meßwerten komplexer wird, das gilt sicherlich auch für die Interpolation, aber aus einem Bauchgefühl herraus traue ich der Interpolation mehr und das auch, weil sie wesentlich einfacher in einer Programmiersprache umzusetzen ist.

Von Interpolation würde ich dir auf jeden Fall abraten:

Krösus schrieb:

... ~ 9000, Stützstellen ...

Bei so einer "Datenwolke" würde ich auf jeden Fall zu diskreter GA raten!
Nach Wahl der Anstzfunktionen phi_i stellst du das NGS auf und berechnest so die Koeffizienten alpha_i, sodaß deine Gesuchte Funktion y=sum(alpha_i*phi_i) herauskommt.

So ein großes Gleichungssystem möchtest Du lösen ??? Wie möchtest Du das in C/C++ implementieren ?

Wie auch immer, wenn Krösus eine Funktion berechnen möchte bzw. nachher als analytischen Ausdruck haben möchte, dann ist die Approximation sein Wahl, wenn er eine numerische Annäherung haben möchte, dann ist die Interpolation sicherlich die bessere Wahl. Für Bauanleitungen findet sich hier -> http://www.library.cornell.edu/nr/cbookcpdf.html bestimmt etwas...

WebFritzi

Winn schrieb:

fubar schrieb:

Winn schrieb:

Interpolation - Entwicklung einer Funktion die Werte zwischen Meßwerten möglichst genau widergeben, ohne dabei die eigentliche Funktion zu kennen auf die die Meßwerte beruhen.

Vielleicht sollte man noch dazu sagen, daß bei Interpolation stets f(x_i)=y_i gilt, was natürlich bei der Approximation nicht der Fall ist!
Man versucht Polynome zu finden, die die Meßpunkte _genau_ treffen...

Schwachsinn ! Warum soll bei der Interpolation stets f(x_i)=y_i sein ? Spline Funktionen dürften wohl schon per Definition nicht so sein, wie Du behauptet hast...

Doch, i.A. ist das bei der Interpolation so. Auch bei Splines.

Winn

WebFritzi schrieb:

Doch, i.A. ist das bei der Interpolation so. Auch bei Splines.

Okay, dann frag ich mal anders herum, was versteht ihr unter f(x_i)=y_i ? Bzw. warum sollte das bei der Approximation nicht so sein oder so sein ? Und bei der Interpolation ausschließlich nur f(x_i)=y_i gelten ?

Okay, generelle Frage... aber ich glaube hier entwickelt sich ein Mißverständnis, entweder vom Niedergeschriebenen oder vom Stoff her...

fubar

Winn schrieb:

Schwachsinn ! Warum soll bei der Interpolation stets f(x_i)=y_i sein ?

Aber das ist doch gerade der Sinn der Interpolation

Winn schrieb:

Spline Funktionen dürften wohl schon per Definition nicht so sein, wie Du behauptet hast...

Doch per definitionem ist es genau so!

Winn schrieb:

So ein großes Gleichungssystem möchtest Du lösen ??? Wie möchtest Du das in C/C++ implementieren ?

Die Matrix des NGS ist aus IR^Anzahl der Ansatzfunktionen², also nicht abhängig von der Anzahl der Stützstellen, d.h. problemlos in C/C++ umzusetzen.

Edit: Sorry, hatte deinen Beitrag noch nicht gelesen. Vielleicht reden wir ja aneinander vorbei.

fubar

Nehmen wir mal an, wir haben (n+1) paaweise versch. Stützstellen x_0,...,x_n und die zugehörigen Stützwerte y_0,...,y_n.
Gesucht wir nun ein(/das eindeutig bestimmte) Polynom P n-ten Grades, das die Interpolationsbedingungen P(x_i)=y_i erfüllt!

Dieses kann man z.B. durch Lagrange/Newton-Interpolation finden.

Bei mehr als ~7 Stützstellen fangen diese Interpolationspolynome an zu "oszillieren".

Jetzt könnte man z.B. auf kubische Splineinterpolation umsteigen.

Hat man aber eine große Anzahl Meßwerte, die natürlich mit Meßfehlern behaftet sind, ist Interpolation nicht sehr sinnvoll. Hier nimmt man dann IMHO Approximation.

Edit:

Als (zugegebenermaßen konstruiertes) Bsp.:
Stützstellen:
x y
0 0
1 2
2 2
3 4
4 4
5 6
6 6
7 8
8 8
9 10

Das interpolierende Polynom P=sum(a_i*x^i, i=0..9) hätte die Koeffizienten:

3,24840340502144E-6 // a_0
68,4264735655574
-166,634400171086
162,906874766606
-83,6968066168767
25,0704576308921
-4,53133321606725
0,486557471969308
-0,0285588171212395
0,000705156601175834 //a_9

Stellt man das jetzt graphisch dar, sieht man, daß dieses Polynom zwar die Punkte interploiert, aber nicht den "erwarteten" Verlauf aufweist...

Winn

fubar schrieb:

Nehmen wir mal an, wir haben (n+1) paaweise versch. Stützstellen x_0,...,x_n und die zugehörigen Stützwerte y_0,...,y_n.
Gesucht wir nun ein(/das eindeutig bestimmte) Polynom P n-ten Grades, das die Interpolationsbedingungen P(x_i)=y_i erfüllt!

gg, okay, dann haben wir uns mißverstanden... das die Interpolationsbedingung f(x_i)=y_i sein muß ist klar, gg... dachte Du meinst damit die interpolierten also die berechneten Werte die die Meßwerte quasi "ergänzen".

Das die Wahl des Interpolations oder des Approximations Verfahren stark von den Meßwerten abhängt, ist zumindest aus meiner Sicht klar. Eine "ungefähre" Vorstellung über die dahinter liegende Funktion ist unabdingbar für die "richtige" Wahl...

Bei Deinem Beispiel würde ich z.B. das Differenzenverfahren anwenden (f(x1)-f(x0))/2

wenn Ihr die wirkliche Funktion hinter einer Messreihe kennt dann gratuliere ich euch.
Mag der sachverhalt auch einen gesetz wie y=e^x gehorchen, werden Messwert doch davon abweichen und dass die Fehlerfunktion bekannt oder mit 100% sicherheit zu bestimmen ist bezweifle ich doch stark.
Approximieren und Interpolieren sind Begriffe aus der glechen Werkzeugkiste, nur schliessen sich beide nicht aus.
Das Verfahren zur Bestimmung einer gesuchten Funktion ist die Approximation (Parameter Schätzung).
Das Verfahren zur Werte Berechnung, mit dieser Funktion, innerhalb eines Messwerte Intervalls, ist die Interpolation.

fubar

.b7f7 schrieb:

wenn Ihr die wirkliche Funktion hinter einer Messreihe kennt dann gratuliere ich euch.
Mag der sachverhalt auch einen gesetz wie y=e^x gehorchen, werden Messwert doch davon abweichen und dass die Fehlerfunktion bekannt oder mit 100% sicherheit zu bestimmen ist bezweifle ich doch stark.

Hat das denn irgendeiner behauptet?

.b7f7 schrieb:

Approximieren und Interpolieren sind Begriffe aus der glechen Werkzeugkiste, nur schliessen sich beide nicht aus.

Könntest du das vielleicht mal etwas genauer erklären, verstehe den Sinn noch nicht so ganz?

fubar schrieb:

.b7f7 schrieb:

Approximieren und Interpolieren sind Begriffe aus der glechen Werkzeugkiste, nur schliessen sich beide nicht aus.

Könntest du das vielleicht mal etwas genauer erklären, verstehe den Sinn noch nicht so ganz?

bei der Approximation bestimmt man die Funktionsparameter welche man zum Interpolieren(einfügen) von Zwischenwerten benutzt.

Krösus

Also der Tip von .b7f7 (#7) hat meine Frage genau getroffen.
Ich kam dann darauf, daß ich nach "Levenberg-Marquardt" oder auch nach "Gauß-Newton-Verfahren" suchen muß und habe tatsächlich auch zwei programmiertechnische Implementierungen gefunden (leider in FORTRAN und Java, nicht C): http://www.zib.de/SciSoft/CodeLib/codes/nlscon/nlscon.f
http://www.idiom.com/~zilla/Computer/Javanumeric/LM.java
Vielen Dank an alle für die Diskussion!

www.nr.com
da sind c implementationen zu L/M