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

4. Übungsblatt zur VL “Numerik für Informatiker” (Numerik linearer Gleichungssysteme: LR-Zerlegung und Cholesky-Verfahren)

\underline{1. Aufgabe} (3 Punkte)

A = (\begin{matrix}1 & 5 & 6 \\ 1 & 3 & 3 \\ 2 & 4 & 6 \end{matrix}) , b = (\begin{matrix}19 \\ 12 \\ 20 \end{matrix})

a) Bestimme die Lösung des Gleichungssystems Ax = b mit Hilfe des Gaußalgorithmus mit Spaltenpivotisierung.

b) Gebe eine Permutationsmatrix P und eine LR-Zerlegung der Matrix P A an, in der alle Nichtdiagonalelemente von L kleiner oder gleich 1 sind.

\underline{2. Aufgabe} (5 Punkte)

Führe alle Rechnungen in dieser Aufgabe in 4-stelliger Genauigkeit durch.

Ax = b, mit A = (\begin{matrix}−10^{−5} & 10^{5} \\ 1 & 2 · 10^{5} \end{matrix}) , b = (\begin{matrix}1 \\ 0 \end{matrix})

Bestimme die Lösung des Gleichungssystems Ax = b mit Hilfe des Gaußalgorithmus a) ohne Pivotisierung, b) mit Spaltenpivotisierung, c) mit vollständiger Pivotisierung. Hinweis: Der Gaußalgorithmus mit vollständiger Pivotisierung wählt als Pivotelement im i-ten Schritt des betragsgrößte Element aus der Supmatrix, die aus den Zeilen und Spalten i bis n besteht. Bei Bedarf wird der Gaußalgorithmus mit vollständiger Pivotisierung im Tutorium am 12. November vorgeführt.

\underline{3. Aufgabe} (3 Punkte)

Ein Flop (Abk. von floating point operation) ist eine Gleitpunktzahloperation (Addition, Multiplikation, Vergleich von zwei Gleitpunktzahlen, Integer zählen nicht). Wieviele Flops benötigt der Gaußalgorithmus mit vollständiger Pivotisierung für eine n×n Matrix, wenn er durchführbar ist?

\underline{4. Aufgabe} (4 Punkte)

Prüfen Sie folgende Matrizen auf positive Definitheit und geben Sie ggf. die Cholesky-Zerlegung an.

A = (\begin{matrix}4 & 6 & −6 & −8 \\ 6 & 58 & −23 & 44 \\ −6 & −23 & 17 & −12 \\ −8 & 44 & −12 & 95 \end{matrix}) , B = (\begin{matrix}4 & −2 & −2 & 2 \\ −2 & 17 & 9 & −9 \\ −2 & 9 & 6 & −5 \\ 2 & −9 & −5 & 6 \end{matrix})

\underline{5. Aufgabe} (5 Punkte) Wahr oder falsch (ohne Begründung; Antwort richtig: 0.5 Punkt, falsch: −0.5 Punkt)

a) Der Gaußalgorithmus führt immer auf eine obere Dreiecksmatrix, in der alle Diagonalelemente positiv sind.

b) Der Gaußalgorithmus führt immer auf eine obere Dreiecksmatrix, in der alle Diagonalelemente ungleich Null sind. Wenn der Gaußalgorithmus für ein Gleichungssystem Ax = b durchführbar ist, dann auch für

c) Âx = b, wobei Â durch Vertauschen der Spalten aus A entsteht.

d) Ãx = b̃, wobei Ã und b̃ durch Vertauschen der Zeilen aus A und b entstehen.

e) Ax = c, wobei c = b + b̃ (mit b̃ aus Aufgabe d) ).

f) A^{⊤}x = d, wobei A^{⊤} die Transponierte von A ist.

g) Falls für eine Matrix A eine links-untere Dreicksmatrix L existiert, so daß A = LL^{⊤}, ist A positiv definit.

h) Falls für eine Matrix A eine links-untere Dreicksmatrix L existiert, so daß A = L^{⊤}L, ist A positiv definit.

i) Damit A = L^{⊤}L positiv definit ist, muß L eine untere Dreiecksmatrix ohne Nullen auf der Diagonalen sein.

j) Damit A = R^{⊤}R positiv definit ist, muß R eine obere Dreiecksmatrix mit positiven Diagonalelementen sein.

Abgabe - in der Vorlesung am 16. November oder

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

Besprechung im Tutorium am 19. November