Universität des Saarlandes Wintersemester 2000/2001 Fachbereich Mathematik Prof. Dr. A. Arnold / M. Ehrhardt

12. Übungsblatt zur Vorlesung “Praktische Mathematik” (Trigonometrische Approximation, Schnelle Fourier–Transformation)

\underline{1. Aufgabe} (2 Punkte) Berechnen Sie zu den gegebenen Werten

\begin{matrix}x_{j} & 0 & π/2 & π & 3π/2 \\ f_{j} & 0 & 3/16 & 0 & 15/16 \end{matrix}

das trigonometrische Interpolationspolynom. \underline{2. Aufgabe} (3 Punkte) Berechnen Sie das trigonometrische Ausgleichspolynom 1. Grades T mit

T (x) = a + b cos x + c sin x

zu den vier Punkten (0, 0), (π/2, 1), (π, −1), (3π/2, 1). Skizzieren Sie die vorgegebenen Punkte sowie die berechnete Ausgleichskurve. \underline{3. Aufgabe} (5 Punkte (0.5+0.5+2+2)) Sei ω_{N} := exp(2πi/N), N ∈ ℕ, i^{2} = −1.

a) Zeigen Sie (i) ω_{N}^{N} = 1, ω_{2N}^{N} = −1; (ii) ω_{2N}^{j} · ω_{N}^{j·k} = ω_{2N}^{j(2k+1)}, k, j = 0, …, N − 1.

b) Sei ω_{N}^{(j)} = (ω_{N}^{j·k})_{k=0,...,N−1}, f̂ = (f_{k})_{k=0,...,N−1} ∈ ℝ^{N} und d_{j} = 2 [f̂, ω_{N}^{(j)}]_{N} ω_{2N}^{−j},

j = 0, …, N − 1, wobei [c, d]_{N} = \frac{1}{N} ∑_{k=0}^{N−1} c_{k}d̄_{k}.

Man zeige die Fourier–Synthese

f_{k} = ∑_{j=0}^{N−1} \frac{d_{j}}{2} ω_{2N}^{j(2k+1)}.

Hinweis: Benutzen Sie die Darstellung f_{k} = ∑_{j=0}^{N−1}[f̂, ω_{N}^{(j)}]_{N} ω_{N}^{j·k}. c) Sind f_{k} ∈ ℝ, k = 0, …, n − 1, f_{2n−1−k} = f_{k}, k = 0, …, n − 1, so gilt mit

N = 2n in b)

(i) d_{j} ∈ ℝ, j = 0, …, N − 1, (ii) d_{2n−j} = −d_{j}, j = 1, …, n.

d) Sei p das Interpolationspolynom zu den Stützpaaren (x_{k,n}, f_{k}), k = 0, …, n − 1, wobei x_{k,n} die Nullstellen des n-ten Tschebyscheff–Polynoms T_{n}(x) der 1. Art sind, sowie (f_{k})_{k=0}^{n−1} ∈ ℝ^{n}. Man zeige, daß mit den Koeffizienten d_{j} aus b), c) gilt

p(x) = \frac{d_{0}}{2} + ∑_{j=1}^{n−1} d_{j}T_{j}(x).

Hinweis: Zeigen sie hierzu

(i) T_{j}(x_{k,n}) = \frac{1}{2} [ω_{4n}^{j(2k+1)} + ω_{4n}^{−j(2k+1)}],

(ii) f_{k} = \frac{d_{0}}{2} + \frac{1}{2} ∑_{j=1}^{n−1} d_{j} (ω_{4n}^{j(2k+1)} + ω_{4n}^{−j(2k+1)}).

\underline{4. Aufgabe} (Praktische Aufgabe) (5 Punkte)

Bestimmen Sie die Koeffizienten d_{j}, j = 0, …, n−1, des Interpolationspolynoms aus der 3. Aufgabe, Teil d) mit der schnellen Fourier–Transformation. Interpolieren Sie dabei

a) f(x) = x^{1/3}, x ∈ [0, 64],

b) f(x) = log(x), x ∈ (0, 1],

mit N = 2^{m}, m = 2(2)10. (Das Intervall [-1,1] ist affin–linear auf [0,64] bzw. [0,1] zu transformieren.) Berechnen Sie den auftretenden Fehler an (den linear zu transformierenden) Stellen

x_{j} = −1 + j/10, j = 1, 2, …, 20.

Zur Auswertung von p(x) = d_{0}/2 + ∑_{j=1}^{n−1} d_{j}T_{j}(x) verwende man folgende Verallgemeinerung des Horner–Schemas:

b_{n} := b_{n+1} := 0,
b_{k} := 2xb_{k+1} − b_{k+2} + d_{k},  k = n − 1, n − 2, …, 0,
p(x) = \frac{b_{0} − b_{2}}{2} .

\underline{Zusatzaufgabe} (3 Punkte)

Warum funktioniert das obige Horner–Schema und warum ist es numerisch vorteilhaft?

Abgabe der Lösungen zu den theoretischen Aufgaben am Di, 30.1.01 vor der Vorlesung. Abgabe der Lösungen zu der praktischen Aufgabe am Di, 6.2.01 in den Sprechstunden.