Numerik I Wintersemester 97/98 Dr. Walter Oevel 13. Januar 1998

Ü b u n g s b l a t t 10

Aufgabe 30: (Zur geometrischen Interpretation der Konditionszahl) Es soll gezeigt werden, daß eine Matrix A = (a⃗_{1}, …, a⃗_{n}) dann schlecht konditioniert ist, falls einige der Spalten a⃗_{i} ∈ ℝ^{n} “fast parallel” sind. Zeige: für jedes Spaltenpaar

i_{1} ≠ i_{2} gilt mit dem durch cos(ϕ) = \frac{<a⃗_{i_{1}}, a⃗_{i_{2}} >}{||a⃗_{i_{1}} ||_{2}||a⃗_{i_{2}} ||_{2}} gegebenen Winkel ϕ zwischen a⃗_{i_{1}} und

a⃗_{i_{2}} die Abschätzung

cond_{2}(A) ≥ \frac{\sqrt{1 + 3 cos^{2}(ϕ)}}{| sin(ϕ)|} .  (4)

Anleitung: mit ||A||_{2} ≥ ||Ax⃗_{+}||_{2}/||x⃗_{+}||_{2} und ||A^{−1}||_{2} ≥ ||x⃗_{−}||_{2}/||Ax⃗_{−}||_{2} folgt

cond_{2}(A) ≥ \begin{matrix}||x⃗_{−}|| & 2 \\ ||x⃗_{+}|| & 2 \end{matrix} \begin{matrix}||Ax⃗_{+}|| & 2 \\ ||Ax⃗_{−}|| & 2 \end{matrix} für beliebige Vektorpaare x⃗_{±} ≠ 0. Mit der Standard-

basis e⃗_{i} = (0, …, 0, 1, 0, …, 0) wähle x⃗_{±} = e⃗_{i_{1}} ± γ e⃗_{i_{2}} mit einem geeigneten γ.

Aufgabe 31: (Zur Konditionierung von Gleichungslösern)

a) Die Matrix A = ( \begin{matrix}ϵ & 1 \\ 1 & 1 \end{matrix} ) wird durch Gauß-Elimination mit bzw. ohne Pivo-

tierung auf die obere Dreiecksmatrix R transformiert (vergleiche Aufgabe 25). Berechne jeweils R und vergleiche für |ϵ| ≪ 1 die Konditionszahlen cond_{∞}(A) und cond_{∞}(R) (exakte Rechnung ohne Rundung). (4)

Man sieht: durch Gauß-Elimination ohne Pivotierung kann die Konditionierung eines Gleichungssystems bei Transformation auf gestaffelte Form extrem verschlechtert werden. Diese Situation kann für die Cholesky-Zerlegung nicht auftreten:

b) Zeige, daß für die Cholesky-Faktoren einer s.p.d. Matrix A = LL^{T} gilt:

cond_{2}(L) = cond_{2}(L^{T}) = \sqrt{cond_{2}(A)} ≤ cond_{2}(A) .  (1)

Ähnliches gilt für die QR-Zerlegung:

c) Zeige, daß durch Multiplikation mit orthogonalem H die spektrale Konditionszahl nicht verändert wird: cond_{2}(HA) = cond_{2}(A). (1)

Folgerung: alle Zwischenschemata H^{(j−1)} ⋯ H^{(1)}A der QR-Zerlegung durch Householder-Transformationen haben dieselbe Konditionierung wie die Ausgangsmatrix A.

Aufgabe 32: (Zum Einzelschrittverfahren)

a) Für welche Werte von ϵ konvergiert das Einzelschrittverfahren für Gleichungssysteme mit der Koeffizientenmatrix

( \begin{matrix}1 & ϵ & … & ϵ \\ ⋮ & ... & ... & ⋮ \\ ⋮ & ... & ... & ϵ \\ 1 & … & … & 1 \end{matrix} ) ?  (3)

Anleitung: (D + l)^{−1}r läßt sich explizit angeben.

b) Es sei ϵ = 0.05. Wieviele Iterationsschritte werden benötigt, um die Lösung bezüglich ||.||_{1} garantiert auf die relative Genauigkeit 10^{−10} zu bestimmen? (1)

Aufgabe 33: (Zur Konvergenz des Einzelschrittverfahrens bei positiv definiten Matrizen) Zeige, daß das Einzelschrittverfahren für alle (reellen) s.p.d. Matrizen konvergiert. (4)

Anleitung: Die Matrix sei in der Form A = l + D + l^{T} zerlegt. Betrachte einen (eventuell komplexen) Eigenvektor x⃗ von (D + l)^{−1}l^{T} zum (eventuell komplexen) Eigenwert λ. Zeige

λ = \frac{⟨x⃗, l^{T} x⃗⟩}{⟨x⃗, lx⃗⟩ + ⟨x⃗, D x⃗⟩} ,

Abgabe: Mittwoch, 21. 1., in den Übungsgruppen

wobei ⟨x⃗, y⃗⟩ = ∑_{i} x̄_{i}y_{i} das übliche komplexe Skalarprodukt ist. Aus der positiven Definitheit von A folgt eine geeignete Abschätzung für |λ|.