Splines

Hallo !

Ich habe vor zwei bis drei Jahren mal ein damals schon nicht neues Buch oder Heft über Computergrafik in der Hand gehabt, in dem (und das ist das einzige, an was ich mich noch WIRKLICH GUT erinnere, weil ich dazu noch einen Schmierzettel gefunden habe) ein Verfahren beschrieben wurde, welches über einer Reihe von Punkten ein SPLINE (zusammengesetzte Polynome 3.Grades) berechnen konnte, dessen Glättung durch einen Wichtungsfaktor angegeben werden konnte.

Die x-Werte der n Punkte mußten streng monoton steigend sein.
Das Spline setzte sich zusammen aus n-1 kubischen Polynomen.
Eine Glättung mit dem Wichtungsfaktor von 0 resultiert in einer Geraden, die mit dem Least-Squares-Fit einer Geraden (Regressionsgeraden) identisch ist. Für Wichtungen gegen unendlich werden die kubischen Polynome immer mehr zu Geradensegmenten zwischen benachbarten Punkten und das Spline wird zum Polygonzug, welcher durch alle Punkte geht.

Aus den restlichen Notizen, die ich gefunden haben, geht hervor, daß dies beispielhaft in PASCAL programmiert war. Zunächst wurden Koeffizienten für die Polynome bestimmt sowie eine Matrix, dann wurde zum Lösen des wohl in der Matrix versteckten Gleichungssystems eine Prozedur „decomposition“ und schließlich die Prozedur „solution“ aufgerufen. Anschließend wurden die Lösungswerte noch irgendwie verschoben - und fertig.

Für jeden beliebigen x-Wert konnte man nun das zugehörige Intervall (und damit das Polynom) finden und den y-wert berechnen.

Mir fehlt leider die Quellenangabe…

Weiß jemand, wo ich das herhaben könnte oder wo ich etwas Vergleichbares finde ? Ich bin für jeden Tip dankbar !

Jochen

Hi,

Dein Stichwort heist approximierende Splines, es gibt noch interpolierende, die gehen genau durch die Punkte durch. Ganz brutal gesehen macht man genau das, was Du beschreiben hast: Einen Ansatz 3. Grades fuer die x-Intervalle, parametrisiert durch Funktionswert a_i=S(x_i) und Anstieg b_i=S’(x_i) des Splines S an den Intervallenden (4 Werte fuer 4 Koeffizienten, lineares Gleichungssystem). Dann wird die Funktion r*Integral((S’’)^2,Gesamtintervall)+(1-r)*Summe((a_i-y_i)^2, alle Stuetzstellen) ausgerechnet und minimiert. Da es eine quadratische Funktion ist, ergibt sich ein lineares Gleichungssystem in den a_i,b_i als Ableitungen=0. Effektiv wird man natuerlich die Matrixeintraege und rechten Seiten dazu ausrechnen. Loesung dann mit Gauss-Seidel oder was Dir gerade fuer Bandmatrizen unter die Finger kommt.

Ciao Lutz

PS: Ich hab mal mit interpolierenden Splines gespielt:
http://www.mathematik.hu-berlin.de/~llehmann/splinet…

Danke für die Antwort.

Ich suche eine Quellenangabe, wo das beschrieben ist. Mich interessiert insbesondere der Teil mit den Wichtungen (womit man die „Glättung über alles“ angibt. Ich Glaube mich erinnern zu können, daß jeder der n Punkte eine Wichtung bekam.

Ich habe die exe’s mal aufgerufen, da kam aber nur ein BGI-ERROR (use InitGraph)…

Beste Grüße
Jochen

Danke für die Antwort.

Ich suche eine Quellenangabe, wo das beschrieben ist. Mich
interessiert insbesondere der Teil mit den Wichtungen (womit
man die „Glättung über alles“ angibt. Ich Glaube mich erinnern
zu können, daß jeder der n Punkte eine Wichtung bekam.

Kann man machen, wenn man eine Philosophie fuer die Gewichte hat. Jedes Standard-Buch ueber numerische Verfahren sollte auch Splines haben, in der Mathematik ist das Ueberthema die Variationsrechnung (also Sobolev-Raeume, Distributionen und quadratische Funktionale), Suchmaschine ist nicht sehr ergiebig, zu viel Computergraphics, API-Beschreibungen, wenig Theorie, vielleicht noch die Seite
http://www.tinaja.com/cubic01.asp

Ciao Lutz