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

7. Übungsblatt zur Vorlesung “Praktische Mathematik” (Tschebyscheff–Beschleunigung, Gradientenmethode)

\underline{1. Aufgabe} (1 Punkt) Zeigen Sie, daß die Tschebyscheff–Polynome (T_{n})_{n∈ℕ_{0}} bzgl. dem Skalarprodukt ⟨f, g⟩ = ∫_{−1}^{1} f(x)g(x)(1 − x^{2})^{− \frac{1}{2}} dx ein Orthogonalsystem bilden. \underline{2. Aufgabe} (3.5 Punkte (0.5+1+1+1)) Die Tschebyscheff–Polynome der 2. Art U_{n} sind definiert durch (x ∈ [−1, 1])

U_{0}(x) = 1, U_{1}(x) = 2x, und U_{n+1}(x) = 2xU_{n}(x) − U_{n−1}(x), n ≥ 1. Zeigen bzw. berechnen Sie:

a) U_{n} ist ein Polynom n–ten Grades.

b) U_{n}(cos θ) = \frac{sin[(n + 1)θ]}{sin θ}, θ ∈ (0, π).

c) U_{n}(1), U_{n}(−1).

d) T′_{n}(x) = nU_{n−1}(x), n ≥ 1, x ∈ [−1, 1]. Hinweis zu b): Vollständige Induktion und sin[(n + 1)θ] + sin[(n − 1)θ] = 2 cos θ sin(nθ). \underline{3. Aufgabe} (2.5 Punkte (1+1.5)) Zeigen Sie, daß die bei der Tschebyscheff–Beschleunigung auftretenden Koeffizienten ρ_{k} = 2σ_{2}T_{k−1}(σ_{2})/T_{k}(σ_{2}) der Zwei–Term–Rekursion

ρ_{1} = 2, ρ_{k+1} = \frac{1}{1 − \frac{1}{4}τ^{2}ρ_{k}}

genügen, wobei τ := 1/σ_{2}. Zeigen Sie ferner für den Grenzwert der Folge {ρ_{k}}, daß

lim_{k→∞} ρ_{k} =: ρ = \frac{2}{1 + \sqrt{1 − τ^{2}}}

Hinweis: Sie dürfen voraussetzen, daß die Folge {ρ_{k}} konvergiert.

\underline{4. Aufgabe} (3 Punkte)

Berechnen Sie, ausgehend vom Startvektor x_{0} = (0, 0, 0)^{⊤}, 3 Schritte des vorkonditionierten Verfahrens des steilsten Abstiegs zur näherungsweisen Lösung des Gleichungssystems Ax = b mit

A = (\begin{matrix}2 & −1 & 0 \\ −1 & 2 & −1 \\ 0 & −1 & 2 \end{matrix}) , b = (\begin{matrix}1 \\ 0 \\ 1 \end{matrix}) .

Verwenden Sie dabei die sog. diagonale Vorkonditionierung, d.h. als Vorkonditionierer die Matrix B = diag(A), die Diagonale von A.

Abgabe der Lösungen zu den theoretischen Aufgaben am Di, 12.12. vor der Vorlesung.