Numerik I Wintersemester 97/98 Dr. Walter Oevel 16. 12. 1997

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

Aufgabe 25: (Zu Gauß-Elimination und Pivotierung) In folgendem Beispiel kann jede Zwischenrechnung per Hand vorgenommen werden. Es sei |ϵ| ≪ τ = Maschinengenauigkeit (etwa ϵ = 10^{−20} bei τ ≈ 10^{−16}). Betrachte das Gleichungssystem

( \begin{matrix}ϵ & 1 \\ 1 & 1 \end{matrix} ) ( \begin{matrix}x \\ y \end{matrix} ) = ( \begin{matrix}1 \\ 2 \end{matrix} ) .

a) Bestimme die exakte Lösung, entwickle sie in eine Potenzreihe in ϵ und benutze dann |ϵ| ≪ τ, um die exakte Lösung in der Maschinengenauigkeit anzugeben. (1)

b) Führe die Gauß-Elimination ohne Zeilenvertauschung durch, wobei in jedem Rechenschritt auf die Maschinengenauigkeit gerundet wird (darstellbar z.B. mittels rd(ϵ^{−1})). (2)

c) Vertausche die Zeilen und führe die gerundete Gauß-Elimination noch einmal durch. (2)

Aufgabe 26: (Eigenschaften positiv definiter Matrizen) Eine reelle symmetrische n × n-Matrix A = (a_{ij}) heißt positiv definit (s.p.d.), wenn ⟨x⃗, Ax⃗ ⟩ > 0 für alle 0 ≠ x⃗ ∈ ℝ^{n}, wobei ⟨., .⟩ das übliche Euklidische Skalarprodukt darstellt. Zeige:

a) a_{ii} > 0 , i = 1, …, n . (1)

b) a_{ij}^{2} < a_{ii} a_{jj} , i ≠ j ∈ {1, …, n}. (1)

c) Alle Eigenwerte sind rell und positiv, die Matrix ist invertierbar. (1)

d) Alle durch Streichen von k Zeilen und den entsprechenden Spalten entstehenden symmetrischen Untermatrizen der Größe (n − k) × (n − k) sind wieder positiv definit. (1)

e) Betrachte die Blockzerlegung A = ( \begin{matrix}a & a⃗ \\ a^{T} & a_{nn} \end{matrix} ) mit dem (n − 1) × (n − 1)-Block a. Zeige: a

ist invertierbar, und es gilt a_{nn} > ⟨ a⃗, a^{−1}a⃗ ⟩ . (2)

Anleitung: b) Betrachte Vektoren der Form \begin{aligned}& & & & & & i & & & & & & & & j \\ x⃗ = ( 0 & , & … & , & 0 & , & 1 & , & 0 & , & … & , & 0 & , & x & , & 0 & , & … & , & 0 )^{T} \end{aligned} mit geeignetem x. e) Betrachte ⟨x⃗, Ax⃗ ⟩ mit x⃗ = (?, 1)^{T}.

Aufgabe 27: (Cholesky-Zerlegung dünnbesetzter Matrizen)

Betrachte eine s.p.d. Matrix der Form A = ( \begin{matrix}d_{1} & a_{1} & 0 & … & 0 & a_{n} \\ a_{1} & d_{2} & ... & 0 & … & 0 \\ 0 & ... & ... & ... & ... & ⋮ \\ ⋮ & ... & ... & ... & ... & 0 \\ 0 & … & 0 & ... & d_{n−1} & a_{n−1} \\ a_{n} & 0 & … & 0 & a_{n−1} & d_{n} \end{matrix} ) . Zeige, daß eine

Faktorisierung A = LL^{T} mit einem Cholesky-Faktor der Form

L = ( \begin{matrix}δ_{1} \\ β_{1} & ... \\ & ... & ... \\ & & β_{n−2} & δ_{n−1} \\ γ_{1} & … & γ_{n−2} & γ_{n−1} & γ_{n} \end{matrix} )

existiert. Finde einen Algorithmus (in Pseudo-Code anzugeben), der die Daten δ_{1}, …, γ_{n} in der

Laufzeit O(n) bestimmt. Anleitung: Partitionierung wie im Beweis von Satz 4.27. (8)

Abgabe: Mittwoch, 7. 1. 98, in den Übungsgruppen

Frohe Weihnachten und einen Guten Rutsch!