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

6. Übungsblatt zur VL “Numerik für Informatiker” (Iterative Lösung linearer und nichtlinearer Gleichungssysteme)

\underline{1. Aufgabe} (7 Punkte)

Sei A = [\begin{matrix}9 & 1 & −1 & −1 \\ 3 & 10 & −1 & 2 \\ 2 & −4 & 9 & 1 \\ 3 & −3 & 4 & 11 \end{matrix}] , b = [\begin{matrix}8 \\ 14 \\ 8 \\ 15 \end{matrix}] , x^{(0)} = [\begin{matrix}0 \\ 0 \\ 0 \\ 0 \end{matrix}] .

a) Gebe die exakte Lösung x an.

b) Berechne die ersten 4 Iterierten x^{(1)}, x^{(2)}, x^{(3)}, x^{(4)} der Jacobi-Iteration für Ax = b.

c) Berechne die 1-Norm und die ∞-Norm der Iterationsmatrix des Jacobi-Verfahrens.

d) Berechne die ersten 4 Iterierten x^{(1)}, x^{(2)}, x^{(3)}, x^{(4)} der Gauß-Seidel-Iteration für Ax = b.

e) Berechne die 1-Norm und die ∞-Norm der Iterationsmatrix des Gauß-Seidel-Verfahrens. Hinweise: Bei a) braucht die Lösung nur hingeschrieben werden; bei b) und d) soll mindestens der Vektor x^{(1)} per Hand ausgerechnet werden. Die restlichen Iterierten können auch per Rechner berechnet werden. Eine Iteration beinhaltet einen Update jeder Variablen. Das Jacobi- und das Gauß-Seidel-Verfahren kann man als Fixpunktiteration x^{(i+1)} = F (x^{(i)}) = Bx^{(i)} + b auffassen. Die Matrix B heisst Iterationsmatrix. In MATLAB sind die Befehle diag, triu, tril, \ für diese Aufgabe hilfreich.

\underline{2. Aufgabe} (2 Punkte)

Gegeben: A, b wie in der 1. Aufgabe. Die 2-Norm der Iterationsmatrix des Jacobi-Verfahrens beträgt 0.705. Folgende Werte wurden ausgehend von x^{(0)} berechnet:

x^{(0)} = [\begin{matrix}10 \\ 10 \\ 10 \\ 10 \end{matrix}] , x^{(1)} = [\begin{matrix}2.0000 \\ −2.6000 \\ 2.0000 \\ −2.2727 \end{matrix}] , x^{(2)} = [\begin{matrix}1.1475 \\ 1.4545 \\ −0.4586 \\ −0.6182 \end{matrix}] , x^{(3)} = [\begin{matrix}0.6076 \\ 1.1335 \\ 1.3490 \\ 1.6141 \end{matrix}] , x^{(4)} = [\begin{matrix}1.0922 \\ 1.0298 \\ 1.0783 \\ 1.0165 \end{matrix}]

Gebe mit Hilfe dieser Daten eine a-priori und eine a-posteriori Schranke für den Fehler ∥x^{(4)} − x∥_{2} von x^{(4)} an.

\underline{3. Aufgabe} (3 Punkte)

Wie viele Flops braucht eine Iteration des Gauß-Seidel- und des Jacobi-Verfahrens? Hinweis: Gesucht sind nur die Ordnung p und die führende Konstante c, also ein Ausdruck der Form cn^{p} + O(n^{p−1}). Mit Begründung.

\underline{4. Aufgabe} (5 Punkte)

Sei f(x_{1}, x_{2}) = [\begin{matrix}sin(x_{1}) + 2x_{1}x_{2} \\ x_{1}^{2} + x_{2}^{2} − 1 \end{matrix}].

a) Berechne die Jacobimatrix J von f, also eine Matrix voller Funktionen mit J_{ij} = \frac{∂f_{i}}{∂x_{j}}.

b) Berechne die ersten 4 Iterierten x^{(1)}, x^{(2)}, x^{(3)}, x^{(4)} des Newton-Verfahrens mit Start-

wert x^{(0)} = [\begin{matrix}−3 \\ −2 \end{matrix}] für das Nullstellenproblem f(x_{1}, x_{2}) = 0.

Hinweis: Aufgabe a) soll per Hand gemacht werden. Bei Aufgabe b) hätte ich gerne die Berechnungsvorschrift gesehen. Die eigentlichen Vektoren können per Programm berechnet werden.

\underline{5. Aufgabe} (3 Punkte)

Wahr oder falsch (ohne Begründung; Antwort richtig: 0.5 Punkte, falsch: −0.5 Punkte) Sei B die Iterationsmatrix des Jacobi-Verfahrens.

a) Das Jacobi-Verfahren konvergiert für jede Matrix und jeden Startwert.

b) Wenn die 1-Norm von B kleiner als 1 ist, dann konvergiert das Jacobi-Verfahren.

c) Wenn die ∞-Norm von B kleiner als 1 ist, dann konvergiert das Jacobi-Verfahren.

d) Wenn die 1-Norm und die ∞-Norm von B kleiner als 1 sind, dann konvergiert das Jacobi-Verfahren.

e) Wenn die 1-Norm kleiner als 1 ist und die ∞-Norm von B größer als 1 sind, dann konvergiert das Jacobi-Verfahren.

f) Wenn die ∞-Norm kleiner als 1 ist und die 1-Norm von B größer als 1 sind, dann konvergiert das Jacobi-Verfahren.

Abgabe - in der Vorlesung am 30. November oder

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

Besprechung im Tutorium am 3. Dezember