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

8. Übungsblatt zur Vorlesung “Praktische Mathematik” (Verfahren der konjugierten Gradienten)

\underline{1. Aufgabe} (3 Punkte)

Gegeben ist die Matrix A ∈ ℝ^{3×3} mit

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

Berechnen Sie, ausgehend vom Startvektor x_{0} = (0, 0, 0)^{⊤}, mit Hilfe des Verfahrens der konjugierten Gradienten die Lösung des Gleichungssystems Ax = b. Wieviele Iterationen sind dazu nötig?

\underline{2. Aufgabe} (4 Punkte (2+2))

a) Zeigen Sie: Um beim Verfahren der konjugierten Gradienten den Fehler in der Energienorm ∥ · ∥_{A} = (A · , ·)^{1/2} um einen Faktor ε zu reduzieren, d.h.

∥z_{m}∥_{A} = ∥x_{m} − x∥_{A} ≤ ε ∥z_{0}∥_{A} ,

benötigt man höchstens m Iterationen, wobei m die kleinste ganze Zahl ist mit

m ≥ \frac{1}{2} \sqrt{κ_{2}(A)} ln (\frac{2}{ε}) .

Hierbei bezeichnet κ_{2}(A) = ∥A∥_{2} · ∥A^{−1}∥_{2} die Konditionszahl bzgl. der 2–Norm. Hinweise:

(i) Benutzen Sie Satz 1 aus der Vorlesung mit ρ = \frac{\sqrt{κ_{2}(A)}−1}{\sqrt{κ_{2}(A)}+1}

(ii) Für a > 1 gilt

ln (\frac{a + 1}{a − 1}) > \frac{2}{a}.

b) Das Verfahren der konjugierten Gradienten werde auf eine positiv definite Matrix A angewendet. Es ist lediglich bekannt, daß ∥z_{0}∥_{A} = 1 und ∥z_{10}∥_{A} = 2^{−9} ist. Berechnen Sie aus diesen Informationen eine untere Schranke für κ_{2}(A) und überprüfen Sie damit die Ungleichung aus a).

\underline{3. Aufgabe} (3 Punkte)

Sei A ∈ ℝ^{n×n} eine positiv definite Matrix mit Eigenvektoren {v_{j}}_{1≤j≤n}. Der Vektor b ∈ ℝ^{n} sei eine Linearkombination von v_{1}, …, v_{k}, k ≤ n:

b = ∑_{j=1}^{k} γ_{j} v_{j}.

Zeigen Sie: Das Verfahren der konjugierten Gradienten zur Lösung von Ax = b liefert mit x_{0} = 0 die exakte Lösung nach k Schritten, d.h. z_{k} = x_{k} − x = 0.

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

Schreiben Sie ein Programm, welches ein Gleichungssystem Ax = b mit dem Verfahren der konjugierten Gradienten löst. Testen Sie das Programm an dem Gleichungssystem aus der 1. Aufgabe und an dem Beispiel der praktischen Aufgabe vom 6. Übungsblatt für N = 30 beziehungsweise N = 200. Die Iteration soll jeweils abgebrochen werden, wenn

∥x^{(k)} − x^{(k−1)}∥_{∞} ≤ 10^{−5}

ausfällt. Als Startwert wähle man x^{(0)} = 0. Man gebe jeweils die Anzahl der benötigten Iterationsschritte k, ∥x^{(k)} − x^{(k−1)}∥_{∞} und den Fehler max_{j=1,...,N−1} |v_{j} − u(x_{j})| tabellarisch an. Wiederholen Sie Ihre Berechnungen mit dem vorkonditionierten Verfahren der konjugierten Gradienten. 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, 19.12. vor der Vorlesung. Abgabe der Lösungen zu der praktischen Aufgabe am Di, 9.1.2001 in den Sprechstunden.