Numerik I Wintersemester 97/98 Dr. Walter Oevel 9. 12. 1997

Ü b u n g s b l a t t 7

Aufgabe 22: (Zu Dreiecksmatrizen) Es sei L eine invertierbare untere n × n-Dreiecksmatrix, B sei eine beliebige n × m-Matrix. Es soll X = L^{−1}B bestimmt werden.

a) L^{−1} sei nicht bekannt. Mit wievielen Additionen kann X per Rücksubstitution

berechnet werden? Anleitung: berechne X = (x⃗_{1}, …, x⃗_{m}) spaltenweise. (2)

b) L^{−1} sei bekannt. Wieviele Additionen braucht die Matrixmultiplikation L^{−1}B? (2)

Sei L = ( \begin{matrix}1 & & & 0 \\ −1 & ... \\ & ... & ... \\ 0 & & −1 & 1 \end{matrix} ).

c) Beantworte a) für dieses L. (2)

d) Bestimme L^{−1} (exakt). Beantworte b) für dieses L. (2)

Man sieht: die Benutzung der Inversen L^{−1} ist nicht nur überflüssig (vergleiche a) und b)), sondern kann sogar schädlich sein (vergleiche c) und d)).

Aufgabe 23: (LR-Faktorisierung ohne Zeilenvertauschung) Eine n × n-Matrix A = (a_{ij}) heißt (stark) diagonaldominant, wenn in jeder Zeile das

Diagonalelement im Sinne von |a_{ii}| > ∑_{{j=1 \atop j≠i}}^{n} |a_{ij}| (i = 1, …, n) dominiert.

a) Zeige, daß diagonaldominante Matrizen eine LR-Faktorisierung A = LR ohne Zeilenvertauschung zulassen. Zeige, daß solche Matrizen automatisch invertierbar sind. (4)

Anleitung: nach dem ersten Schritt des Gauß-Verfahrens sei die Matrix auf die Form

( \begin{matrix}a_{11} & a_{12} & … & a_{1n} \\ 0 & a′_{22} & … & a′_{2n} \\ ⋮ & ⋮ & ... & ⋮ \\ 0 & a′_{n2} & … & a′_{nn} \end{matrix} ) , a′_{ij} = a_{ij} − \frac{a_{i1}a_{1j}}{a_{11}} , i, j = 2, …, n

gebracht. Zeige, daß der (n − 1) × (n − 1)-Block (a′_{ij}) wieder diagonaldominant ist.

b) In der obigen Definition der Diagonaldominanz wird die Ungleichung > durch ≥ ersetzt. Ist bei zusätzlich vorausgesetzter Invertierbarkeit eine Faktorisierung A = LR ohne Zeilenvertauschung garantiert? (1)

Aufgabe 24: (LR-Faktorisierung von Bandmatrizen)

Das n × n-Gleichungssystem ( \begin{matrix}2 & −1 & & 0 \\ −1 & ... & ... \\ & ... & ... & −1 \\ 0 & & −1 & 2 \end{matrix} ) ( x_{1} ; ⋮ ; ⋮ ; x_{n} ) = ( b_{1} ; ⋮ ; ⋮ ; b_{n} ) ist zu lösen.

a) Finde die (exakten) Daten der LR-Zerlegung A = LR. (3)

Anleitung: die die Bänder von L und R definierende Rekursion ist leicht lösbar.

b) Berechne (exakt) den Lösungsvektor x⃗ für b⃗ = (1, …, 1)^{T} . (3)

Anleitung: die Rekursionen der Rücksubstitutionen sind für dieses b⃗ leicht lösbar.

c) Berechne numerisch die Komponente x_{10 000} für b⃗ = (sin(1), sin(2), …, sin(n))^{T}, n = 500 000. (3)

Welcher Speicherplatzbedarf fällt an? Notiere die Laufzeit, Quelltext des Programmes mitabgeben!

Achtung! Das Gleichungssystem ist schlecht konditioniert, relative Rundungsfehler werden um Faktoren der Größenordnung n^{2} verstärkt!

Abgabe: Mittwoch, 17. 12., in den Übungsgruppen (alternativ: in der Vorlesung oder in meinem Büro D1.329)