Kubische Spline-Interpolation |
| 12.02.2017, 22:54 | Fridde | Auf diesen Beitrag antworten » | ||||||||
| Kubische Spline-Interpolation Hallo zusammen! Ich schreibe eine Facharbeit über Spline-Interpolation, speziell kubische Splines. Ich habe mir schon Lehrbücher für Studenten ausgeliehen und im Internet mathematische Arbeiten durchgelesen, aber für mich ist das alles sehr kompliziert. Ich bin in der 11. Klasse auf einem Gymnasium und viele der ganzen mathematischen Zeichen, habe ich noch nie verwendet und habe keine Ahnung, was sie bedeuten. Wenn ihr mir helfen wollt, wär es gut, wenn ihr euch auf diese Facharbeit bezieht, damit alles einheitlich bleibt. http://moritz.faui2k3.org/files/facharbeit_splines.pdf Zu meinen Problemen: 1. Was ist i und was ist n? Und warum n-1? 2. Guckt mal bitte die Abb. (3.1.1) an. Warum ist da einmal da? Also warum ist da i und dann n-2? 3. Ab Seite 7, kann ich die Schritte nicht mehr richtig nachvollziehen. Da kommt plötzlich h ins Spiel und ich blick überhaupt nicht mehr durch. Wär nice wenn jemand die Seiten 7-10 erklären könnte. 4. Was bedeutet der Doppelpunkt und das Gleichheitszeichen? Ich würde mich sehr über eine Antwort freuen!!! Meine Ideen: 1. n gibt die Menge der Stützstellen an und i, welche Stützstelle welche ist. 2. Echt keine Plan. |
||||||||||
| 13.02.2017, 09:31 | Steffen Bühler | Auf diesen Beitrag antworten » | ||||||||
RE: Kubische Spline Interpolation
Das hast Du Dir ja schon selbst beantwortet: n ist die Anzahl der Stützstellen und i die laufende Nummer. Die Ungleichung sagt aus, dass die Punkte von links nach rechts angeordnet sind, jede x-Koordinate eines Punktes also größer ist als die seines Vorgängers. Da es n Punkte sind, hat der erste Punkt die Nummer 0 und der letzte die Nummer n-1.
Hier geht es um die Verbindungskurven zwischen den n Punkten. Bei drei Punkten gibt es zwei Kurven, also immer eine weniger. Und da man auch hier bei Null anfängt, landet man bei n-2.
Ich schlage vor, Du liest Dir erst mal unseren Workshop dazu durch. Dann wird hoffentlich einiges klarer. Ansonsten frag hier einfach weiter.
Das ist mathematisch für "sei definiert als". Viele Grüße Steffen |
||||||||||
| 21.02.2017, 17:45 | Fritzelchen | Auf diesen Beitrag antworten » | ||||||||
| RE: Kubische Spline Interpolation Ok danke! Das hat mir schon mal weiter geholfen. Ich habe aber jetzt neue Fragen: 1. Welche Verfahren zur Berechnung eines kubischen Splines gibt es? Ich habe jetzt im Internet fast überall das Verfahren gesehen, bei dem man die Koeffizienten a, b und d von dem Koeffizienten c abhängig macht. Man muss also nur noch die c-Koeffizienten bestimmen und kann so alle anderen durch einsetzen in die entsprechenden Formeln berechnen. Von einem Lehrer aus meiner Schule habe ich habe Blätter aus einem Schulbuch bekommen, wo ein Verfahren beschreiben wird, bei dem man alle Koeffizienten auf einmal in einem LGS berechnet. Dies scheint mir erstmal einfacher zu sein, weil dieses Verfahren Ähnlichkeiten mit den Trassierungsproblemen in der Schule hat. Also warum wird nicht dieses Verfahren im Internet beschrieben? Und gibt es auch noch andere Verfahren? Und so komm ich auch zu meiner nächsten Frage. 2. Warum keine sukszessive Berechnung? Wenn man Intervall für Intervall die Polynome 3. Grades berechnen würde, ginge dies doch auch. Für das erste Polynom hätte man dann die Bedingungen für die Stützpunkte links und rechts . Und die erste und zweite Ableitung könnte man an der linken Stelle jeweils einem beliebigen Wert gleichsetzen. Für das zweite Polynom hätte man dann die Stützpunkte und . Danach würde man gucken welche Werte die erste u. zweite Ableitung des ersten Polynoms an der Stelle jeweils haben und würde diese Werte mit der ersten u. zweiten Ableitung des zweitem Polynoms an der Stelle gleichsetzen. So hätte man ja für jedes Polynom 4 Bedingungen und könnte so Schritt für Schritt fortfahren. 3. Wie kann man bei der im Internet beschriebenen Methode Extremstellen an einer bestimmten Stützstelle erzwingen? Hat auch mit meiner zweiten Frage zu tun. Wenn ich einen Achterbahnschienenverlauf mit einer Splinefunktion beschreiben will und eine der Stützstellen ist auf dem höchsten Punkt der Achterbahn. Wie kann ich dann an dieser Stelle einen Hochpunkt der Splinefunktion erzwingen? Danke für eure Antworten 
|
||||||||||
| 22.02.2017, 08:53 | Steffen Bühler | Auf diesen Beitrag antworten » | ||||||||
| RE: Kubische Spline Interpolation Prinzipiell funktioniert die sukzessive Berechnung natürlich immer. Da aber immer jeweils zwei Punkte und deren Steigungen identisch sind, kann man sich einiges an Rechnerei sparen. Daher sieht solch ein Gesamtansatz zwar zunächst monströs aus, spart unterm Strich aber dann doch Rechenzeit, besonders wenn er als Algorithmus programmiert wird. Wobei das wiederum in Zeiten, wo wir uns dem Exaflop nähern, fast schon wieder vernachlässigbar ist... Einen Hochpunkt "erzwingst" Du automatisch, indem Du die Steigung der beiden angrenzenden Kurven auf Null setzt. Wenn die jeweils anderen Punkte dieser Kurven niedrigere y-Werte haben, wird zwangsläufig ein Hochpunkt daraus. Viele Grüße Steffen PS: da Du Dich ja nun angemeldet hast: herzlich willkommen! |
||||||||||
| 28.02.2017, 22:29 | Fritzelchen | Auf diesen Beitrag antworten » | ||||||||
RE: Kubische Spline Interpolation
Wie meinst du das mit den jeweils zwei Punkten?
Man hat ja eigentlich an den inneren Stützpunkten die Gleichung . Damit ist also an der Stelle die Ableitung mit einer Gleichung gleichgesetzt. Wenn ich jetzt aber den Hochpunkt mit und erzwinge, habe ich ja jetzt 2 Gleichungen statt einer!!!???
Hier habe ich ein Screenshot von einer Seite, auf der Splinefunktionen automatisch durch Stützpunkte interpoliert werden. Bei dieser Splinefunktion hat der Punkt 1 den höchsten y-Wert, aber dort ist trotzdem kein Hochpunkt. Danke für Antworten
|
||||||||||
| 01.03.2017, 09:45 | Steffen Bühler | Auf diesen Beitrag antworten » | ||||||||
| RE: Kubische Spline Interpolation Ach, jetzt verstehe ich Dich erst. Nein, ein erzwungener Hochpunkt ist bei der kubischen Interpolation in der Tat nicht vorgesehen. Dafür müsste man dann mit Ordnung 4 rangehen. Mit den "zwei Punkten" meine ich den Endpunkt eines Splines und den Anfangspunkt des folgenden. Da diese in Wert und Steigung identisch sind, kann man hier einiges gleichsetzen, wenn man die "Gesamtansicht" betrachtet. Genau das wird bei dem LGS-Ansatz getan. |
||||||||||
| Anzeige | ||||||||||
|
|
||||||||||
| 01.03.2017, 15:54 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||
Sagen wir es so: Es wäre höchst unüblich. Allerdings hat man bei kubischen Splines zwei Freiheitsgrade übrig, deren Verwendung unterschiedlich gehandhabt wird - ein paar Möglichkeiten sind ja auch in dem Screenshot von Fritzelchen ersichtlich. a) natürliche Splines: Null Krümmung an den beiden Enden, d.h. b) periodische Splines: gleiche Ableitung und Krümmung an den beiden Enden, d.h. und c) Und man kann sich natürlich auch vorstellen, lokale Extremalstellen per für irgendein (z.B. auch am Stützpunkt selbst) zu erzwingen, was auch entsprechend jeweils einen Freiheitsgrad verbraten würde, man kann das also maximal zweimal pro Gesamtspline machen. |
||||||||||
| 01.03.2017, 16:55 | Fritzelchen | Auf diesen Beitrag antworten » | ||||||||
Ok angenommen ich erzwinge eine Extremstelle nicht an einem Stützpunkt, sondern bei mit . So dann habe ich nur noch einen Freiheitsgrad für die beiden Enden der Splinefunktion zu verfügen und muss mich entscheiden welches Ende wichtiger ist. Aber für das Polynom habe ich ja dann 5 Gleichungen, für die 4 Koeffinzienten?? |
||||||||||
| 01.03.2017, 17:05 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||
So kann man das nicht sagen: Du hast bereits ohne die Freiheitsgradbedingungen sogar schon 6 Gleichungen für jedes Intervall (außer den beiden äußeren), nämlich jeweil drei (Funktion, erste und zweite Ableitung) an beiden Randpunkten des Intervalls. Allerdings sind in die entsprechenden Gleichungen nicht nur die Koeffizienten des aktuellen, sondern auch der betreffenden Nachbarintervalle involviert, deswegen kann man es nicht so simplifiziert betrachten, wie du es da gerade tust. |
||||||||||
| 01.03.2017, 19:52 | Fritzelchen | Auf diesen Beitrag antworten » | ||||||||
RE: Kubische Spline Interpolation
Bei welchem Algorithmus wird dies getan? Bei dem Algorithmus der hier (warum kann ich keine links einfügen? 
, ihr müsst bei google tm-aktuell eintippen und auf dieser Seite zu den "Natürlichen Splines" gehen) beschrieben wird, setzt man ja auch die Ableitungen an den Stützstellen gleich, aber dann wird ja alles von den c-Koeffizienten abhängig gemacht und dieser werden im LGS berechnet. |
||||||||||
| 01.03.2017, 20:03 | Fritzelchen | Auf diesen Beitrag antworten » | ||||||||
Mhh ok...aber ich komme immer noch nicht so ganz darauf klar. Kennst du eine Internetseite oder ein Buch, wo alles mit den Splinefunktionen und der Herleitung des Algorithmus alles "schülerfreundlich" erklärt ist? Zu meinem Problem mit dem Hochpunkt ist mir eine Idee gekommen: Man könnte doch an der Stützstelle, wo der Hochpunkt sein soll, die Splinefunktion beenden. Da man ja an den Rändern jeweils eine Gleichung übrig hat, könnte man ja da die erste Ableitung gleich null setzen. An genau diesem Stützpunkt würde dann auch eine neue Splinefunktion beginnen. Bei der setzt man dann auch die erste Ableitung an diesem Stützpunkt gleich null. Ich hab nur meine Bedenken mit der Krümmung an dieser Stelle. Die wäre ja dort nicht gleich, oder ist das nicht so schlimm? Und falls das gehen sollte, wie gehen diese Gleichungen dann in die Berechnung der Koeffizienten ein? |
||||||||||
| 01.03.2017, 20:55 | Steffen Bühler | Auf diesen Beitrag antworten » | ||||||||
Links kannst Du erst ab zehn Beiträgen posten. Diese und diese Seite kennst Du schon? Ich habe vor Jahren auch mal eine sehr gute Einführung für Anfänger im Netz gesehen, aber die scheint es leider nicht meht zu geben. |
||||||||||
| 02.03.2017, 22:42 | Fritzelchen | Auf diesen Beitrag antworten » | ||||||||
Die erste Seite kenne ich, denn die habe ich ausgedruckt von einem Lehrer bekommen, der mich auf das Thema gebracht hat. Die zweite Seite kannte ich nicht, aber die scheint sehr gut erklärt zu sein (wobei ich die Umformungen immer noch nicht checke). Vielen Dank 
Danke für deine Antwort! |
||||||||||
| 03.03.2017, 09:44 | Steffen Bühler | Auf diesen Beitrag antworten » | ||||||||
Das ist schwer zu beantworten. Es ist ähnlich wie bei der Fouriertransformation. Da gibt es in der Originalformel wegen der Symmetrie des Sinus auch viele Multiplikationen, die unnötigerweise mehrfach durchgeführt werden. Deswegen haben sich die Mathematiker in den 60ern hingesetzt und einen Algorithmus (die FFT) entwickelt, der jede notwendige Multiplikation nur ein einziges Mal benötigt. Denn die Prozessoren waren langsam und Multiplikationen erst recht. Das wurde dann sogar noch einmal verfeinert, weil die üblichen Eingangswerte ja reell sind, man also davon ausgehen kann, dass der Imaginärteil zunächst Null ist, was erneut Rechenzeit spart. Ich hatte solch einen Algorithmus vor 30 Jahren in Assembler implementiert, damit eine 1024-Punkte-FFT in weniger als einer halben Sekunde berechnet werden konnte. Bei einem Prozessortakt von 8 MHz. Aber die Programme und Formeln, die dadurch entstanden, sind sehr hässlich und kaum nachvollziehbar. Und so ist es wie bei den Splines eben auch. Sie werden vielleicht doppelt so schnell berechnet, aber das Erklären der Formel füllt mehrere Seiten. Und sprengt vielleicht den Rahmen einer Facharbeit. Wie schon erwähnt, sind die Rechner heute so schnell, dass man nicht mehr merkt, ob Excel die Splines durch hundert Punkte nun nach diesem oder jenem Algorithmus bestimmt hat. Das heißt nicht unbedingt, dass man die schnellen Routinen wegschmeißen sollte. Aber es sollte zwischen Effizienz und "Wartbarkeit" abgewogen werden. Ein supersuperschneller Algorithmus, in den sich ein neuer Programmierer aber erst eine Woche einarbeiten muss, könnte aus diesen Gründen durchaus einem nur superschnellen Algorithmus zum Opfer fallen, weil der besser verstanden wird und damit auch weniger fehleranfällig ist. So etwas entscheidet dann der Softwaremanager. Meine Empfehlung aufgrund dieser praktischen Erfahrung ist daher, den "einfachen" Algorithmus zu erklären und nur darauf hinzuweisen, dass es Optimierungspotential gibt. Viele Grüße Steffen |
||||||||||
| 10.03.2017, 14:55 | Fritzelchen | Auf diesen Beitrag antworten » | ||||||||
Vielen Dank für die Erklärung! Dann werde ich jetzt das "einfache Verfahren" benutzen. Ich wollte nur noch fragen, mit welchem Programm ich am besten mein LGS lösen lassen soll. Ich habe GeoGebra auf dem PC, mir steht ein CAS-Rechner zur Verfügung und ich habe Excel. Meine zweite Frage ist, wie man am besten die Stützstellen wählt. Klar, je mehr Stützstellen, desto genauer. Aber sollte man auf die Extremstellen eine Stützstelle setzte usw.? Gibt es Nachteile, wenn die Abstände zwischen den Stützstellen nicht überall gleich sind? Hier ist meine Achterbahn, deren Schienenverlauf ich in meiner Facharbeit durch eine Splinefunktion beschreiben möchte. [attach]44076[/attach] |
||||||||||
| 10.03.2017, 15:14 | Steffen Bühler | Auf diesen Beitrag antworten » | ||||||||
Hm, wenn ich mir das so ansehe, habe ich das Gefühl, das die "sukzessive" Methode hier am sinnvollsten wäre. Es kann natürlich sein, dass der Lehrer partout ein Riesen-LGS gelöst bekommen will (ich hab hier nur ein uraltes Mathcad, das für meine Ansprüche reicht, daher kann ich nicht viel empfehlen). Dann sollte man es ihm natürlich auch geben. Ansonsten sehe ich hier aber vier Splines zwischen den einzelnen Maxima, die zu berechnen sind. Und da würde ich viermal ein 4*4-LGS lösen, so, wie es im erwähnten Workshop beschrieben ist. Dann hast Du vier kubische Funktionen, die Du nur aneinandersetzen musst. |
||||||||||
| 10.03.2017, 16:06 | Fritzelchen | Auf diesen Beitrag antworten » | ||||||||
Nur so wenige? Hab mir das grad mal mit ner App zeichnen lassen. Man erkennt schon die Form, aber es ist dann noch längst nicht perfekt. |
||||||||||
| 10.03.2017, 16:12 | Steffen Bühler | Auf diesen Beitrag antworten » | ||||||||
Meinetwegen auch noch ein paar Zwischenwerte, dann musst Du halt die jeweiligen Steigungen rausmessen. Du sollst hier ja keine perfekte Achterbahn abliefern, sondern zeigen, dass Du das Prinzip der kubischen Splines verstanden hast. Ich hab vor ein paar Jahren in diesem Thread auch mal jemandem bei einer Facharbeit geholfen, die war vom Prinzip her recht vergleichbar. |
||||||||||
| 10.03.2017, 16:37 | Fritzelchen | Auf diesen Beitrag antworten » | ||||||||
Aber ich wollte doch jetzt keine sukzessive Berechnung machen. Deshalb muss ich doch keine Steigungen an den Stützstellen rausfinden!? |
||||||||||
| 10.03.2017, 16:49 | Steffen Bühler | Auf diesen Beitrag antworten » | ||||||||
Das war nur ein Vorschlag von mir. Nein, dann mach es auf die Weise, die Dir am besten passt. Ich will Dir da nicht reinreden. Viel Erfolg Steffen |
||||||||||
| 18.03.2017, 16:01 | Fritzelchen | Auf diesen Beitrag antworten » | ||||||||
Hallo nochmal! Ich habe ein großes Problem, bei der Berechnung eines Splines! Zur Probe, habe ich einen kleinen Spline mit 3 Stützstellen berechnet und habe jetzt auch eine zweimal differenzierbare Funktion. Diesen habe ich mir mit GeoGebra zeichnen lassen und habe aus Spaß einen Spline durch die selben Stützpunkte automatisch mit GeoGebra berechnen lassen. Jetzt habe ich dieses Ergebnis hier: [attach]44113[/attach] Warum bekomme ich nicht den gleichen Spline wie GeoGebra raus? Das Programm benutzt ja die Parameterdarstellung, aber das müsste doch eigentlich keinen Unterschied machen. Das Problem ist, dass mein Spline mehr ausschwingt als der andere Spline. Ich würde also eigentlich eher den Spline von GeoGebra berechnen wollen, aber mit dem "einfachen" Verfahren, dass aus dem Schulbuch ist (damit habe ich auch meinen eigenen Spline berechnet). Der grüne Graph ist mein selbst errechneter Spline und der rote Graph der Spline von GeoGebra. Die Funktionen dazu (h(x) und p(x) sind meine Teilfunktionen): [attach]44114[/attach] Ich brauche dringend Hilfe!!! Also danke für Antworten! |
||||||||||
| 18.03.2017, 17:30 | Steffen Bühler | Auf diesen Beitrag antworten » | ||||||||
Mit Geogebra kenne ich mich nicht aus, aber hier hatte jemand dasselbe Problem. Die beiden Lösungen lassen sich wohl nicht vergleichen, mit der üblichen Methode kommt man nur an Dein Ergebnis. |
||||||||||
| 29.03.2017, 20:46 | Fritzelchen | Auf diesen Beitrag antworten » | ||||||||
Wissen Sie oder jemand anderes, aus welchem Buch diese http://www.mathematik-gymnasium.de/sites...804-5_79_86.pdf Seiten sind? Brauche dringend die Quellenangaben zu dem Buch! Vielen Dank
|
||||||||||
| 29.03.2017, 20:57 | moody_ds | Auf diesen Beitrag antworten » | ||||||||
Guckst du hier. Ohne Gewähr aber aus der URL würde ich die ISBN ableiten files/3-507-85804-5_79_86.pdf 978-3-507-85804-6 Und das Cover hat ja auch so Kästchen. Das wäre allerdings in der Auflage wohl Kapitel 2.4 statt 1.4, aber falls du nicht genau die Ausgabe brauchst sollte das ja passen. lg |
||||||||||
| 29.03.2017, 21:21 | Fritzelchen | Auf diesen Beitrag antworten » | ||||||||
Ich denke das passt! Danke
|
||||||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
