Dr. Frank Wübbeling WS 2002/03

Übungen zur Vorlesung Einführung in die Numerische Mathematik

Übungsblatt 3 , Abgabe: 12.11.2002 , 11.00 Uhr

Aufgabe 9: (4 Punkte) Zeigen Sie: Die QR-Zerlegung einer invertierbaren (n × n)–Matrix A ist eindeutig bis auf Multiplikation mit einer Diagonalmatrix mit |D_{ii}| = 1, i = 1 … n, d.h. falls A = QR = Q′R′, so gilt Q = DQ′.

Aufgabe 10: (4 Punkte)

(a) Eine Hessenbergmatrix A erfüllt A_{i,j} = 0 für i > j + 1. Wieviele Rechenoperationen benötigt man für die QR-Zerlegung einer n × m–Matrix nach Householder, n ≥ m?

(b) Eine Alternative zur Householdermethode ist die Givens–Rotation. Sei φ ein Rotationswinkel, c = cos φ und s = sin φ. Dann heißt die unitäre n × n–Matrix G Givens– Rotation um den Winkel φ in der Ebene (i, k), falls G mit der Einheitsmatrix übereinstimmt außer in folgenden Elementen:

G_{i,i} = c, G_{i,k} = s, G_{k,i} = −s, G_{k,k} = c

für ein Paar (i, k) mit 1 ≤ i, k ≤ n. Sei A die Hessenbergmatrix aus (a). Bestimmen Sie φ so, dass für die Givens–Rotation G um den Winkel φ in der (1, 2)-Ebene gilt: GA = B und B hat in der ersten Spalte nur Nullen unterhalb der Hauptdiagonalen. Aufgabe 11: (4 Punkte) Lösen Sie das Gleichungssystem

( \begin{matrix}−1 & 0 & −1 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \end{matrix} ) ( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \end{matrix} ) = ( \begin{matrix}1 \\ −3 \\ 0 \end{matrix} )

mit Hilfe der QR-Zerlegung. Geben Sie die Matrizen Q und R und alle Rechenschritte explizit an.

Aufgabe 12: (4 Punkte) Schreiben Sie eine Prozedur qr, die die QR–Zerlegung einer n × m–Matrix, n ≥ m, berechnet. Ihr Programm sollte die Matrix R und die Vektoren v_{k}, k = 1 … m, berechnen. Schreiben Sie weiter eine Prozedur qmalx, die Q auf einen Vektor anwendet (wie in der Vorlesung), und eine Prozedur qtmalx, die Q^{t} auf einen Vektor anwendet. Testen Sie ihr Programm für die Matrix n×m–Matrix A, A_{i,k} = 1/(i+k−1), n = 100, 200, m = 50, 100. Wenden Sie zum Test Ihr Programm qmalx auf die einzelnen Spalten der Matrix R an und geben Sie die Norm von QR − A aus.