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

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

Aufgabe 28: (QR-Zerlegung von 3-Band-Matrizen, technische Durchführung)

Sei A = ( \begin{matrix}β_{1} & γ_{1} & & 0 \\ α_{1} & ... & ... \\ & ... & ... & γ_{n−1} \\ 0 & & α_{n−1} & β_{n} \end{matrix} ).

a) Zeige induktiv

H^{(j−1)} ⋯ H^{(1)}A = ( \begin{matrix}u_{1} & v_{1} & w_{1} \\ & ... & ... & ... \\ & & ... & ... & ... \\ & & & u_{j−1} & v_{j−1} & w_{j−1} \\ & & & & β̃_{j} & γ̃_{j} & 0 \\ & & & & α_{j} & β_{j+1} & γ_{j+1} \\ & & & & 0 & α_{j+1} & β_{j+2} & γ_{j+2} \\ & & & & & & ... & ... & ... \end{matrix} ) ,

wobei rekursiv

H^{(j)} = ( I 1 ; c_{j} s_{j} ; s_{j} −c_{j} ; I 1 )\begin{matrix}← j \\ ← j + 1 \end{matrix} mit \begin{matrix}c_{j} = β̃_{j} / \sqrt{β̃_{j}^{2} + α_{j}^{2}} \\ s_{j} = α_{j} / \sqrt{β̃_{j}^{2} + α_{j}^{2}} \end{matrix}

(bzw. c_{j} = 1, s_{j} = 0 für α_{j} = 0) gewählt wird. Gestartet wird mit β̃_{1} := β_{1}, γ̃_{1} := γ_{1}. (4)

Anleitung: H^{(j)} wirkt nur auf die Zeilen j und j + 1 des Schemas.

Zeige, daß H^{(j)} orthogonal ist. (1)

Anmerkung: es braucht nicht verifiziert zu werden, daß H^{(j)} der Householder-Konstruktion aus der Vorlesung entspricht (was –bis auf Vorzeichen– in der Tat der Fall ist).

b) Leite aus a) eine Rekursion zur Berechnung der 3 Bänder von

R = H^{(n−1)} ⋯ H^{(1)}A = ( \begin{matrix}u_{1} & v_{1} & w_{1} & & 0 \\ & ... & ... & ... \\ & & ... & ... & w_{n−2} \\ & & & ... & v_{n−1} \\ 0 & & & & u_{n} \end{matrix} )

her. Benutze dabei die Daten c_{j}, s_{j} der Matrizen H^{(j)}. Mit welchem Aufwand wird R ermittelt? Implementiere die Rekursion und gebe diese Daten für (α_{i}) = (−3, −2, …, 5), (β_{i}) = (1, 2, …, 10), (γ_{i}) = (1, 2, …, 9) an. (5)

c) Die Daten c_{j}, s_{j} der Householder-Matrizen aus a) liegen vor. Wie und mit welchem Aufwand berechnet sich die Transformation Q^{T} b⃗ = H^{(n−1)} ⋯ H^{(1)}b⃗ eines beliebigen Vektors b⃗ ? (2)

d) Zeige Q^{T} = H^{(n−1)} ⋯ H^{(1)} = ( \begin{matrix}∗ & ∗ & & 0 \\ ⋮ & ... & ... \\ ⋮ & ... & ... & ∗ \\ ∗ & … & … & ∗ \end{matrix} ). (1)

Anleitung: H^{(j−1)} ⋯ H^{(1)} = ( ∗ ∗ ; ⋮ ... ... ; ∗ … ∗ ∗ 0 ; ∗ … ∗ ∗ 0 ; 0 … 0 0 1 ; I 1 )← j

Aufgabe 29: (Zu Matrixnormen und Konditionszahlen)

a) Zeige ||A||_{1} = max_{x⃗≠0} \begin{matrix}||Ax|| & 1 \\ ||x|| & 1 \end{matrix} = max_{j=1...n} ∑_{i=1}^{n} |a_{ij}| . (2)

Anleitung: ein Vektor x⃗, für den das Maximum angenommen wird, läßt sich explizit angeben.

b) Zeige ||A||_{2} = ||A^{T} ||_{2} und folgere cond_{2}(A) = cond_{2}(A^{T}). (1)

Anleitung: setze A als invertierbar voraus. Für singuläre Matrizen: Stetigkeit der Norm.

c) Für die invertierbare 4 × 4-Matrix A gelte A ( \begin{matrix}1 \\ 1 \\ 0 \\ 2 \end{matrix} ) = ( \begin{matrix}0 \\ 1 \\ 7 \\ 4 \end{matrix} ) , A ( \begin{matrix}3 \\ 4 \\ 0 \\ 1 \end{matrix} ) = ( \begin{matrix}5 \\ 4 \\ 5 \\ 0 \end{matrix} ) . Zeige: cond_{∞}(A) ≥ 2.8 . (1)

Abgabe: Mittwoch, 14.1.98, in den Übungsgruppen