Universität des Saarlandes Wintersemester 2000/2001 Fachbereich Mathematik Prof. Dr. A. Arnold / M. Ehrhardt

4. Übungsblatt zur Vorlesung “Praktische Mathematik” (Householder–Verfahren)

\underline{1. Aufgabe} (3 Punkte)

Lösen Sie das folgende Gleichungssystem Ax = b durch QR–Zerlegung mittels Householder– Verfahren, wobei

A = (\begin{matrix}−4 & 5 & 15 \\ 3 & 0 & 20 \\ 0 & 4 & 25 \end{matrix}) , b = (\begin{matrix}47 \\ 71 \\ 80 \end{matrix}) .

\underline{2. Aufgabe} (2 Punkte)

Erläutern Sie anhand des Beispiels x = (x_{1}, ε, 0, …, 0)^{⊤} ∈ R^{n}, x_{1} ≠ 0, ε ≥ 0, warum bei der Ermittlung von

h = \frac{x − σe_{1}}{∥x − σe_{1}∥}_{2}, Hx = (I − 2hh^{⊤})x = σe_{1}

die Wahl σ := − sgn(x_{1}) · ∥x∥_{2} gegenüber der Wahl σ := sgn(x_{1}) · ∥x∥_{2} ausgezeichnet ist.

\underline{3. Aufgabe} (2 Punkte)

Es habe A ∈ ℝ^{n×n} die Spaltenvektoren a_{1}, a_{2},..., a_{n} ∈ ℝ^{n}. Zeigen Sie unter Verwendung der QR–Zerlegung die Hadarmardsche Determinantenabschätzung

|det A| ≤ ∏_{j=1}^{n} ∥a_{j}∥_{2}.

(Hinweis: Man berechne einerseits |det A| unter Verwendung der Identität A = QR. Andererseits gilt a_{j} = ∑_{k=1}^{j} r_{kj}q_{k} mit den Spaltenvektoren q_{1}, q_{2},..., q_{j} von Q.

\underline{4. Aufgabe} (3 Punkte)

Man zeige für eine nichtsinguläre Matrix A ∈ ℝ^{n×n} und Vektoren u, v ∈ ℝ^{n}:

a) Ist v^{⊤}A^{−1}u ≠ −1, so gilt die Sherman–Morrison–Formel

(A + uv^{⊤})^{−1} = A^{−1} − \frac{A^{−1}uv^{⊤}A^{−1}}{1 + v^{⊤}A^{−1}u}.

b) Ist v^{⊤}A^{−1}u = −1, so ist (A + uv^{⊤}) singulär.

Hinweis: Für a) multipliziere man

(A + uv^{⊤})(A^{−1} − \frac{A^{−1}uv^{⊤}A^{−1}}{1 + v^{⊤}A^{−1}u}).

\underline{5. Aufgabe} (Praktische Aufgabe) (5 Punkte)

Schreiben Sie ein Programm, welches eine QR–Zerlegung mittels Householder–Verfahren berechnet. Testen Sie das Programm an dem Gleichungssystem aus der 1. Aufgabe und an den Beispielen der praktischen Aufgabe vom 2. Übungsblatt, d.h. Ax = b = (b_{i}) ∈ ℝ^{n}, wobei

a_{ij} = \frac{1}{i + j − 1}, i, j = 1, …, n,

b_{i} = \frac{1}{n + i − 1}, i = 1, …, n.

Dabei gebe man für n = 50, 100, 200 x_{10·i}, i = 1, 2, 3, …, aus. Lösen Sie für n = 10 das lineare Gleichungssystem Ax = b_{k} ∈ ℝ^{n} mit den rechten Seiten b_{k} = e_{k}, k = 1, …, n, um damit die Inverse von A zu berechnen. Vergleichen Sie Ihr Ergebnis mit der exakten Inversen (siehe 2. Übungsblatt).

Hinweise:

a) Die Benutzer von Scilab können ihre Resultate mit denjenigen vergleichen, die die QR–Zerlegung von Scilab (Aufruf: [Q,R]=qr(A)) liefert. Im Programm kann die Scilab–Routine “householder”, die die Spiegelungsmatrix bereitstellt, verwendet werden.

b) Idealerweise sollte es möglich sein, das System für mehrere rechte Seiten b zu lösen, ohne die QR–Zerlegung zu wiederholen. Zur Ersparnis von Speicherplatz sollte die Matrix A dabei mit den Elementen r_{ij} der oberen Dreiecksmatrix R und den Householder–Vektoren h_{1},...,h_{n−1} überschrieben werden. Dazu werden die Diagonalelemente r_{ii}, i = 1, ..., n − 1 und r_{nn} = a_{nn} in einem besonderen Vektor d gespeichert, so daß die Householder–Vektoren in der unteren Hälfte von A Platz finden.

c) Die nötigen Matrixmultiplikationen der Form

(I − 2hh^{⊤})B = B − hg^{⊤}, g^{⊤} := 2h^{⊤}B

führt man am besten so aus, daß zunächst der Vektor g berechnet und anschließend die Matrix A modifiziert (“aufdatiert”) wird.

Abgabe der Lösungen zu den theoretischen Aufgaben am Di, 21.11. vor der Vorlesung. Abgabe der Lösungen zu der praktischen Aufgabe am Di, 28.11. in den Sprechstunden.