2.1. Kubische Spline-Interpolation

Das menschliche Auge nimmt keine Unstetigkeiten ("Spitzen") in der Krümmung, d.h. der zweiten Ableitung, wahr. Also werden zweimal stetig differenzierbare, kubische Splines als "glatt" wahrgenommen.
Þ s_i soll ein Polynom dritten Grades sein.
O.B.d.A. gilt x₀ < x₁ < x₂ < ... < x_n-1 < x_n.

Ansatz der Interpolation durch kubische Splines:

Im Intervall [xi,xi+1] mit i = 0, 1, ..., n - 1 soll si(x) = ai + bi(x - xi) + ci 2 (x - xi)2 + di 6 (x - xi)3 gelten.

Der Spline s wird also durch n Splines s_i (i = 0, 1, ..., n - 1) mit je vier Koeffizienten (a_i, b_i, c_i, d_i) charakterisiert, d.h. es müssen 4n Koeffizienten bestimmt werden.
Zusätzlich zu der Interpolationsbedingung s(x_i) = f_i werden noch folgende Verheftungsbedingungen gefordert:

	si(xi+1)	= si+1(xi+1)
	si'(xi+1)	= si+1'(xi+1)		i = 0, 1, ..., n - 2
	si''(xi+1)	= si+1''(xi+1)

Aus der Interpolationsbedingung und den Verheftungsbedingungen ergeben sich (n + 1) + 3(n - 1) = 4n - 2 Gleichungen. Also werden zwei zusätzliche Bedingungen gebraucht.
Es können folgende Fälle vorliegen:

periodische Randbedingungen:
    s'(x₀) = s'(x_n)
    s''(x₀) = s''(x_n)

Wegen sÎC²[a, b] folgt aus Gleichung (2.1):

si'(x) = bi + ci(x - xi) +	di	(x - xi)2       (2.2)
	2

und s_i''(x) = c_i + d_i(x - x_i) mit i = 0, 1, ..., n - 1       (2.3)
Für x = x_i folgt nun aus (2.1), (2.2) und (2.3):

si(xi) = ai + bi(xi - xi) +	ci	(xi - xi)2 +	di	(xi - xi)3 = ai
	2		6

Þ a_i = f_i       (2.4)

si'(xi) = bi + ci(xi - xi) +	di	(xi - xi)2
	2

Þ s_i'(x_i) = b_i       (2.5)
s_i''(x_i) = c_i + d_i(x_i - x_i)
Þ s_i''(x_i) = c_i       (2.6)

In den nun folgenden Betrachtungen werden die Abstände zwischen den Stützstellen als äquidistant angenommen, damit die Umformungen kompakter dargestellt werden können.
Also existiert eine konstante Schrittweite h:
h := x_i+1 - x_i
Für x = x_i+1 folgt nun aus (2.1), (2.2) und (2.3):

si(xi+1) = ai + bi(xi+1 - xi) +	ci	(xi+1 - xi)2 +	di	(xi+1 - xi)3
	2		6

Þ si(xi+1) = ai + bih +	ci	h2 +	di	h3       (2.7)
	2		6

si'(xi+1) = bi + ci(xi+1 - xi) +	di	(xi+1 - xi)2
	2

Þ si'(xi+1) = bi + cih +	di	h2       (2.8)
	2

s_i''(x_i+1) = c_i+1 + d_i(x_i - x_i)
Þ s_i''(x_i+1) = c_i + d_ih       (2.9)

Nun wird versucht die Koeffizienten a_i, b_i und d_i mit i = 0, 1, ..., n - 1 als Funktion von c₀, c₁, ..., c_n-1 und c_n darzustellen. Dabei ist es unwichtig, dass c_n in keinem Spline s_i als Koeffizient verwendet wird, wenn c_n trotzdem eindeutig bestimmbar ist.
Alle a_i sind durch Gleichung (2.4) eindeutig als Funktion von c_k (k = 0, 1, ..., n) bestimmt. So dass nur noch b_i und d_i als Funktion von c_k dargestellt werden müssen.

Aus s_i''(x_i+1) = s_i+1''(x_i+1) mit i = 0, 1, ..., n - 1 und den Gleichungen (2.6) und (2.9) folgt:
c_i + d_ih = c_i+1

Þ di =	ci+1 - ci	(2.10)
	h

Aus s_i(x_i+1) = s_i+1(x_i+1) und den Gleichungen (2.4) und (2.7) folgt:

ai + bih +	ci	h2 +	di	h3 = ai+1
	2		6
Þ fi + bih +	ci	h2 +	di	h3 = fi+1
	2		6

Unter Verwendung von Gleichung (2.10) folgt daraus:

bih = (fi+1 - fi) -	ci	h2 -	ci+1 - ci	h2
	2		6

bi =	(fi+1 - fi)	-	h(ci+1 + 2ci)	(2.11)
	h		6

Jetzt müssen noch die c_k mit k = 0, 1, ..., n bestimmt werden.
Aus s_i'(x_i+1) = s_i+1'(x_i+1) mit i = 0, 1, ..., n - 2 folgt:

bi + cih +	di	h2 = bi+1
	2

Wegen den Gleichungen (2.10) und (2.11) folgt daraus:

fi+1 - fi	-	h(ci+1 + 2ci)	+ cih +	h(ci+1 - ci)	=	fi+2 - fi+1	-	h(ci+2 + 2ci+1)
h		6		2		h		6

Þ ci + 4ci+1 + ci+2 = 6	fi - 2fi+1 + fi+2	(2.12)
	h2

Natürliche Randbedingungen:

Die natürlichen Randbedingungen einer Spline-Funktion sind:

s''(x_n) = 0
Wegen Gleichung (2.6) ist c₀ = s₀''(x₀).
Þ c₀ = 0       (2.13)
Aus s_i''(x_i+1) = s_i+1''(x_i+1) mit i = 0, 1, ..., n - 1 und Gleichungen (2.6) folgt s_n-1''(x_n) = c_n.
Þ c_n = 0       (2.14)
Aus den Gleichungen (2.12), (2.13) und (2.14) ergibt sich folgendes Gleichungssytem:

																		=						(2.15)
		1	0	0	0	...	0	0	0						c0						0
		1	4	1	0	...	0	0	0						c1						6(f0 - 2f1 + f2) h2
		0	1	4	1	...	0	0	0						c2						6(f1 - 2f2 + f3) h2
		:	:	:	:		:	:	:						:						:
		0	0	0	0	...	1	4	1						cn-1						6(fn-2 - 2fn-1 + fn) h2
		0	0	0	0	...	0	0	1						cn						0

HERMITEsche Randbedingungen:

Die HERMITEschen Randbedingungen einer Spline-Funktion sind:

s'(x_n) = f '_n
Aus Gleichung (2.11) folgt

c1 + 2c0 =	6(f1 - f0 + f '0h)	(2.16)
	h2

Aus s'_n-1(x_n) = f '_n folgt wegen Gleichung (2.8)

bn-1 + cn-1h +	dn-12	= f'n
	2

Þ	fn - fn-1	-	(cn + 2cn-1)h	+	6cn-1h	+	(3cn - 3cn-1)h	= f 'n
	h		6		6		6

Þ cn-1 + 2cn =	6(fn-1 - fn + f 'nh)	(2.17)
	h2

Aus den Gleichungen (2.12), (2.16) und (2.17) ergibt sich folgendes Gleichungssytem:

																		=						(2.18)
		2	1	0	0	...	0	0	0						c0						6(f1 - f0 + f '0h) h2
		1	4	1	0	...	0	0	0						c1						6(f0 - 2f1 + f2) h2
		0	1	4	1	...	0	0	0						c2						6(f1 - 2f2 + f3) h2
		:	:	:	:		:	:	:						:						:
		0	0	0	0	...	1	4	1						cn-1						6(fn-2 - 2fn-1 + fn) h2
		0	0	0	0	...	0	1	2						cn						6(fn-1 - fn + f 'nh) h2

Periodische Randbedingungen:

Die periodischen Randbedingungen einer Spline-Funktion sind:

s''(x₀) = s''(x_n)
Aus s'(x₀) = s'(x_n) folgt wegen den Gleichungen (2.5) und (2.8)

bn-1h = b0h - cn-1h2 -	dn-1	h3
	2

Þ bn-1h = b0h -	cn-1 + cn	h2       (2.19)
	2

Aus s''(x₀) = s''(x_n) folgt wegen den Gleichungen (2.9) und (2.10)
c₀ = c_n-1 + d_n-1h
Þ c₀ = c_n       (2.20)
Wegen Gleichung (2.7) gilt

an-1 + bn-1h +	cn-1	h2 +	dn-1	h3 = fn
	2		6

Daraus folgt wegen den Gleichungen (2.4), (2.10), (2.11), (2.19) und (2.20)

fn-1 + bn-1h +	cn-1	h2 +	dn-1	h3 = fn
	2		6

Þ b0h -	(cn-1 + cn)	h2 +	cn-1	h2 +	(cn - cn-1)	h2 = fn - fn-1
	2		2		6

Þ (f1 - f0) -	(2c0 + c1)	h2 -	3cn	h2 +	(cn - cn-1)	h2 = fn - fn-1
	6		6		6

Þ -(2c₀ + c₁ + c_n-1 + 2c_n)h² = 6(f_n - f_n-1) - 6(f₁ - f₀)

4c0 + c1 + cn-1 =	6(f1 - f0) - 6(fn - fn-1)	(2.21)
	h2

Aus den Gleichungen (2.12), (2.20) und (2.21) ergibt sich folgendes Gleichungssytem:

																		=						(2.22)
		4	1	0	0	...	0	1	0						c0						6(f1 - f0)h-2 - 6(fn - fn-1)h-2
		1	4	1	0	...	0	0	0						c1						6(f0 - 2f1 + f2)h-2
		0	1	4	1	...	0	0	0						c2						6(f1 - 2f2 + f3)h-2
		:	:	:	:		:	:	:						:						:
		0	0	0	0	...	1	4	1						cn-1						6(fn-2 - 2fn-1 + fn)h-2
		1	0	0	0	...	0	0	-1						cn						0

Inhalt
Spline-Interpolation

Hosted by www.Geocities.ws