Prof. Dr. F. Natterer WS 1998/99

Übungen zur Vorlesung NUMERISCHE MATHEMATIK I

Übungsblatt 13, Abgabe: 02.02.1999, 11.00 Uhr, Übungskästen 43-48.

Die Programmieraufgabe muß erst am 09. Februar 1999 abgegeben werden.

Aufgabe 48: (4 Punkte) Seien x_{0}, …, x_{n−1}, y_{0}, …, y_{n−1} reell. Zeigen Sie:

(a)  x̂_{n−k} = \overline{x̂}_{k}, k = 0, …, n − 1.

(b) Mit z_{k} = x_{k} + iy_{k} gilt

x̂_{k} = \frac{1}{2} (\overline{ẑ}_{n−k} + ẑ_{k}) , ŷ_{k} = \frac{i}{2} (\overline{ẑ}_{n−k} − ẑ_{k}) .

(c) Zwei Fourier-Transformationen der Länge n auf reellen Daten kann man bis auf einen gemeinsamen reellen Faktor ausführen durch eine komplexe Fourier-Transformation der Länge n, plus n komplexe Additionen.

Aufgabe 49: (4 Punkte) Seien x_{0}, …, x_{n−1} reell. Sei n gerade und m = n/2. Sei

z_{j} = x_{2j} + ix_{2j+1} , j = 0, …, m − 1 .

Zeigen Sie:

(a)

2x̂_{k} = \frac{1}{2} (ẑ_{k} + \overline{ẑ}_{m−k}) − \frac{i}{2} (ẑ_{k} − \overline{ẑ}_{m−k}) e^{−2πik/n} , k = 0, …, m − 1 .

(b) Eine Fourier-Transformation der Länge n auf reellen Daten kann man bis auf einen gemeinsamen reellen Faktor ausführen durch eine komplexe Fourier-Transformation der Länge n/2, plus n komplexe Additionen, plus \frac{n}{2} komplexe Multiplikationen.

Aufgabe 50: (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 = ( w_{0} w_{1} … w_{n−1} ; w_{1} w_{0} … w_{n−2} ; ⋮ ; w_{n−1} w_{n−2}  w_{0} ) ,  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 51: (Programmieraufgabe, 4 Punkte) Schreiben Sie Programm

deconvolve (w, y, n) ,

welches für n = 2^{p} das Gleichungssystem W x = y mit der Matrix W aus Aufgabe 50(b) mit O (n log_{2} n) Rechenoperationen löst. Verwenden Sie Aufgabe 47.