kubischer periodischer Spline

Neue Frage »

mathcat Auf diesen Beitrag antworten »
kubischer periodischer Spline
Hallo Mathefreunde! Wink

Könnt ihr mir bei folgender Aufgabe zufällig helfen traurig
_________________________________________________________
Gesucht ist der kubische periodische Spline s auf [0,1], der die Funktion f(x)=e^x in den Knoten x_j=(j/4) mit j=0,1,...,4 interpoliert.


Man soll von folgendem Ansatz ausgehen:
,
wobei psi_k die normierten B-Splines bzgl. der Knoten (l) bezeichnet.

Man soll die Koeffizienten c_k bestimmern.

Wäre für jeden noch so kleinen hint dankbar.

Liebe Grüße
mathcat
yeti777 Auf diesen Beitrag antworten »
RE: kubischer periodischer Spline
Hallo mathcat!

Um kein Missverständnis aufkommen zu lassen, rekapituliere ich:
Geg.: Stützpunkte im , gewünschte Kurvenform geschlossener (periodischer) B-Spline
Gesucht: Polynomkoeffizienten für das Interpolationspolynom

Ich habe diese Aufgabe vor über 10 Jahren gelöst, und das nicht nur für B-Splines, sondern für NURBS (Non Uniform Rational B-Splines). Ich habe sogar eine Software geschrieben, die es erlaubt, die Stützpunkte mit der Maus einzugeben. Leider ist das schon sehr lange her, sodass ich die Theorie nur noch verschwommen im Kopf habe. Trotzdem bin ich in meinem Archiv fündig geworden. Kopien meiner Theorieblätter (12 Seiten A4) sind noch vorhanden. Aber jetzt sitze ich hier im schönen Appenzellerland und du bist irgendwo in der Welt draussen. So muss ich mich denn fürs erste auf ein paar Stichworte und Literaturhinweise beschränken.

Die Koeffizienten, die du berechnen willst, sind in der Literatur unter dem Namen DE BOOR - Punkte bekannt. Berechnet werden sie mit einem LGS, das eine periodische Bandmatrix aufweist. Die Koeffizienten dieser Matrix und diejenigen des Störungsvektors sind zu kompliziert, um sie hier anzugeben. Ich kann dir aber 2 sehr gute Bücher empfehlen:

(1) "Curves and Surfaces" von Gerald Farin, meine "Bibel" für CAGD (Computer Aided Geometric Design)

(2) Hoschek/Lasser: "Grundlagen der geometrischen Datenverarbeitung", ebenfalls sehr gut und ausführlich

Sowohl im "Farin", als auch im "Hoschek" findest du Alles, was die Cracks der CAGD anzubieten haben, inklusive ein reichhaltiges Literaturverzeichnis von andern guten Büchern, die ich aber nur vom Schnuppern kenne.

Als Anhang sende ich dir noch das Bild eines geschlossenen B-Splines (NURBS mit Standardgewicht 1 in allen Stützpunkten), das ich mit meinem Programm "produziert" habe.

Ich weiss nicht, ob dir diese Info ausreicht. Wenn du weitere Fragen hast, nur zu.

Gruss yeti

PS. Bitte teile mir mit, ob du den Anhang sehen kannst. Aus unerfindlichen Gründen sehe ich nämlich mit meinem Browser (IE7) keine.
kingskid Auf diesen Beitrag antworten »

hi,
danke für deine erklärungen - irgendwie häng ich an der gleichen aufgabe.
warum meinst du sind die stützpunkte aus R^2?
nochmal mit latex:
Gesucht ist der kubische periodische Spline s auf [0,1], der die Funktion in den Knoten (j=0,...,4) interpoliert.
ansatz: und nun soll man die bestimmen.
Als Zusatzbedingungen hat man ja: s''(a) = s''(b), s'(a)=s'(b).
d.h. es müsste gelten:
.

nur hat die matrix des LGS dann folgende form ?
matrix.jpg

das ist doch diese periodische bandmatrix die du angesprochen hast, oder?
und wie kann man diese N's nun konkret berechnen? geht das nur über diese rekursive definition?

viele grüße
Kingskid

ps: ich kann deinen anhang sehen. aber mal noch ne andre frage dazu, wie kann dieser kringel eine funktion sein? oder wie ist das zusammengesetzt? weil so eindeutig sind die punkte da ja nicht zugeordnet, oder?

pps: irgendwie kann ich meine matrix nicht sehen... wie funktioniert das mit dem anhang?
yeti777 Auf diesen Beitrag antworten »

Hallo kingskid!

1. Es muss nicht der sein. Allgemein gilt: . Das ist die Parameterdarstellung einer Kurve im . Den habe ich nur genommen, weil der sich für die graphische Darstellung gut eignet. In der Praxis habe ich vor allem mit gearbeitet (weil 5-achsige Werkzeugmaschine). Für einen periodischen Spline, der ja nichts anderes als eine geschlossene Kurve ist, kann man die explite Funktion nicht brauchen.

Wenn du also einen dimensionalen Spline hast, musst du Splines berechnen. Damit stellt sich die Frage der Parametrisierung. Wie soll der Parameter t gewählt werden? Äquidistant (schlecht), chordal (gut) oder noch raffinierter? Da gibt es eine Abhandlung darüber im Buch von Farin. Je nachdem wie man parametrisiert, ergibt sich eine andere Kurve!

Was das für ein periodischer Spline mit sein soll, begreife ich nicht. Periodisch heisst doch , wenn der Anfangspunkt und der Enpunkt ist, also eine geschlossene Kurve. Missverständnis? Deine Definition von "periodisch"?

Wenn du einen B-Spline willst, musst du den Trägervektor kennen. Wenn die Koeffizienten einmal bekannt sind, Auswertung des Splines mit dem DE BOOR - Algorhitmus. Sagt dir das etwas? Die N's musst du dann gar nicht explizit berechnen. Der DE BOOR - Algorhitmus ist der effizienteste Algorithmus, so eine Art HORNER-Schema. Siehe zB. hier: http://ls7-www.cs.uni-dortmund.de/studen...t/bspline.shtml

Dein Bild kann ich auch nicht sehen, nur ein kleines rotes Kreuz. Frage: Welchen Browser benützest du?

Der von mir anghängte "Kringel" = periodischer Spline ist keine Funktion, sondern die Parameterdarstellung einer geschlossenen Kurve (-> siehe Definition "Kurve"!).

Wie bereits gesagt, kann ich gar keine Anhänge sehen. Ich weiss nicht, woran es liegt. Habe die Einstellungen meines Browsers IE7 überprüft. Anfrage im Off-Topic deponiert, aber keine Antwort.

Gruss yeti
AD Auf diesen Beitrag antworten »

Wollen wir mal die Leute nicht unnötig mit höherdimensionalen Räumen verwirren: Es geht hier nur um einfache kubische Splines . Der Bemerkung

Zitat:
Original von yeti777
Was das für ein periodischer Spline mit sein soll, begreife ich nicht. Periodisch heisst doch , wenn der Anfangspunkt und der Enpunkt ist, also eine geschlossene Kurve. Missverständnis? Deine Definition von "periodisch"?

stimme ich allerdings voll zu - der Begriff periodisch im Zusammenhang mit



ist völlig rätselhaft.
kingskid Auf diesen Beitrag antworten »

Hi yeti, hi Arthur Dent,

hm, also ich hab die aufgabe so verstanden, dass der gesuchte spline aus sein soll. damit das LGS dann lösbar ist, sind ja noch diese beiden Zusatzbedingungen gegeben. In der VL haben wir periodische Splines so definiert:
s''(a)=s''(b), s'(a)=s'(b). mit a anfangs-, b endpunkt, das ist doche igentlich auch deine definition bis auf j=0, oder? *confused*
warum ist das rätselhaft mit f(x) = e^x ?
ah, es ist nicht , sondern ... ist es dann ok?

danke für den link - das is cool... nur leider haben wir weder deboor noch das horner-schema in der VL gemacht, wir haben nur die Def. der B-Splines so aufgeschrieben wie auf der seite.
deshalb ist mir immernoch nicht klar wie ich die koeffizienten berechnen kann.
ohh - sorry, die frage mit dem browser kann ich dir leider nicht beantworten, ich glaub ich versuchs doch besser so:
sollte die matrix dann so aussehen?

=

wobei in der matrix soll in der 1.zeile die 2.Abl. von den N's sein und in der letzten die erste, das hab ich mit latex nicht hinbekommen.
wie kann ich ohne Hornerschema die N's herausbekommen?
Wir sollen das LGS dann mit Matlab lösen, aber dazu brauch ich ja zahlen... traurig traurig

hm und mit der summierung stimmt irgendetwas noch nicht. im skript steht das so:. aber dann würde dass doch keine 5x5-matrix mehr, oder? von wo bis wo muss denn das k laufen?

viele grüße & danke für eure hilfe
kingskid
 
 
AD Auf diesen Beitrag antworten »

Zitat:
Original von kingskid
In der VL haben wir periodische Splines so definiert:
s''(a)=s''(b), s'(a)=s'(b). mit a anfangs-, b endpunkt

Ja, ich hab auch gerade in der Wikipedia gelesen, dass man "periodische Randbedingungen" bei kubischen Splines so auffasst.

In meinen Augen macht das allerdings nur dann Sinn, wenn man das auf den Fall s(a)=s(b) anwendet, und der ist hier nicht gegeben. Was nützt die (vermeintliche) stetige Fortsetzbarkeit der ersten und zweiten Ableitung, wenn nicht mal Stetigkeit der Funktion an sich in diesem Punkt bei der periodischen Fortsetzung gegeben ist!!!

Formal rechnen mit diesen Randbedingungen kann man natürlich, allerdings ist mir der Sinn eines solchen Vorgehens im vorliegenden Fall nach wie vor schleierhaft. verwirrt
Miriam1986 Auf diesen Beitrag antworten »
kubischer periodischer Spline
Hi alle!

Also ich hab ja das selbe Problem, dass ich nicht auf diese Ns komme...
Aber meine Matrix ist eine 7x7 Matrix, d.h. k durchläuft die Werte von
-3 bis 3.
Fragt mich, aber bitte nicht, wie ich da nur draufgekommen bin *grübel*
yeti777 Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
Es geht hier nur um einfache kubische Splines .


@Arthur: Ich möchte noch ganz kurz auf diese Bemerkung eingehen bevor ich mich abmelde. In meinem Verständnis haben einfache kubische Splines segmentweise die Monome als Basis. Dieser Typ Spline hat in der Praxis 2 grosse Nachteile:

1. Die Koeffiziente haben keine "geometrische" Bedeutung, dh. man kann aus ihnen nicht auf die ungefähre Form der Kurve schliessen.
2. Die Veränderung eines Stützpunkts wirkt sich auf den ganzen Spline aus (allerdings exponentiell abnehmend). Man hätte aber gern "Lokalität".

Diese Nachteile vermeiden die B-Splines, weil sie die sog. normalisierten B-Spline- Funktionen, auch Basis-Splines genannt, als Basis haben, Definition siehe Wiki. Die Koeffizienten des B-Splines sind gerade die Punkte des DE BOOR - Polygons, aus dem man auf die Form der Kurve schliessen kann. Der Einfluss eines Stützpunkts erstreckt sich beim kubischen B-Spline nur über 4 benachbarte Punkte und nicht über den ganzen Spline. Das ist wichtig, wenn man Freiformkurven oder Freiformflächen (Autokarosserien, Flugzeugflügel, Wasserhahnen, usw., usw.) entwerfen will.

@alle Anderen: Ich muss jetzt weg. Wenn das Problem aktuell bleibt, werde ich mich noch einmal melden.

@Artur: Hast du vielleicht eine Ahnung, warum ich die Anhänge nicht sehen kann oder kennst du einen der Moderatoren, der diese Frage beantworten könnte? Danke zum voraus.

Gruss yeti
kingskid Auf diesen Beitrag antworten »

Hi Miri,

ich denke du bist da draufgekommen weil die summe ja von -3 bis n-1=4-1=3 läuft(so ham wir das ja für die natürlichen splines aufgeschrieben...), also 7x7-Matrix...
hab mich da glaub ich vertan, der spline müsste dann auch aus sein, dann würde das mit derm dim m+n=3+4=7 auch wieder sinn machen, oder??

dann hoff ich nur, dass uns noch jemand helfen kann die N's herauszubekommen??
wir haben leider kein bsp dazu, und die def. der norm. B-splines ist wirklich sehr unhandlich zum rechnen...*help*
@Arthur Dent: ja ich versteh den sinn der aufgabe sowieso nicht wirklich. aber wie meinst du denn könnte man formal damit rechnen? also die aufgabenstellung ist wirklich so...

viele grüße
AD Auf diesen Beitrag antworten »

Ich meine das so: Wenn du deinen fertig berechneten Spline des Intervalls [0,1] dann periodisch dransetzt, d.h., als Intervalle [1,2], [2,3], [3,4], ..., sowie auch an der negativen Seite [-1,0], [-2,-1], ..., dann hast du an den ganzzahligen Argumenten jeweils einen "Sprung", also eine Unstetigkeit. Und das ist ja nicht gerade der Sinn von Splines. So ausrechnen kann man das aber trotzdem.

Natürlich könnte man die Stetigkeit erzwingen, indem man die Fortsetzungsstücke in y-Richtung so verschiebt, dass Stetigkeit gewährleistet ist. Dann ist aber die fortgesetzte Funktion nicht mehr periodisch. Also auf eins von beiden - Stetigkeit oder Periodizität - muss man bei diesem Beispiel verzichten.
kingskid Auf diesen Beitrag antworten »

achsoo... jetzt versteh ich wie du das meinst... kann das sein, dann wird das wohl bei dieser aufgabe einfach nicht beachtet... sorry, vielleicht dumme frage, aber ist das der sinn von periodischen splines, dass die immer so weitergehen sollten? wie z.B. sinus oder cosinus?

aber ich hab gerade in einem buch noch etwas gefunden zu dem problem wie man die B-Splines nun bestimmen kann... bzw das LGS lösen.
Wir haben hier doch den spezialfall von äquidistanten knoten, wenn ich das richtig verstanden hab, hat die Matrix ja dann immer die gleiche gestalt, oder? also im periodischen fall:



mit der rechten Seite .

die Bedingungen in dem Buch sind nun auch allgemeiner gestellt wie oben, also dass gilt (i) s(x_j) = f(x_j) und
(ii)

---> Wie ändert sich die Matrix, wenn man nur die ersten beiden Ableitungen als Bedingungen stellt?
----> Warum sind die ersten beiden Einträge des Vektors b Null und warum taucht f(x_0) zweimal auf?

Viele grüße
kingskid
mathcat Auf diesen Beitrag antworten »
Gleichungssystem
Hallo smile

Das vorherige Gleichungssystem hat sich logischer angehört (@kingskid). Vielleicht muss man die normierten B-Splines mittels ihrer komplizierten Definition ausrechnen und somit das LGS mit Zahlen auffüllen. Das wird wahrscheinlich eine Mordsrechnerei, aber ... irgendwie weiss ich auch nicht weiter?!?

unglücklich Hat denn niemand hier eine bessere Idee?!?

traurig HILFE .... die Aufgabe ist schrecklich ....

LG mathcat
kingskid Auf diesen Beitrag antworten »

Huhuu,
ich glaub ich weiß wie man auf die matrix kommt...

man hat ja gegeben
1.Abl.
1.Abl
1.Abl

(sorry, Latex nimmt nicht das zeichen ' )

da außerdem ja gelten muss, dass
f''(a)=f''(b) gdw f''(a)-f''(b)=0, müssen also an den stellen, wo es einen Beitrag gibt für a=x_0 ( immer von den drei vorherigen N's, also N_{-3}, N_{-2} und N_{-1} ) bzw das gleiche für b=x_4 in der matrix eben diese einträge stehen.
damit sich die Differenz Null wird (also damit die Ableitungen übereinstimmen) muss man dann halt noch das Vorzeichen ändern...
könnte hinkommen... oder?

viele grüße =)
yeti777 Auf diesen Beitrag antworten »

Hallo zusammen!

Weil mich die Aufgabe interessiert, habe ich ein bisschen nachgegrübelt. Ich kann sogar wieder meine eigenen Notizen lesen Augenzwinkern .

1. Vorgehen beim Lösen der Aufgabe:
- DE BOOR-Punkte berechnen = Koeffizienten (LGS)
- Trägervektor aufsetzen
- Interpolieren mithilfe des DE BOOR-Algorithmus

2. Zur Theorie:
Ich habe mich im Internet umgesehen und die zwei Bücher von Farin und Hoschek konsultiert, die ich weiter oben erwähnte. Der Zugang zu den Koeffizienten wird in diesen Unterlagen durchwegs mit den Bézier-Polynomen bewerkstelligt (konstruktiv). Das hängt damit zusammen, dass die Splines einen Vektorraum bilden. Der Unterschied zwischen den Bézierkurven und den B-Splines besteht lediglich in den unterschiedlichen Basen. Bernsteinpolynome für die Bézierkurven, Basissplines für die B-Splines.
Die Form des LGS im periodischen Fall werde ich in einem nächsten Post hochladen (Kapazitätsbeschränkung 80 kb). Eine Auswertung des B-Splines direkt mit der Definition mit den Basissplines habe ich nicht gefunden. Die rekursive Definition der Basissplines ist für die Auswertung zu umständlich und vor allem zu zeitaufwändig.

3. Mit einem Murks kann man die exp-Funktion approximieren und gleichzeitig einen periodischen Spline konstruieren. Das sieht dann ungefähr so aus: Siehe Anhang!

4. Wieviel an Theorie habt ihr im Rucksack für die Lösung der gestellten Aufgabe? Bézierkurven? DE BOOR-Polygon? Trägervektor? Das sind Begriffe, die im Zusammenhang mit den B-Splines immer wieder auftauchen.

Gruss yeti

Edit1: Falsche Grafik!

Edit2: Die roten Punkte sind die Stützpunkte, die grünen die DE BOOR-Punkte = Koeffizienten. Die rote Kurve stellt den periodischen Spline durch die Stützpunkte dar, die gestrichelten Linien das DE BOOR-Polygon. Man sieht sehr schön die sogenannte "convex hull property", die besagt, dass der B-Spline innerhalb der konvexen Hülle der DE BOOR-Punkte verlaufen muss.
yeti777 Auf diesen Beitrag antworten »

Und hier noch zwei Scans aus dem Buch von Farin, die

a) den Zusammenhang zwischen Stützpunkten und DE BOOR-Punkten zeigen und

b) die Form des LGS im Fall des periodischen B-Splines. Das LGS hat eine positiv-definite Matrix (dominante Hauptdiagonale) und wird am besten mit dem Cholesky-Algorithmus gelöst.

Gruss yeti
mathcat Auf diesen Beitrag antworten »
kubischer periodischer Spline
Hallo yeti,
vielen Dank für deine Nachforschungen und Bemühungen ... Mit Zunge

zu den Begriffen: also DE BOOR ist bei uns in der Vorlesung nie gefallen, genauso wenig wie Bezierkurven.
Aber Trägervektor würd mir was sagen.

Meinst du es könnte auch lösbar sein mit der Idee von kingskid?!? Dass man praktisch von äquidistanten Knoten ausgeht??

Gibt es einen einfacheren Weg als De Boor oder ohne De Boor?!? verwirrt

Lg mathcat
yeti777 Auf diesen Beitrag antworten »
RE: kubischer periodischer Spline
Hallo mathcat!

DE BOOR, Bézier-Kurven: Ich weiss nicht, wie man es ohne macht. Meine Kenntnisse stammen von der Vorlesung 'CAGD' der FernUni Hagen. Und da führte der Weg über die Bézierkurven, die DE BOOR-Punkte und über den DE BOOR-Algoritmus. Dieselbe Technik in den von mir zitierten Büchern. Argumentation: Siehe meinen letzten Beitrag.

Trägervektor: OK, dir bekannt.

Idee von kingskid: Da ich nicht weiss, wie sie zu ihrer Matrix gekommen ist, kann ich es nicht beurteilen. Sicher ist, dass die Besetzung ihrer Matrix anders ist, als die von mir angegebene Form.

Äquidistante Knoten funktionieren auf jeden Fall! Das nennt sich dann uniformer B-Spline. Äquidistante Knoten ergeben die einfachste LGS-Matrix, haben aber die Tendenz zu unerwünschtem Überschwingen. Zum Üben sicher gut.

Einfacherer Weg ohne DE BOOR: Weiss ich nicht verwirrt . Doch schau doch mal hier: http://en.wikipedia.org/wiki/B-spline

Gruss yeti
mathemaduenn Auf diesen Beitrag antworten »

Hallo zusammen,
Wenn ich mal durch einen unqualifizierten Beitrag verwirren darf. Forum Kloppe
Soweit ich mich erinnere war die Interpolationsbedingung bei den Basissplines automatisch durch die Konstruktion erfüllt die c_k aus der Matrix waren die ersten Ableitungen der Splines an den Zwischenpunkten so das das Gleichungssystem dann noch die Gleichheit der 2. Ableitung sicher stellen mußte.
viele grüße
matheamduenn
yeti777 Auf diesen Beitrag antworten »

@mathemaduenn: Ich verstehe deine Ausführungen leider nicht verwirrt .

@mathecat: Ich verstehe jetzt die direkte Lösung. Der Weg ist stachelig, die Lösung eher einfach.

1. Rechne den Basisspline gemäss der rekursiven Definition:



2. Rechne alle Basissplines ... und stelle sie grafisch dar. Siehe Anhang!

3. Man sieht, dass in jedem Stützpunkt jeweils nur 3 Basissplines einen Beitrag leisten. Das ist der Witz des kompakten Trägers der ! Jetzt DE BOOR - Punkte zuordnen , usw., wobei zu beachten ist, dass bei einem periodischen B-Spline gilt , im vorliegenden Fall


4. LGS aufstellen und Multiplikation auf beiden Seiten mit Faktor 6 ergibt:

Die Matrix des LGS ist recht einfach, da wir einen uniformen B-Spline) haben.

5. Das Vektor-LGS zerfällt in 2 skalare LGS, die zB mit dem Algorithmus von CHOLESKY gelöst werden können (die Matrix ist positiv definit).

6. DE BOOR - Punkte in die B-Spline-Definition einsetzen und interpolieren!

Gruss yeti
mathcat Auf diesen Beitrag antworten »
periodischer Spline
Hallo Yeti Wink

Vielen Dank für deine Erklärungen .... das sieht für mich nun einleuchtender aus Freude und ich versteh es.
Danke für deine Hilfe

mathcat
yeti777 Auf diesen Beitrag antworten »
RE: periodischer Spline
Hallo Mathcat Wink

Ich denke, mein Ansatz ist richtig. Aber er kann in deinem speziellen Fall noch vereinfacht werden. Wegen der Vorgabe 'periodisch' bin ich die ganze Zeit von geschlossenen B-Spline-Kurven ausgegangen, also vom Ansatz . Mit dem Murks kannst du den gesuchten B-Spline so ansetzen , dh. . So kommst du auf die Form . Der in meinem letzten Post angegebene Ansatz bleibt gültig. Wegen kannst du aber direkt die Koordinate äquidistant unterteilen. DAS LGS muss dann nur für die Koordinate gelöst werden.

Allerdings bleibt die eingangs diskutierte Frage, wie , eine Funktion, nicht eine Kurve (!), mit einem geschlossenen B-Spline interpoliert werden soll, bestehen. Ich denke, euer Professor wollte euch das Problem von Anfangs- und Endtangente ersparen, das sich bei einem offenen B-Spline stellt. Beim offenen B-Spline hat man nämlich diese zwei freien Randbedingungen.

Gruss yeti
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »