Stern Mathematik: Interpolation durch kubische Splines
Released by matroid on So. 14. Oktober 2007 12:19:11 [Statistics]
Written by kostja - 13726 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)

Das Interpolationsproblem


Gegeben sei eine Funktion f: \IR \superset [a, b] =: I \to \IR und eine (n+1) elementige Stützstellenmenge T = menge( x_i \in I, 0 <= i <= n ). Wir suchen nun eine "einfache" Funktion p: I -> \IR, welche die


\blue\ll(Interpolationsbedingung)\black \forall 0 <= i <= n: $ p(x_i) = f(x_i) =: f_i
erfüllt.
Natürlich versteht jeder unter "einfach" etwas anderes, so dass ich hier einige Beispiele bringen und dann die Interpolation mit kubischen Splines etwas näher beleuchten möchte.


Navigation:
TODO:
  • Beweis der Fehlerabschätzung



Interpolation durch Polygonzüge

Die einfachste Form einer interpolierenden Funktion ist wohl ein abschnittsweise definierter
\blue\ll(Streckenzug)\black \forall 1<=i<=n: $ I_i := [x_(i-1), x_i] $ $ $ $ $ $ $ $ $ $ $ p_(\|I_i)(x) := f_(i-1) + (f_i - f_(i-1))*(x - x_(i-1))/(x_i - x_(i-1))
Die Qualität der Interpolation im Falle einer Funktion f \in C^2(I) ist gegeben^1 durch den
\blue\ll(Interpolationsfehler)\black max(x \in I, abs(f(x)-p(x))) <= 1/2 * max(1 <= i <= n, (x_i - x_(i-1))^2) * max(\x \in I, abs(f''(\x)))
Nehmen wir mal als Beispiel: f(x) = 1/(1 + 25*x^2) und T = menge( -1+i/5, 0 <= i <= 10 ). Dann sieht der zu diesen Stützstellen definierte Streckenzug so aus Streckenzug Der Nachteil dieser Methode ist, dass der interpolierende Streckenzug nur eine sehr grobe Näherung an die zu interpolierende Funktion f darstellt und in der Regel nichteinmal differenzierbar ist.


Lagrangeinterpolation

Als Lagrangeinterpolation bezeichnet man die Interpolation durch ein Polynom n-ten Grades. Der Vorteil gegenüber den Streckenzügen liegt auf der Hand. Ein Polynom ist eine glatte Funktion. Die Interpolationsbedingung wird mit Hilfe der
\blue\ll(Lagrangepolynome)\black \forall 0 <= i <= n: $ L_i(x) = prod((x-x_j)/(x_i - x_j),array(j=0;j!=i),n)
elegant durch das
\blue\ll(Interpolationspolynom)\black p(x) = sum(f_i L_i(x), i=0, n)
gelöst. Betrachten wir nochmal unser Beispiel: f(x) = 1/(1 + 25*x^2) und T_n = menge( -1+2*i/n, 0 <= i <= n ). Dann sieht das Interpolationspolynom für n \in menge( 5, 10, 15, 20 ) so aus
Lagrangepolynom, n=5Lagrangepolynom, n=10
Lagrangepolynom, n=15Lagrangepolynom, n=20
Den Nachteil dieser Methode kann man hier sehr gut erkennen. Aufgrund der Steifheit von beliebig oft diffbaren Funktionen, werden die Abweichungen an den Rändern beliebig groß, wenn man die Stützstellen Zahl und damit den Polynomgrad erhöht. Den
\blue\ll(Interpolationsfehler)\black abs(f(x)-p(x)) <= max(\x \in I, abs(f^(n+1)(\x)/(n+1)! * prod((\x-x_i),i=0,n))) \frameoff
kann man nach oben abschätzen.\void^2 Man kann hier auch erkennnen, dass prod((\x-x_i),i=0,n) bei Hinzunahme weiterer Stütstellen x_k, mit abs(x_k - \x) > 1, weiter wächst. Noch ein paar Infos und eine ausführliche Rechnung zur Lagrangeinterpolation findet man auch in

needles Artikel: LAGRANGE-Interpolation.



Motivation

Vergessen wir für einen Moment die Mathematik und sinnen etwas darüber nach, welche Hilfsmittel man verwenden könnte, um eine glatte Kurve durch vorgegebene Punkte in einer Ebene zu zeichnen. Ich weiß nicht, auf welche Ideen Ihr kommt, aber Leute aus dem Schiffsbau haben hier die Idee gehabt eine dünne Holzlatte zwischen Querstreben einzuspannen und den Verlauf nachzuziehen. Hier ein kleiner Selbstversuch. Es wurde jedoch statt einer Holzlatte ein Karton verwendet.

KartonsplineKartonspline
KartonsplineKartonspline

Ich habe im auf der Homepage der AG Numerik (Uni Bielefeld) dieses intessante Dokument (Backup) gefunden, das gleich am Anfang sehr ausführlich den Zusammenhang von kubischen Splines mit der Biegeenergie solcher Holzlatten beschreibt.



Ein mathematisches Modell

Wir folgen also den Schiffsbauern, und versuchen die Punkte mit einem Biegestab, nein einem Polynom 3. Grades zwischen den Stützstellen, zu interpolieren. Es ist übrigens auch eine Synthese aus der Interpolation durch Polygonzüge und der Idee Polynome für die Interpolation zu verwenden. Wir machen als den Ansatz und definieren den
\blue\ll(Spline)\black \forall 1 <= i <= n: $ I_i := [x_(i-1), x_i] $ $ $ $ $ $ $ p_(\|I_i)(x) := a_i + b_i * (x-x_(i-1)) + c_i * (x - x_(i-1))^2 + d_i * (x - x_(i-1))^3
Außerdem müssen wir noch weitere Forderungen an den Spline stellen um die 4n unbekannten eindeutig festlegen zu können. Wir wollen, dass die Funktion p(x) \in C^2(I) liegt. Es muss also insbesondere stetig, stetig differenzierbar und ein zweites Mal stetig differenzierbar sein. Aus diesen Bedingungen erhalten wir die folgenden (4n-2) Gleichungen
\blue\ll(S1)\black (stetig) \forall 1 <= i <= n: $ p_i(x_(i-1)) = f_(i-1) und p_i(x_i) = f_i \blue\ll(S2)\black (1 mal stetig diffbar) \forall 1 <= i <= n-1: $ p'_i(x_i) = p'_(i+1)(x_i) \blue\ll(S3)\black (2 mal stetig diffbar) \forall 1 <= i <= n: $ $ p''_i(x_i) = p''_(i+1)(x_i) \frameoff
Da dies auf jeden Fall mindestens 2 Gleichungen zu wenig sind, wollen wir noch die Krümmung am Rand vorgeben:
\blue\ll(S4)\black p''_1(x_0) = e_1 $ und $ p''_n(x_n) = e_2
Dass dies unseren Spline nun eindeutig festlegt, werden wir gleich sehen. Dazu kommen wir nun endlich zum


Aufstellen der Gleichungen

Es wird sich gleich herausstellen, dass folgende Definition uns etwas Schreibaufwand abnimmt
\forall 1 <= i <= n: $ $ h_i = x_i - x_(i-1)
Jetzt setzen wir die Definition des \blue \ref(Spline)s\black in die Bedingungen \blue \ref(S1)\black bis \blue \ref(S4)\black ein und erhalten daraus die Bedingungen für die Koeffizienten a_i, b_i, c_i und d_i. Dies entspricht ganz leichten Rechnungen, die lediglich das Differenzieren von Polynomen erfordern. Da ich zu faul bin es hier auszuführen, überlasse ich diese Aufgabe dem Leser \(Das wollte ich schon immer mal schreiben\). Man erhält auf diese Weise, dann die folgenden Bedingungen für die Koeffizienten
\blue \ref(S1) => \blue\ll(K1)\black \forall 1 <= i <= n: $ f_(i-1) = a_i \blue\ll(K2)\black \forall 1 <= i <= n: $ f_i - f_(i-1) = b_i h_i + c_i h_i^2 + d_i h_i^3 \blue \ref(S2) => \blue\ll(K3)\black \forall 1 <= i <= n-1: $ b_(i+1) = b_i + 2 c_i h_i + 3 d_i h_i^2 \blue \ref(S3) => \blue\ll(K4)\black \forall 1 <= i <= n-1: $ c_(i+1) = c_i + 3 d_i h_i \blue \ref(S4) => \blue\ll(K5)\black c_1 = 1/2 e_1 und c_n + 3 d_n h_n = 1/2 e_n
Definieren wir
c_(n+1) = 1/2 e_n
so folgt aus \blue \ref(K5)\black und \blue \ref(K4)
\blue\ll(d)\black \forall 1 <= i <= n: $ $ d_i = (c_(i+1)-c_i)/(3 h_i)
Weiterhin erhält man aus \blue \ref(K2)\black und \blue \ref(d)
\blue\ll(b)\black \forall 1 <= i <= n: $ $ b_i = (f_i - f_(i-1))/h_i - 1/3 (c_(i+1) + 2 c_i) h_i
Nun haben wir die Koeffizienten a_i, b_i und d_i als Funktionen von den c_i ausgedrückt. Gelingt es uns nun letztere zu bestimmen, so wären wir fertig. Dazu nehmen wir die noch nicht verwendete Gleichung \blue \ref(K3)\black und setzen hier \blue \ref(b)\black und \blue \ref(d)\black ein: \forall 1 <= i <= n-1 b_(i+1) = b_i + 2 c_i h_i + 3 d_i h_i^2 <=> (f_(i+1) - f_i)/h_(i+1) - 1/3 (c_(i+2) + 2 c_(i+1)) h_(i+1) = (f_i - f_(i-1))/h_i - 1/3 (c_(i+1) + 2 c_i) h_i + 2 c_i h_i + 3 (c_(i+1)-c_i)/(3 h_i) h_i^2 <=> 3 (f_(i+1) - f_i)/h_(i+1) - 3 (f_i - f_(i-1))/h_i = h_(i+1) c_(i+2) + 2 (h_(i+1) + h_i) c_(i+1) + h_i c_i Nun, an dieser Stelle haben wir schon so gut wie gewonnen. Die letzte Formel beschreibt ein lineares Gleichungssystem, welches wir mit den folgenden Definition wesentlich übersichtlicher darstellen können.
\forall 1 <= i <= n-1: $ $ \D_i = 3 (f_(i+1) - f_i)/h_(i+1) - 3 (f_i - f_(i-1))/h_i $ $ $ $ $ $ $ $ $ $ $ $ D_1 = \D_1 - h_1 c_1 $ $ $ $ $ $ $ $ $ $ $ $ D_(n-1) = \D_(n-1) - h_n c_(n+1) \forall 1 <= i <= n-1: $ $ H_i = 2 (h_(i+1) + h_i)
Man beachte, dass c_1 und c_(n+1) schon bekannt sind! (h_1, H_1, h_2, 0, \cdots, 0; 0, h_2, H_2, h_3, \cdots, 0; \vdots, \ddots, \ddots, \ddots, \cdots, 0; 0, 0, \cdots, h_(n-1), H_(n-1), h_n) * (c_1; \vdots; c_(n+1)) = (\D_1; \vdots; \D_(n-1)) <=> (H_1, h_2, 0, \cdots, 0; h_2, H_2, h_3, 0, \cdots; \ddots, \ddots, \ddots, 0, \cdots; 0, \cdots, 0, h_(n-1), H_(n-1)) * (c_2; \vdots; c_n) = (D_1; \D_2; \vdots; \D_(n-2); D_(n-1)) Woraus nun auch schon die


Existenz und Eindeutigkeit der Lösung

folgt. Die vorliegende Matrix A = (a_ij) = \d_(i-1)j h_i + \d_ij H_i + \d_i(j-1) h_j ist nämlich symmetrisch und (\blue strikt diagonal dominant )__ \black. Das bedeutet
\forall 1 <= i <= n-2: $ sum(abs(a_ij),array(j=1; j != i),n-1) < abs(a_ii),
denn es ist ja \forall 1 <= i <= n-2: $ h_i + h_(i+1) < 2 ( h_i + h_(i+1) ). Das nächste kleine Lemma zeigt, dass wir nun fertig sind.
\blue \big Lemma Sei A = (a_ij) eine symmetrische und strikt diagonal dominante n \times n Matrix, dann ist A regulär.
Ich setze an dieser Stelle die Kenntniss des Gaußalgorithmus voraus, mit dem wir nun den \blue \big Beweis \black \normal führen werden.

Wer's kürzer mag und den Satz von den Gerschgorin-Kreisen kennt, dem sei gesagt, dass aus der strikten Diagonaldominanz folgt, dass die Eigenwerte von Null weg beschränkt sind und der Kern somit trivial sein muss.

Der Gaußalgorithmus ohne Pivotierung erzeugt im (k+1)-ten Schritt die Matrix
\blue \ll(Gauß)\black \forall k < i <= n: $ a_ij^(k+1) = a_ij^(k) - (a_ik^(k))/(a_kk^(k))*a_kj^(k)
Betrachten wir nun "unsere" Matrix. Wegen der strikten Diagonaldominanz gilt a_11 > sum(abs(a_1j),j=2,n) >= 0, also a_11 > 0. Somit ist der erste Gaußschritt wohldefiniert. Und wir erhalten eine neue Matrix mit den Einträgen: \forall 1 <= j <= n: a_1j^(2) = a_1j^(1) \(Klar an der k-ten Zeile und drüber tut der Algo nichts\) \forall 1 < i <= n: a_(i1)^(2) = a_i1^(1) - (a_i1^(1))/(a_11^(1))*a_11^(1) = 0 \forall 1 < i, j <= n: a_ij^(2) = a_ij^(1) - (a_i1^(1))/(a_11^(1))*a_1j^(1) = a_ij^(1) - (a_1j^(1))/(a_11^(1))*a_i1^(1) $ $ $ $ $ $ $ $ $ $ $ bigop(=,,,Symmetrie!) a_ji^(1) - (a_j1^(1))/(a_11^(1))*a_1i^(1) = a_ji^(2) Das bedeutet die Untermatrix A^~^(2) = (a_ij^(2))_array(2 <= i <= n; 2 <= j <= n), auf die der nächste Gaußschritt angewendet wird, ist wieder symmetrisch! Sollte sich herrausstellen, dass sie auch noch strikt diagonal dominant ist, dann haben wir damit induktiv gezeigt, dass der Gaußalgo durchläuft, bis nur noch eine obere Dreickesmatrix übrigbleibt, deren letzter Eintrag wegen der strikten__ Diagonaldominanz wieder ungleich Null ist. Betrachten wir doch mal für i > 1 abs(a_ii^(2)) = abs(a_ii^(1) - (a_i1^(1))/(a_11^(1))*a_1i^(1)) >= abs(a_ii^(1)) - abs((a_i1^(1))/(a_11^(1))*a_1i^(1)) > sum(abs(a_ij^(1)),array(j=1; j != i),n) - abs((a_i1^(1))/(a_11^(1))*a_1i^(1)) \bigop(>,,für a_11^(1),diag. D.) sum(abs(a_ij^(1)),array(j=2; j != i),n) - abs((a_i1^(1))/(a_11^(1))*a_1i^(1)) + sum(abs(a_1j^(1)),j=2,n)/abs(a_11^(1)) abs(a_1i^(1)) = sum(abs(a_ij^(1)),array(j=2; j != i),n) - abs((a_i1^(1))/(a_11^(1))*a_1i^(1)) + abs(a_1i^(1))/abs(a_11^(1)) sum(abs(a_1j^(1)),array(j=2; j!=i),n) + abs(a_1i^(1))/abs(a_11^(1))*abs(a_1i^(1)) \bigop(=,,,Symmetrie) sum(abs(a_ij^(1)),array(j=2; j != i),n) + sum(abs(a_1i^(1)/a_11^(1)*a_1j^(1)),array(j=2; j!=i),n) >= sum(abs(a_ij^(1) - a_1i^(1)/a_11^(1)*a_1j^(1)),array(j=2; j!=i),n) = sum(abs(a_ij^(2)),array(j=2; j!=i),n) $ $ $ $ $ $ \;\-\)


Simple Beispiele

Wie sieht der natürliche kubische Spline zu einem Polynom dritten Grades aus?
\blue \ll(1) \black f: [0, 1] \to \IR, x \mapsto x^3 $ $ $ $ $ $ $ $ T = menge(i/2, 0 <= i <= 2) $ $ $ $ $ $ $ $ e_1 = 0 $ e_2 = 0
x_0 = 0 $ x_1 = 1/2 $ x_2 = 1 f_0 = 0 $ f_1 = 1/8 $ f_2 = 1 \forall 1 <= i <= 2: $ h_i = 1/2 c_1 = 0 $ c_3 = 0 \D_1 = 9/2 = D_1 $ $ c_2 = 9/4 b_1 = -1/8 $ $ d_1 = 3/2 b_2 = 1 $ $ d_2 = 3/2
\void => \void p_1(x) = 1/8 - 1/8 x + 3/2 x^3 p_2(x) = 1 + (x-1/2) - 9/4 (x-1/2)^2 - 3/2 (x-1/2)^3
Was passiert, wenn wir die tatsächliche Krümmung am Rand vorgeben?
\blue \ll(2) \black f: [0, 1] \to \IR, x \mapsto x^3 $ $ $ $ $ $ $ $ T = menge(i/2, 0 <= i <= 2) $ $ $ $ $ $ $ $ e_1 = 0 $ e_2 = 6
x_0 = 0 $ x_1 = 1/2 $ x_2 = 1 f_0 = 0 $ f_1 = 1/8 $ f_2 = 1 \forall 1 <= i <= 2: $ h_i = 1/2 c_1 = 0 $ c_3 = 0 \D_1 = 9/2 $$ D_1 = D_(2-1) = 3/2 $ $ c_2 = 3/4 b_1 = 0 $ $ d_1 = 1 b_2 = 3/4 $ $ d_2 = 1
\void => \void p_1(x) = x^3 p_2(x) = 1/8 + 3/4 (x-1/2) + 3/2 (x-1/2)^2 + (x-1/2)^3 = (x-1/2+1/2)^3 = x^3
Allgemein kann man sogar behaupten, dass ein Polynom bis zum dritten Grad, bei Vorgabe der tatsächlichen Krümmung am Rand sein eigener Spline ist. Diese Behauptung folgt nämlich unmittelbar aus der


Fehlerabschätzung

\blue \ll(Fehlerabschätzung) \normal Sei f \in C^4([a, b]) und s ein kubischer Spline mit den Eigenschaften \blue \ll(1) \black s''(a) = f''(a) und \blue \ll(2) \black s''(b) = f''(b), dann gilt $ $ $ $ max(a<=x<=b, abs(f(x)-s(x))) <= 1/2 \D^4 max(a<=x<=b, abs(f^(4)(x))).
Dabei bezeichnet \D = max(1=i<=n, abs(x_i-x_(i-1))).
\big \blue Beweis: \black \normal FIX ME!


Eine Implementierung

Jetzt haben wir zwar eine schöne Theorie, aber zugegebener Maßen, sind die dabei anfallenden Rechnungen nichts, was man gerne von Hand erledigt. Um noch ein paar Beispiele zu betrachten und diese nicht selbst rechnen zu müssen, möchte ich noch eine mögliche Implementierung des Algorithmus vorstellen. Da man mit MATLAB/Octave um das Problem herum kommt, zuerst eine Bibliothek für Matrizen zu schreiben, habe ich meine Wahl darauf gelegt. Die folgenden Code Abschnitte sind für Octave geschrieben, sollten aber ohne weiteres entweder direkt mit Matlab laufen, oder mit geringem Aufwand auf Matlab portierbar sein. Zunächst den Algorithmus, um den es hier ja gehen soll.

\sourceon Matlab function y = Spline(x, f, e1, en, xi) % x, f, xi: Zeilenvektoren. x paarweise verschieden und aufsteigend sortiert. % % Werte den kubischen Spline zu den Stützstellen (x,f) % an den Stellen xi aus. % Lege s''(x(1)) = e1 und s''(x(n)) = en fest. [tmp, n] = size(x); n = n-1; % Wir haben nun n+1 Stützstellen!!! % Gitterweiten for i=1:n h(i) = x(i+1)-x(i); end % Unsere Polynom haben die Gestalt: % p(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 % Berücksichtige die Krümmung am Rand a_2(1) = 1/2*e1; a_2(n+1) = 1/2*en; % Erzeuge das Gleichungssystem: Ax = b % % Berechne den Lösungsvektor b for i=1:n-1 b(i) = 3 * ( ( f(i+2) - f(i+1) ) / h(i+1) - ( f(i+1) - f(i) ) / h(i) ); end b(1) = b(1) - h(1) * a_2(1); b(n-1) = b(n-1) - h(n) * a_2(n+1); % % Erzeuge das Gleichungssystem A for i=1:n-1 H(i) = 2*(h(i) + h(i+1)); end A = diag(H) + diag(h(2:n-1), 1) + diag(h(2:n-1), -1); % Löse das Gleichungssystem a_2(2:n) = Gauss(A, b', true); % Berechne die übrigen Koeffizienten for i = 1:n a_1(i) = ( f(i+1) - f(i) ) / h(i) - h(i)/3 * ( a_2(i+1) + 2*a_2(i) ); end for i = 1:n a_3(i) = ( a_2(i+1) - a_2(i) ) / ( 3 * h(i) ); end % Werte nun die Polynome an den Stellen xi aus. [tmp, m] = size(xi); for k = 1:m j(k) = 1; % Suche i mit x(i-1) <= xi <= x(i) for i = 1:n+1 % Das sollte man hier besser machen! O(n) im worst case if ( xi(k) < x(i) ) j(k) = i-1; break; end j(k)=n; end % Auswertung mit Horner-Schema X = (xi(k) - x(j(k))); y(k) = f(j(k)) + X*( a_1(j(k)) + X*( a_2(j(k)) + X*a_3(j(k)) ) ); end return \sourceoff Spline.m

Hier der verwendete Gaussalgo:

\sourceon Matlab function x = Gauss(A, b, pivot) % Gaussverfahren löst _reguläres_ Gl.System % Es wird nicht auf Lösbarkeit geprüft!!! % % pivot: Schalter für Pivotierung [n, t] = size(b); x = zeros(n, 1); A = [A, b]; % Ich denke das ist selbsterklärend. Gewöhnlicher Gaussalgo... for k = 1 : n-1 if (pivot) [C, l] = max(abs(A(k:n,k))); t = A(k+l-1,:); A(k+l-1,:) = A(k,:); A(k,:) = t; end for j = k+1 : n if ( A(k,k) == 0 ) disp('Lösung nicht möglich') x = inf; return end A(j,:) = A(j,:) - A(j,k)/A(k,k) * A(k,:); end end x(n) = A(n,n+1)/A(n,n); for k = n-1 : -1 : 1 x(k) = (A(k,n+1) - A(k,k+1:n)*x(k+1:n))/A(k,k); end return \sourceoff Gauss.m

Als nächstes schreiben wir noch ein paar kleine Funktionen, die uns das Leben etwas erleichtern sollen:

\sourceon Matlab function [x, f] = Func(a, b, n, F) % a < b reell, n natürliche Zahl, F: Name einer reellwertigen Funktion % % Berechnet die Stützstellen der Funktion F zu der Zerlegung % x(i) = i*(b-a)/n F = str2func(F); x = zeros(1, n+1); f = zeros(1, n+1); h = (b-a)/n; for i = 0:n x(i+1) = a + h*i; f(i+1) = F( x(i+1) ); end return \sourceoff Func.m


Noch ein paar Beispiele

\blue \ll(1) \black I = [ -1\, 1] $ $ f(x) = 1/(1 + 25*x^2) $ $ T_n = menge( i*2/n, 0<=i<=n )
\sourceon Matlab function y = Func_F(x) % Eine Testfunktion: y = 1 / ( 1 + 25 * x * x ); y = 1 / ( 1 + 25 * x * x ); return \sourceoff Func_F.m

Nun ein Testprogramm

\sourceon Matlab function main() % Testet Spline.m g = 80; % Gitterweite % Plot der Testfunktion [X, Y] = Func(-1, 1, g, 'Func_F'); for n = 2:2:12 % Plotte den Spline mit n Stützstellen % Berechne die Stützstellen zur Testfunktion [x, f] = Func(-1, 1, n, 'Func_F'); % Plotte den Spline F = Spline(x, f, 0, 0, X); % Plot Befehle plot(x, f, 'x ;Stuetzwerte;'); hold on; plot(X, F, '+ ;Spline;'); plot(X, Y, ';Funktion;'); hold off; title(['Spline Interpolation: n = ', int2str(n)]); xlabel('x'); ylabel('f(x)'); axis([-1, 1, -0.5, 1.1]); pause; % Taste drücken end return \sourceoff main.m
Spline, n=2Spline, n=4
Spline, n=6Spline, n=8
Spline, n=10Spline, n=12


Ausblick

Mann kann Splines natürlich auch dazu verwenden um Linien im Mehrdimensionalen zu zeichnen. Hat man eine Parametrisierung für Messpunkte, so wendet man einfach in jeder komponente die Interpolation durch und trägt die Splinefunktionen übereinander auf. Hier ist ein ganz simples Beispiel:

\sourceon Matlab function dim2spline() T=0.1:1/2:2*pi; X = log(T).*cos(T); Y = log(T).*sin(T); t=0.1:1/50:2*pi; x = Spline(T, X, 0, 0, t); y = Spline(T, Y, 0, 0, t); plot(X,Y, ';Stuetzstellen;+r'); hold on; plot(x,y, ';kubisdcher Spline;'); hold off; title('2 dimensionaler Spline'); xlabel('x(t)'); ylabel('y(t)'); \sourceoff dim2spline.m 2 dimensionaler Spline

In diesem Zusammenhang sollte man sich aber vor allem mal die sog. NURBS - eine Verallgemeinerung dieses Konzepts - anschauen, da diese in der Praxis häufiger vorkommen und auch Flächen modelieren können.



Abschluss

Dem aufmerksamen Leser ist sicherlich nicht entgangen, dass der Beweis der Fehlerabschätzung fehlt. Nun, ich muss ehrlich zugeben, ich hatte keine Lust, diesen einzutragen, aber fühlt Euch herzlich eingeladen dies zu tun. Dazu einfach auf Bearbeiten im entsprechenden Abschnitt klicken. Ich und viele andere Leser auf dem MP würden sich sicher darüber freuen. ;-) Ich verbleibe nun mit schönen Grüßen und wünsche Euch einen guten Start ins neue Semester! Euer Konstantin



  1. 1 cf. Prof. Rannacher - Vorlesungsskript: Numerik 0 Seite 41
    Aufgerufen am: 14.02.2007 - 16:01 Uhr
  2. 2 cf. Prof. Rannacher - Vorlesungsskript: Numerik 0 Seite 29
    Aufgerufen am: 14.02.2007 - 16:08 Uhr

\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: Angewandte Mathematik :: Numerik :: Interpolation :
Interpolation durch kubische Splines [von kostja]  
Wir suchen nun eine ''einfache'' Funktion p: I -> \IR, welche die Interpolationsbedingung erfüllt. Natürlich versteht jeder unter "einfach" etwas anderes, so dass ich hier einige Beispiele bringen und dann die Interpolation mit kubischen Splines etwas näher beleuchten möchte.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 13726
 
Aufrufstatistik des Artikels
Insgesamt 2574 externe Seitenaufrufe zwischen 2012.01 und 2022.01 [Anzeigen]
DomainAnzahlProz
https://matheplanet.com40.2%0.2 %
https://www.startpage.com20.1%0.1 %
https://google.com170.7%0.7 %
https://duckduckgo.com50.2%0.2 %
http://google.de198877.2%77.2 %
https://google.de1465.7%5.7 %
http://google.it1174.5%4.5 %
http://google.fr1144.4%4.4 %
http://google.ro321.2%1.2 %
http://google.ru271%1 %
https://google.lu150.6%0.6 %
http://kostja.selfip.org60.2%0.2 %
https://www.bing.com70.3%0.3 %
http://images.google.de40.2%0.2 %
http://google.se40.2%0.2 %
http://www.bing.com401.6%1.6 %
http://r.duckduckgo.com30.1%0.1 %
https://www.ecosia.org30.1%0.1 %
http://google.nl20.1%0.1 %
http://www.ecosia.org50.2%0.2 %
http://www1.delta-search.com10%0 %
http://just-like.net10%0 %
http://suche.web.de40.2%0.2 %
http://search.tb.ask.com40.2%0.2 %
http://metager.de10%0 %
http://ecosia.org50.2%0.2 %
https://search.becovi.com10%0 %
http://de.search.yahoo.com60.2%0.2 %
https://search.gexsi.com10%0 %
http://search.mywebsearch.com20.1%0.1 %
http://suche.t-online.de20.1%0.1 %
https://suche.web.de10%0 %
http://www.fireball.de10%0 %
https://www.qwant.com10%0 %
http://search.conduit.com10%0 %
http://cn.bing.com10%0 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 6 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2022.01.19 15:24viewtopic.php?topic=105692
2022.01.17 11:51https://www.startpage.com/
2022.01.04-2022.01.16 (3x)https://google.com/
2022.01.16 09:10viewtopic.php?topic=162197

Häufige Aufrufer in früheren Monaten
Insgesamt 2477 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2013-2018 (215x)http://google.de/url?sa=t&rct=j&q=
2014-2015 (193x)http://google.de/url?sa=t&rct=j&q=kubische spline interpolation beispiel
201201-01 (154x)http://google.de/url?sa=t&source=web&cd=1&ved=0CCMQFjAA
201501-02 (130x)http://google.de/url?sa=t&rct=j&q=kubische spline interpolation
201205-05 (121x)http://google.de/url?sa=t&rct=j&q=spline matroid
2020-2021 (119x)https://google.de/
201301-01 (117x)http://google.de/url?sa=t&rct=j&q=spline matlab matheraum
201202-02 (117x)http://google.it/imgres?q=streckenzug
201210-11 (96x)http://google.de/url?sa=t&rct=j&q=spline interpolation octave
201212-12 (94x)http://google.de/url?sa=t&rct=j&q=splines übungsaufgabe
201207-07 (85x)http://google.de/url?sa=t&rct=j&q=octave kumischer spline
201406-06 (82x)http://google.de/url?sa=t&source=web&cd=3&ved=0CCAQFjAC
201302-02 (71x)http://google.fr/url?sa=t&rct=j&q=kubische interpolationspolynom
201206-06 (70x)http://google.de/url?sa=t&rct=j&q=natürlicher kubischer spline beispiel
201412-12 (60x)http://google.de/url?sa=t&source=web&cd=6&ved=0CCcQFjAF
201203-03 (58x)http://google.de/url?sa=t&source=web&cd=1&ved=0CCwQFjAA
201407-07 (57x)http://google.de/url?sa=t&rct=j&q=mathe spline interpolation
201305-05 (54x)http://google.de/url?sa=t&rct=j&q=zahlenbeispiel quadratischer spline
201204-04 (46x)http://google.de/url?sa=t&rct=j&q=streckenzuginterpolation
201401-01 (43x)http://google.fr/url?sa=t&rct=j&q=
201306-06 (41x)http://google.de/url?sa=t&rct=j&q=octave spline beispiele
201209-09 (41x)http://google.de/url?sa=t&rct=j&q=spline kubisch beispiel
201307-07 (34x)http://google.de/url?sa=t&rct=j&q=splines kubisch
201403-03 (33x)http://google.de/url?sa=t&rct=j&q=natürliche splines code
201505-05 (32x)http://google.ro/url?sa=t&rct=j&q=
201304-04 (32x)http://google.de/url?sa=t&rct=j&q=kubischen spline differenzieren
201506-06 (30x)http://google.de/url?sa=t&rct=j&q=algorithmus für kubische spline-interpol...
201311-11 (29x)http://google.de/url?sa=t&rct=j&q=interpolierende kubische spline berechnen
201410-10 (27x)http://google.ru/url?sa=t&rct=j&q=
201409-09 (27x)http://google.de/url?sa=t&rct=j&q=mathroids b-spline interpolate
201408-08 (22x)http://google.de/url?sa=t&rct=j&q=spline kubisch rechnung
201303-03 (19x)http://google.de/url?sa=t&rct=j&q=kubische spline berechnen
201208-08 (18x)http://google.de/url?sa=t&rct=j&q=matheplanet spline
201308-08 (15x)http://google.de/url?sa=t&rct=j&q=spline interpolation matroids matheplanet
202005-05 (15x)https://google.lu/
202012-12 (14x)https://google.de/url?sa=t
2020-2021 (13x)https://google.de
2020-2021 (13x)https://google.com/
201309-09 (13x)http://google.de/url?sa=t&rct=j&q=kubische spline interpolation online
2012-2013 (6x)http://kostja.selfip.org/science-math.htm
202104-11 (5x)https://www.bing.com/
201604-09 (4x)http://images.google.de/url?sa=t&rct=j&q=
202102-09 (4x)https://duckduckgo.com/
201507-07 (4x)http://google.se/url?sa=t&rct=j&q=
201302-02 (4x)http://www.bing.com/search?q=kubischer Spline beispiel rechnung&qs=n&form=QBR...

[Top of page]

"Stern Mathematik: Interpolation durch kubische Splines" | 4 Comments
The authors of the comments are responsible for the content.

Re: Interpolation durch kubische Splines
von: Meren-Adven am: So. 14. Oktober 2007 13:41:06
\(\begingroup\)Hi Konstantin, gefällt mir gut, der Artikel. Zwei Vorschläge: 1) Die Lagrange-Polynome kriegst Du doch sicher noch in einem Satz motiviert, oder ;) 2) Schön, diese Motivation der Splines, warum hast du aber nicht gleich noch dazugeschrieben, dass daher das Wort "Spline" kommt? Vermutlich steht das im verlinkten Artikel, aber da will ich jetzt nicht reinschauen ;) Bin mal gespannt, ob sich ein Fehlerabschätzungs-Beweiser findet :D Kommt irgendwann noch was zu B-Splines? Gruß Hannes\(\endgroup\)
 

Re: Interpolation durch kubische Splines
von: Ueli am: Mo. 29. Oktober 2007 14:54:57
\(\begingroup\)Hallo Konstantin, Dein Artikel hat mir sehr gefallen. Ich bin auch oft mit Interpolation konfrontiert. Leider passen Polynome bei mir nicht gut (auch Splines). Ich habe Funktionen die bei kleinen Werten sehr gross werden und bei grossen Werten verschwinden, ähnlich wie f=1/x. Ein Ansatz war daher zum Beispiel die reziproke Funktion 1/f zu interpolieren und erhalte somit 1/p(x). Manchmal ist es aber auch besser durch eine physikalische Überlegung die Funktion mehr oder weniger zu erraten und noch etwas an den Konstanten zu schrauben, bis der Fehler minimal wird. Nun seh ich aber in deinem Artikel den 2-dimensionalen Spline und werde einmal probieren ob es damit besser geht... Übrigens noch ein Buch-Tip: W. Dahmen, A. Reusken: Numerik für Ingenieure und Naturwissenschaftler Springer-Verlag GmbH ISBN: 3540255443 EAN: 9783540255444 Gruss Ueli\(\endgroup\)
 

Re: Interpolation durch kubische Splines
von: kostja am: Di. 30. Oktober 2007 16:09:13
\(\begingroup\)Hallo Uelli, vielen Dank für Deinen Beitrag. Die Idee 1/f zu interpolieren klingt irgendwie interessant. 😄 Ich glaube ich mache mal ein paar Tests, wenn ich mal wieder Zeit finden sollte. Das "Funktion raten und an den Parametern schrauben" nennt sich auch fitten, und ist zunächst eine völlig andere Art der Aufgabenstellung. Hier erwartet man zum Beispiel nicht, dass alle Punkte auf der Kurve liegen. So weit ich weiß, gibt es dafür eigene Agorithmen und Lösungsansätze. Bitte sag mir, ob der 2d-Spline Ansatz, irgendetwas vernünftiges liefert. MfG Konstantin\(\endgroup\)
 

Re: Interpolation durch kubische Splines
von: MichaH am: Do. 18. Dezember 2008 03:40:03
\(\begingroup\)*den Urschrei ausstoß* Man man man ... erstmal mega viel lob an den autor ... sry bin gerade zu faul den namen nachzugucken aber respekt, den du dir verdient hast, von mir :) Ich hab damit gerade mal ne Aufgabe gelöst und es sogar alles verstanden, SUPER. Aber eine kleine Sache die mich seit ca. 2 Stunden beschäftige :D es gibt einen kleinen fehler was mir voll net wahr war weil das noch keiner gesehen hat ... Aus \ H_i = 2(h_(i+1) - h_i) muss natürlich \H_i = 2(h_(i+1) + h_i) werden. Dann stimmen auch die Ergebnisse ... mit denen ich mich jetzt so lange rumgequält hab :D Aber wie gesagt mega vielen dank und respekt ... sowas kann ja immer mal passieren ... wenn ich es schaffe (die berechtigung hab) werde ich den fehler auch gleich mal korrigieren ... aber erstmal eine rachen ^^ lg micha \(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]