<<

. 24
( 31 .)



>>

a
die Anzahl an Multiplikationen/Divisionen, die wir fur die FFT benotigen. Wir
¨ ¨
k
vernachl¨ssigen die Berechnung von q . Es gilt
a

M0 = 0
n n
= 2Mp + 2p
Mp+1 = 2Mp + +
2 2

also
1 1
Mp = 2p’1 + 2 · 2p’2 + . . . + 2 · 2 · . . . · 2 = p · 2p’1 = · p · 2p = log2 n · n
2 2
p’1 mal

Damit gilt der
Interpolation durch Splines 105




Satz 5.24 (Aufwand FFT). Eine Fouriertransformation der L¨nge n = 2p
a
kann mit O(n · log2 n) komplexen Multiplikationen berechnet werden.
Bemerkung 5.25. Die Anzahl an Additionen/Subtraktionen ergibt sich ebenfalls
zu O(n · log2 n).
Bemerkung 5.26. Es gilt:

O(n) < O(n · log2 n) < O(n2 ).

5.3.4 Anwendungen
Die FT ¬ndet Ihre Anwendung z.B. in der Signalverarbeitung. Eine wichtige An-
wendung ist die Frequenzanalyse, hier haben die Fourierkoe¬zienten der trigono-
metrischen Polynome (im Gegensatz zu herk¨mmlichen Koe¬zienten) eine klare
o
physikalische Bedeutung: Jeder der Fourierkoe¬zienten ak bzw- bk geh¨rt zu ei-
o
ner bestimmten Frequenz im Sinus bzw. Kosinus. Die Anwendbarkeit der FT
ergibt sich z.B. wenn Signale durch St¨rungen (Rauschen) beein¬‚ußt werden. Die
o
FT gl¨ttet und das Originalresultat kann h¨u¬g reproduziert werden, bzw. die
a a
Hauptfrequenzen des Signals k¨nnen besser identi¬ziert werden. Dies nutzt man
o
dann z.B. beim Filtern aus. Hat man einmal ein Signal zerlegt und stehen die
Fourierkoe¬zienten (die eine bestimmte Frequenz beschreiben) zur Verfugung
¨
kann man durch Vergr¨ßern oder Verkleinern der einzelnen Koe¬zienten spe-
o
zielle Frequenzen unterschiedlich stark betonen oder sogar ganz herausnehmen
(Filtern). Weitere Anwendungen sind die Zerlegung eines Signals in verschiede-
nen Frequenzbereiche oder Datenkompression (Null“Setzen der Koe¬zienten mit
geringem Betrag). Da die Anwendungen alle in Echtzeit durchgefuhrt werden
¨
mussen ist eine e¬ziente Implementierung im Sinne der FFT o¬ensichtlich.
¨


5.4 Spline“Interpolation
Spline“Funktionen, die sich stuckweise aus Polynomen zusammensetzen, verbin-
¨
den den Vorteil einer glatten oszillationsfreien Interpolation mit denjenigen, die
der Umgang mit Polynomen niedrigen Grades mit sich bringt.

5.4.1 Polynom“Splines
Sei ∆ = {a = x0 < x1 < . . . < xn = b} eine Zerlegung des Intervalls [a, b] ‚ IR
mit inneren Knoten x1 , . . . , xn’1 und Randknoten x0 , xn .
De¬nition 5.27. Eine Funktion s : [a, b] ’ IR heißt Polynom-Spline vom Grad
l, l = (0, 1, 2, . . .) zur Zerlegung ∆, wenn sie folgende Eigenschaften besitzt:
106 Interpolation




(a) s ∈ C l’1 [a, b]

(b) s ∈ Πl fur xj ¤ x < xj+1 , j = 0, 1, . . . , n ’ 1.
¨

Hierbei ist C ’1 [a, b] der Raum der auf [a, b] stuckweise stetigen Funktionen. Die
¨
Menge aller Polynom-Splines vom Grade l zur Zerlegung ∆ bezeichnen wir mit
Sl (∆). Fortan wird schlechthin von Splines gesprochen.

Beispiel 5.28. (Lineare Splines): Sind (n + 1) Punkte

(x0 , y0 ), (x1 , y1 ), . . . , (xn , yn )

gegeben, so stellt der Polygonzug durch diese Punkte einen Spline s ∈ S1 (∆) dar.




x0 x1 x2 x3

Abbildung 5.3: Polynomspline vom Grade 1.


Beispiel 5.29. (Quadratische Splines): Bei ¨quidistanten Knoten xj = a+jh,
a
j = 0, . . . , n, ist
±
(x ’ xj )2 , xj ¤ x < xj+1


1
s(x) = 2 h2 + 2h(x ’ xj+1 ) ’ 2(x ’ xj+1 )2 , xj+1 ¤ x < xj+2
2h 

(xj+3 ’ x)2 , xj+2 ¤ x < xj+3

ein quadratischer B-Spline s ∈ S2 (∆).


s(x)


3/4
1/2 1/2

x j’1 xj x j+1 x j+2 x j+3 x j+4
Abbildung 5.4: Polynomspline vom Grade 2.
Interpolation durch Splines 107




Beispiel 5.30. Die Funktionen qlj : [a, b] ’ IR, j = 0, 1, . . . , n ’ 1,

(x ’ xj )l , x ≥ xj
xj )l
qlj (x) = (x ’ :=
+
0 , x < xj

sind Splines vom Grade l zu ∆. Man beachte, dass qlj keine Polynome in [a, b]
sind.



ql ql ql ql
0 1 2 3




a=x 0 x1 x2 x3 x 4=b
Abbildung 5.5: Splines vom Grade l.


Der Spline-Raum Sl (∆) ist ein linearer Teilraum von C l’1 (∆). Der folgende Satz
gibt Auskunft uber eine Basis von Sl (∆).
¨

Satz 5.31. Die Menge Sl (∆) ist ein linearer Raum der Dimension n + l. Die
Elemente pi (x) = xi , (i = 0, . . . , l), qlj (x) = (x ’ xj )l (j = 1, . . . , n ’ 1) bilden
+
eine Basis von Sl (∆).

Beweis: Wir haben zu zeigen, dass es zu s ∈ Sl (∆) eine eindeutige Darstellung
l n’1
ai xi + bj (x ’ xj )l ,
s(x) = x ∈ [a, b],
+
i=0 j=1


gibt. Dies erkennt man durch Induktion bzgl. des Index j der Zerlegung ∆. Im
Intervall I1 = [x0 , x1 ] ist s ein Polynom s(x) = a0 + a1 x + . . . + al xl , also gilt die
Darstellung
l k’1
i
bj (x ’ xj )l
s(x) = ai x + +
i=0 j=1

fur k = 1 auf Ik = [x0 , xk ]. Wir betrachten nun
¨
l k’1
ai xi ’ bj (x ’ xj )l .
d(x) := s(x) ’ +
i=0 j=1
108 Interpolation




Dann ist d ∈ C l’1 (Ik+1 ) und d(x) = 0 fur x ∈ Ik . Außerdem ist d ∈ Πl in
¨
[xk , xk+1 ]. Also genugt d auf [xk , xk+1 ] der Di¬erentialgleichung
¨

d(l+1) (x) = 0, xk ¤ x ¤ xk+1
d(i) (xk ) = 0, i = 0, . . . , l ’ 1

Die L¨sung dieser Anfangswertaufgabe ist
o

d(x) = bk (x ’ xk )l , xk ¤ x, bk ∈ IR.
+


Damit ist die Behauptung fur den Index k + 1 gezeigt. Fur k = n bilden daher
¨ ¨
die n + l linear unabh¨ngigen Elemente
a

pi (x) = xi , qlj (x) = (x ’ xj )l ,
(i = 0, . . . , l), (j = 1, . . . , n ’ 1)
+


eine Basis von Sl (∆).
Wir untersuchen nun die folgende Interpolationsaufgabe:
Bestimme zu Stutzwerten yj , j = 0, . . . , n einen interpolierenden Spline s ∈ Sl (∆)
¨
mit
s(xj ) = yj , j = 0, . . . , n.
Die Stutzwerte yj sind dabei als Funktionswerte yj = f (xj ) einer hinreichend
¨
glatten Funktion f aufzufassen. Wegen dim Sl (∆) = n + l k¨nnen uber die n + 1
o ¨
Interpolationsbedingungen hinaus noch

n + l ’ (n + 1) = l ’ 1

freie Parameter bestimmt werden. Fur ungerades l = 2m ’ 1 ist dies eine gerade
¨
Anzahl 2m ’ 2 von Parametern, welche sich symmetrisch in den Randknoten
x0 , xn anordnen lassen.
Wir beschr¨nken uns nachfolgend auf den in der Praxis wichtigen Fall m = 2 der
a
kubischen Splines, d.h. Polynom“Splines mit l = 3, der sich besonders h¨u¬g in
a
den Anwendungen wieder¬ndet.


5.4.2 Kubische Splines
5.4.2.1 Einfuhrung und Aufgabenstellung
¨
Nach De¬nition ist ein Spline s ∈ C 2 [x0 , xn ] auf jedem der Intervalle [xk’1 , xk ],
k = 1, . . . , n durch

s(x) = sk (x) = ak + bk (x ’ xk’1 ) + ck (x ’ xk’1 )2 + dk (x ’ xk’1 )3
Interpolation durch Splines 109




gegeben. Neben den Interpolationsbedingungen

(5.21) s(xj ) = f (xj ), j = 0, . . . , n

erfordert die Glattheit s ∈ C 2 [x0 , xn ] (an den Nahtstellen sollen keine Knicke auf-
treten und die Krummungen sollen stetig ineinander ubergehen) die zusatzlichen
¨ ¨ ¨
Bedingungen

(5.22) sk (xk ) = sk+1 (xk ) und sk (xk ) = sk+1 (xk ), k = 1, . . . , n ’ 1.

Die 2n ’ 2 linearen Gleichungen in (5.22) ergeben dann zusammen mit den 2n
linearen Gleichungen aus (5.21) zusammen 4n ’ 2 lineare Gleichungen fur die ¨
4n Unbekannten ak , bk , ck , dk , k = 1, . . . , n. Das Problem ist somit zwar l¨sbar,
o
jedoch existieren ∞ viele L¨sungen. Der Grund liegt in den Randpunkten x0 und
o

<<

. 24
( 31 .)



>>