Prof. Dr. F. Natterer WS 2001/02

Übungen zur Vorlesung Einführung in die Numerische Mathematik

Übungsblatt 13 , Abgabe: 01.02.2002 , 13.00 Uhr, Übungskasten F17, F25, F29

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

Aufgabe 49: (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 50: (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 51: (4 Punkte) Berechnen Sie den Spline B_{0,4}(x) für x_{i} = i, i = 0, 1, 2, 3, 4 und stellen Sie ihn graphisch dar.

Aufgabe 52: (Programmieraufgabe, 4 Punkte) Schreiben Sie ein Programm

deconvolve (w, y, n) ,

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