Dr. Frank Wübbeling WS 2002/03

Übungen zur Vorlesung Einführung in die Numerische Mathematik

Übungsblatt 10 , Abgabe: 21.1.2003, Programmieraufgabe 1 Woche später , 11.00 Uhr

Aufgabe 37: (4 Punkte) Sei s ein (kubischer) Spline der Ordnung 4 zu den Knoten x_{0} bis x_{n} auf dem Intervall [a, b], der die reellen Punkte (x_{i}, y_{i}), i = 0 … n, interpoliert. Sei g ∈ C^{2}([a, b]) eine weitere interpolierende Funktion mit g′(a) = s′(a) und g′(b) = s′(b). Dann gilt

∫_{a}^{b}(s′′(x))^{2}dx ≤ ∫_{a}^{b}(g′′(x))^{2}dx.

Hinweis: Schreiben Sie g′′ = s′′ + (g′′ − s′′), rechnen Sie die Integrale aus und verwenden Sie partielle Integration. Aufgabe 38: (8 Punkte)

a) Schreiben Sie ein Programm, das den FFT–Algorithmus der Vorlesung implementiert für (inverse und direkte) Fouriertransformationen der Länge 2^{n}. Testen Sie es, indem sie die Fouriertransformation von Vektoren der Form y_{k} = e^{2πikl/n}, l ganz, berechnen und mit der analytischen Lösung vergleichen.

b) Wenden Sie Ihr Programm auf ein einfaches Bildkompressionsproblem an. Auf der Homepage der Vorlesung unter den Übungen und unter /u/wuebbel auf den Rechnern des Fachbereichs finden Sie eine 256x256-Matrix M_{1} unter dem Namen “trui.matrix”, die ein Bild darstellt (im Textformat). Unter matlab laden Sie das Bild mit load 'trui.matrix'

und zeigen Sie es mit an mit imagesc(trui) und colormap('gray').

Wenden Sie nun die Fouriertransformation auf alle Zeilenvektoren von M_{1} an, und fügen Sie die Transformierten wieder zu einer Matrix M_{2} zusammen. Wenden Sie nun die Fouriertransformation auf die Spaltenvektoren von M_{2} an und Sie erhalten wie oben eine neue Matrix, M_{3}. Setzen Sie nun (M_{3})_{ik} = 0, falls |(M_{3})_{ik}| kleiner ist als ein Schwellenwert ϵ, so daß nur etwa zehn Prozent der Elemente von M_{3} übrigbleiben. Führen Sie nun die inverse Fouriertransformation zunächst auf den Spalten, dann auf den Zeilen von M_{3} durch (wie oben). Sie erhalten eine Matrix M_{4}. Zeigen Sie den Realteil wieder als Falschfarbenbild an und vergleichen Sie mit dem Originalbild. Aufgabe 39: (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 40: (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.