Prof. Dr. F. Natterer WS 2001/02

Übungen zur Vorlesung Einführung in die Numerische Mathematik

Übungsblatt 12 , Abgabe: 25.01.2002 , 13.00 Uhr, Übungskasten F17, F25, F29

Die Programmieraufgabe 48 darf eine Woche später abgegeben werden.

Aufgabe 45: (4 Punkte) Seien x_{0}, …, x_{n} paarweise verschiedene Stützstellen und y_{0}, …, y_{n} zugehörige Stützwerte. Zeigen Sie: Ist σ_{0}, …, σ_{n} irgend eine Permutation der Zahlen 0, …, n, so ist

[y_{0}, …, y_{n}] = [y_{σ_{0}}, …, y_{σ_{n}}] .

Aufgabe 46: (4 Punkte) Berechnen Sie sämtliche Eigenwerte und Eigenvektoren der Matrix W aus Satz 1 aus §3, Teil V.

Aufgabe 47: (4 Punkte) Seien f = (f_{0}, …, f_{n−1}) und g = (g_{0}, …, g_{n−1}) Vektoren aus IR^{n}, welche wir periodisch fortsetzen durch

f_{m·n+r} = f_{r} ∀ m ∈ ZZ 0 ≤ r < n ,

ebenso für g. Wir nennen Vektoren mit dieser Eigenschaft n-periodisch. Für n-periodische Vektoren e, h definieren wir

e · h durch (e · h)_{j} = e_{j}h_{j} ,
e ∗ h durch (e ∗ h)_{j} = \frac{1}{n} ∑_{ℓ=0}^{n−1} e_{j−ℓ}h_{ℓ} , die Faltung ,

und ê als n-periodische Fortsetzung der Fourier - Transformierten der Länge n von (e_{0}, …, e_{n−1}).

(a) Zeigen Sie, daß für die n-periodischen Vektoren gilt

f̂ ∗ g = f̂· ĝ .

(b) Sei W die Matrix

W = ( \begin{matrix}w_{0} & w_{1} & ⋯ & w_{n−1} \\ w_{1} & w_{0} & ⋯ & w_{n−2} \\ ⋮ & ⋮ & ... & ⋮ \\ w_{n−1} & w_{n−2} & ⋯ & w_{0} \end{matrix} ) , w_{i} ∈ C ,

und y ∈ C^{n}. Zeigen Sie, daß W y und W^{−1}y (falls W^{−1} existiert) in O (n log_{2} n) Rechenoperationen berechnet werden kann (n = 2^{p}).

Aufgabe 48: (Programmieraufgabe, 4 Punkte) Schreiben Sie ein rekursives Programm fft(y, n, sign) zur schnellen Fourier - Transformation der Länge n = 2^{k}. Für sign = −1 soll die direkte, für sign = +1 die inverse Transformation durchgeführt werden. Prüfen Sie nach, ob Ihr Programm für einige Folgen komplexer Zahlen y_{0}, …, y_{n−1} nach den Aufrufen fft(y, n, −1), fft(y, n, +1), eventuell bis auf einen Faktor n, wieder die ursprüngliche Folge liefert.