Technische Universität Berlin Wintersemester 07/08 Fakultät II – Institut für Mathematik PD Dr. M. Ehrhardt Dipl.–Ing. C. Schröder

5. Übungsblatt zur VL “Numerik für Informatiker”

(Numerische Lösung linearer Gleichungssysteme: Householder-Transformation und QR-Zerlegung)

\underline{1. Aufgabe} (4 Punkte)

a) Es seien eine n×n Matrix A sowie ihre LR-Faktoren L (untere Dreiecksmatrix, Einsen auf der Diagonale) und R (obere Dreiecksmatrix, keine Null auf der Diagonale) gegeben. Entwerfen Sie einen Algorithmus, der die LR-Zerlegung von A^{⊤} in O(n^{2}) Flops berechnet. (Gefragt ist Code einer konkreten Programmiersprache oder Pseudocode.) Hinweis: Input der Routine sind L und R (und n). Output sind L̃ und R̃, die LR-Faktoren von A^{⊤}.

b) Finde eine LR-Zerlegung von A^{⊤}, wobei

A := LR, L := [\begin{matrix}1 & 0 & 0 & 0 \\ −1 & 1 & 0 & 0 \\ 1 & −1 & 1 & 0 \\ −1 & 1 & −1 & 1 \end{matrix}] , R := [\begin{matrix}1 & 2 & 3 & 4 \\ 0 & 2 & 3 & 4 \\ 0 & 0 & 3 & 4 \\ 0 & 0 & 0 & 4 \end{matrix}] .

\underline{2. Aufgabe} (3 Punkte)

a) Beweisen Sie, daß es zu jedem Vektor v ∈ ℝ^{n} eine Zahl τ gibt, so daß die Matrix H = I − τvv^{⊤} orthogonal ist. Hinweis: v^{⊤}v = ∥v∥_{2}^{2}.

b) Geben Sie so eine Zahl τ für folgende Vektoren an:

v_{1} = [\begin{matrix}1 \\ 2 \\ 3 \\ 4 \end{matrix}] , v_{2} = [\begin{matrix}π \\ π^{2} \\ 1 \\ 0 \\ −1 \end{matrix}] , v_{3} = [\begin{matrix}0 \\ 0 \\ 0 \end{matrix}] , v_{4} = [1 1 ⋮ 1] ∈ ℝ^{n}

\underline{3. Aufgabe} (4 Punkte)

a) Gegeben sind 2 Vektoren x, y ∈ ℝ^{n} gleicher 2-Norm. Finde einen Vektor v und eine Zahl τ, so daß (I − τvv^{⊤})x = y.

b) Geben Sie solche v und τ für folgende x, y an:

[x_{1}, y_{1}] = [\begin{matrix}1 & 4 \\ 2 & 3 \\ 3 & 2 \\ 4 & 1 \end{matrix}] , [x_{2}, y_{2}] = [\begin{matrix}1 & \sqrt{30} \\ 2 & 0 \\ 3 & 0 \\ 4 & 0 \end{matrix}] , [x_{3}, y_{3}] = [\begin{matrix}1 & −\sqrt{30} \\ 2 & 0 \\ 3 & 0 \\ 4 & 0 \end{matrix}] , [x_{4}, y_{4}] = [\begin{matrix}1 & −1 \\ 2 & −2 \\ 3 & −3 \\ 4 & −4 \end{matrix}]

\underline{4. Aufgabe} (5 Punkte)

a) Berechnen Sie die 1-, 2- und ∞-Normen der Vektoren v_{1}, v_{3} und v_{4} der 2. Aufgabe!

b) Berechnen Sie die 1- und ∞-Normen sowie die jeweiligen Konditionszahlen der Matrizen L und R der 1. Aufgabe! (Hier ist nach 8 Zahlen gefragt.)

\underline{5. Aufgabe} (4 Punkte)

Wahr oder falsch (ohne Begründung; Antwort richtig: 0.5 Punkte, falsch: −0.5 Punkte)

a) Für jede 2 Vektoren x, y ∈ ℝ^{n} gibt es eine Householdermatrix H, so daß Hx = y.

b) Für jede 2 Vektoren x, y ∈ ℝ^{n} gibt es eine Householdermatrix H und eine Zahl α ∈ ℝ, so daß Hx = αy.

c) Für jede 2 Vektoren x, y ∈ ℝ^{n} gibt es eine Householdermatrix H und eine Zahl α > 0, so daß Hx = αy.

Falls A = QR eine QR-Zerlegung der invertierbaren Matrix A ist, dann

d) ist QR^{T} eine QR-Zerlegung von A^{T}.

e) ist QR^{−1} eine QR-Zerlegung von A^{−1}.

f) ist QR^{−T} eine QR-Zerlegung von A^{−T}.

g) Wenn Q orthogonal ist, dann ist Q^{T} Q = QQ^{T}.

h) Wenn Q^{T} Q = QQ^{T}, dann ist Q orthogonal.

\underline{Praktische Aufgabe} (10 Punkte)

Implementieren Sie die QR-Zerlegung in folgenden Schritten.

a) Schreiben Sie eine Routine house, die einen Vektor x als Parameter bekommt, und einen Vektor v und ein Skalar τ berechnet, so daß v(1) = 1, (I − τvv^{⊤}) eine orthogonale Matrix ist und (I − τvv^{⊤})x ein Vielfaches des ersten Einheitsvektors.

b) Schreiben Sie eine Routine apply house, die ein Skalar τ und Vektoren v und y als Parameter bekommt, und z = (I − τvv^{⊤})y berechnet. Sie können annehmen, daß v(1) = 1. Konzipieren Sie die Routine so, daß sie ohne lokale Arrays auskommt. Bilden Sie insbesondere nicht die Matrix (I − τvv^{⊤}).

c) Schreiben Sie eine Routine qr inplace, die eine n × n Matrix A bekommt und eine gleichgroße Matrix B und einen Vektor t zurückliefert, so daß der obere dreieckige Teil von B der oberen Dreiecksmatrix R der QR-Zerlegung von A entspricht. Die Spalten von B unterhalb der Diagonalen enthalten die Householdervektoren v. Der Vektor t enthält die Skalare τ.

d) Schreiben Sie eine Routine lgs solve qr, die eine n × n Matrix A und einen Vektor b bekommt und die Lösung x des Gleichungssystems Ax = b mittels QR-Zerlegung berechnet.

e) Schreiben Sie eine Routine qr generate, die eine Matrix B und einen Vektor t, wie in c) berechnet, bekommt und die orthogonale Matrix Q der QR-Zerlegung ausgibt. Für diese Aufgabe eignen sich Sprachen wie C oder Matlab gut.

Abgabe - in der Vorlesung am 23. November oder

- vorher im Briefkasten zwischen den Räumen MA470, MA471

Besprechung im Tutorium am 26. November