Prof. Dr. F. Natterer WS 2001/02

Übungen zur Vorlesung Einführung in die Numerische Mathematik

Übungsblatt 4 , Abgabe: 16.11.2001 , 13.00 Uhr, Übungskasten F17, F25, F29

Die Programmieraufgabe 16 darf eine Woche später abgegeben werden.

Aufgabe 13: (4 Punkte) Zeigen Sie:

∥A∥_{2} = ρ(A^{∗}A)^{1/2}, ∥A∥_{1} = \begin{matrix}Max \\ j \end{matrix} ∑_{i} |a_{ij}|

Aufgabe 14: (4 Punkte)

a) Sei A hermitesche, invertierbare (n, n)-Matrix.

Seien λ_{max}, λ_{min} der betragsgrößte bzw. betragskleinste Eigenwert von A. Zeigen Sie:

k_{2}(A) = \frac{|λ_{max}|}{|λ_{min}|} .

b) Es sei bekannt, daß in der Gleichung

Ax = b , A = ( \begin{matrix}4 & 1 \\ 1 & 4 \end{matrix} ) , b = ( \begin{matrix}5 \\ 5 \end{matrix} ) ,

A und b in der ∥ · ∥_{2}-Norm jeweils einen maximalen relativen Fehler von 0.05 aufweisen. Welche relative Genauigkeit können Sie für x garantieren?

Aufgabe 15: (4 Punkte) Sei A eine reelle (n, n)-Matrix.

(a) Zeigen Sie, daß die QR-Zerlegung von A nach Householder \frac{2}{3}n^{3} + O(n^{2}) Rechenoperationen erfordert.

(b) Sei A eine Hessenberg-Matrix, d.h. a_{i,j} = 0 für i > j+1. Wieviele Rechenoperationen braucht die QR - Zerlegung von A nach Householder?

(Angabe an^{b} + O(n^{b−1}) genügt).

Zeigen Sie, daß auch Q Hessenbergform hat.

Aufgabe 16: (Programmieraufgabe, 4 Punkte) Schreiben Sie ein Programm qrdcmp (a, d, n, m) zur QR−Zerlegung nach Householder. Die (n, m)−Matrix a enthält bei Aufruf die zu zerlegende Matrix (n ≥ m). Der Faktor R finde sich nach Ablauf des Programms oberhalb der Diagonalen von a und in dem m−Vektor d. Auf und unterhalb der Diagonalen von a befinden sich die Vektoren der Spiegelungen. Schreiben Sie weiter die Programme

qmalx (a, x, n, m) , qtmalx (a, x, n, m) ,

welche - nach Aufruf von qrdcmp (a, d, n, m) - den n−Vektor x mit Qx bzw. Q^{∗}x überschreiben.