<<

. 23
( 31 .)



>>

Gegeben seien Stutzstellen (xk , fk ), k = 0, . . . , n ’ 1 mit
¨

xk = k
n
Trigonometrische Interpolation 101




Gesucht ist ein Trigonometrisches Polynom
n’1
βk ω k
P (ω) = p(x) =
k=0

mit √
ω := eix = cos(x) + i · sin(x), i= ’1
so dass
p(xk ) = fk , k = 0, 1, . . . , n ’ 1.
2πi
Bemerkung 5.19. Ausdrucke der Form e n ·k heißen n™te Einheitswurzeln k =
¨
0, . . . , n ’ 1. Sie liegen alle auf dem Einheitskreis.

Im x
2πi 3 2πi 1
i
e8 e8



1 Re x
’1


2πi 5
2πi 7
e8 ’i e8


Abbildung 5.2: Einheitswurzeln, hier am Beispiel n = 8.


Nach Satz 5.3 ist die Interpolationsaufgabe
n’1
j
ωk = ei·xk ,
(5.10) P (ωk ) = β j ω k = fk , (Fourier“Synthese)
j=0

eindeutig l¨sbar. Die Interpolationsaufgabe (5.10) ist schreibbar als
o

f = Wβ

mit « « « 
n’1
f0 1 ω0 · · · ω0 β0
¬ ·¬ . ·¬ . ·
f =¬ . ·=¬ . . . ·¬ . ·
. . .
. . . .  . 
n’1
fn’1 1 ωn’1 · · · ωn’1 βn’1
=:W
=:f =:β

Es gilt die Beziehung
¯ ¯
W W T = nI,
(5.11) mit W konjugiert komplexe Matrix zu W,
102 Interpolation




da
n’1 n’1 n’1 n’1
’2πi
2πi 2πi
¯ ωk · ωlj =
j
(W W T )k,l = ·k·j ·l·j ·j(k’l)
qj
¯ e ·e = e =
n n n

j=0 j=0 j=0 j=0

2πi
·(k’l)
mit q = e . Dies ist eine geometrische Reihe und wir erhalten weiter
n


1’q n
n’1
0, falls k = l
, falls q = 1 q n =1
qj = 1’q
=
n, falls k = l.
n, falls q = 1
j=0

Damit ist die Inverse von W aus (5.11) einfach zu berechnen:
1 ¯T 1¯
W ’1 = ’ β = nW T f
(5.12) W
n
In Komponentenschreibweise:
n’1
1 ’2πi
·j·k
(5.13) βj = fk · e n
n k=0


Formel (5.13) wird Diskrete Fouriertransformation der L¨nge n genannt.
a
Bemerkung 5.20. Der Aufwand zur Berechnung aller Komponenten betr¨gt of-
a
fensichtlich O(n2 ).

5.3.2 Trigonometrische Interpolation
¨
Der Zusammenhang mit der Uberschrift dieses Abschnittes ergibt sich durch den
nachfolgenden Satz.
Satz 5.21 (Reelle Fouriertransformation). De¬niert man
n’1 n’1
2 2πkj 2 2πkj
aj := fk ·cos , bj := fk ·sin , j = 0, . . . , n’1.
n n n n
k=0 k=0

und setzt fur ungerades n = 2m + 1
¨
m
a0
Ψ(x) := + (aj cos(jx) + bj sin(jx))
2 j=1

bzw. fur gerades n = 2m
¨
m’1
a0 am
Ψ(x) := + (aj cos(jx) + bj sin(jx)) + cos(mx)
2 2
j=1
Trigonometrische Interpolation 103




so gilt
Ψ(xk ) = fk , k = 0, . . . , n ’ 1
mit xk aus (5.3.1).
Beweis: Zun¨chst notieren wir einige interessante Beziehungen.
a
n
Wegen ωk = 1 folgt fur die komplexen Koe¬zienten:
¨
n’1 n’1
1 1
j’n j
(5.14) βn’j = fk ω k = fk ω k .
n n
k=0 k=0

Der Zusammenhang der reellen Fourierkoe¬zienten mit den komplexen Koe¬zi-
enten ergibt sich wegen (5.13) zu
1 1
(5.15) βj = (aj ’ ibj ), und βn’j = (aj + ibj ).
2 2
Hierraus folgt unmittelbar die Beziehung
j n’j
(5.16) βj ωk + βn’j ωk = aj cos jxk + bj sin jxk .

Nach diesen Voruberlegungen wenden wir uns nun dem eigentlichen Beweis zu.
¨
Fur gerades n = 2m ist
¨
m
b0 = 0, bm = 0, ωk = cos(mxk ),

und daher gilt (wegen f = W β) mit (5.14)“(5.16)
n’1 m’1
j j n’j m
fk = βj ωk = β0 + (βj ωk + βn’j ωk ) + βm ωk
j=0 j=1
a0 am
cos(mx)
aj cos(jxk )+bj sin(jxk ) 2
2
= ψ(xk ).

Ebenso folgt die Behauptung fur ungerades n = 2m + 1.
¨
Bemerkung 5.22. Der Aufwand zur Berechnung aller Komponenten betr¨gt
a
O(n2 ).

5.3.3 Schnelle Fourier“Transformation (FFT)
Cooley“Tukey haben eine M¨glichkeit gefunden die diskrete Fouriertransforma-
o
’2πi
tion e¬zienter durchzufuhren. Sei hierzu q = e n und n gerade, n = 2m, dann
¨
ist (5.13) darstellbar als
n’1
1
fj · q j·k .
(5.17) βk =
n j=0
104 Interpolation




Es gilt q n = 1 und q n/2 = ’1.
Idee: Spalte Summe in (5.17) nach geraden und ungeraden Indizes auf.
m’1 m’1
1 (2l)k
f2l+1 · q (2l+1)k
βk = f2l · q +
n l=0 l=0
m’1 m’1
1 1 1
lk lk
f2l · q 2 + qk f2l+1 · q 2
=
2 n/2 l=0 n/2 l=0
1
gk + q k uk
=:
2
2πi
n
2
Wegen q = e lassen sich gk und uk als Fouriertransformation der L¨nge
a
n/2
2
berechnen. Weiterhin folgt durch einfaches Nachrechnen

gk+m = gk
(5.18)
uk+m = uk

und damit fur k = 0, 1, . . . , m ’ 1
¨
1
gk + q k uk
(5.19) βk =
2
und
1 1
gk + q k+m uk = gk ’ q k uk .
(5.20) βk+m =
2 2
Bemerkung 5.23. Die gk aus (5.19) k¨nnen somit bei (5.20) direkt ohne zus¨tz-
o a
lichen Rechenaufwand wieder verwendet werden.
Anstelle von 1 mal n2 hat man jetzt nur noch 2 mal (n/2)2 , also 1 n2 als Aufwand.
2


Sei nun n = 2p . Die Idee ist es nun die zuvor dargestellte Berechnungsvorschrift
mehrfach anzuwenden, also auch gk und uk gem¨ß (5.20) zu bestimmen. Sei Mp

<<

. 23
( 31 .)



>>