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

10. Übungsblatt zur Vorlesung “Praktische Mathematik” (QR–Algorithmus, Singulärwertzerlegung)

\underline{1. Aufgabe} (3 Punkte (1.5+1.5))

Sei A ∈ ℝ^{n×n} eine diagonalisierbare Matrix.

a) In welchem Zusammenhang stehen beim QR–Algorithmus

A_{0} := A , A_{k} = Q_{k}R_{k} , A_{k+1} = R_{k}Q_{k} , k = 0, 1, 2, …

die Eigenvektoren der A_{k} zu denen von A?

b) Zeigen Sie, daß der QR–Algorithmus die Hessenbergstruktur einer Matrix erhält.

\underline{2. Aufgabe} (2 Punkte (0.5+1.5))

Von der Matrix

A = (\begin{matrix}1 & \frac{1}{2} & 0 \\ \frac{1}{2} & −1 & −\frac{1}{2} \\ 0 & −\frac{1}{2} & \frac{5}{2} \end{matrix} )

soll der mittlere Eigenwert und ein dazugehöriger Eigenvektor näherungsweise bestimmt werden.

a) Schätzen Sie die Lage der Eigenwerte mit Hilfe des Satzes von Gerschgorin ab.

b) Bestimmen Sie einen Eigenvektor zum mittleren Eigenwert durch 2 Schritte einer geeigneten Vektoriteration, ausgehend vom Startwert (1, 0, 0)^{⊤}, und eine Näherung an den gesuchten Eigenwert mit Hilfe des Rayleigh–Quotienten

R[x_{1}] = \frac{x_{1}^{⊤}x_{2}}{x_{1}^{⊤}x_{1}} .

\underline{3. Aufgabe} (2 Punkte)

Berechnen Sie eine Singulärwertzerlegung von

A = (\begin{matrix}10 & 5 & −10 \\ 2 & −11 & 10 \end{matrix}) .

Tip: Die Ergebnisse können mit Scilab (Aufruf: ‘[U,Sigma,V]=svd(A)’) geprüft werden.

\underline{4. Aufgabe} (3 Punkte (1+2))

Ein Iterationsverfahren zur Bestimmung einer Minimum–Norm–Lösung von Ax = b mit x ∈ ℝ^{n}, b ∈ ℝ^{k}, A ∈ ℝ^{k×n} ist das Landweberverfahren

x_{0} := 0 , x_{m+1} := x_{m} + β A^{⊤}(b − Ax_{m}) , β ∈ ℝ .

a) Zeigen Sie:

x_{m} = β ∑_{j=0}^{m−1}(I − βA^{⊤}A)^{j}A^{⊤}b für alle m ∈ ℕ .

b) Bestimmen Sie eine Funktion F (m, σ), so daß gilt:

x_{m} = ∑_{σ_{ℓ}>0} F (m, σ_{ℓ}) σ_{ℓ}^{−1} b^{⊤}u_{ℓ} v_{ℓ} .

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

Schreiben Sie ein Programm, das mit Hilfe des QR–Algorithmus die Eigenwerte einer reellen symmetrischen n × n–Matrix berechnet. Eine Routine soll die Matrix mittels Householder–Reflexionen auf Tridiagonalgestalt transformieren. Wenden Sie auf diese Tridiagonalmatrix das QR–Verfahren an. Die notwendigen QR–Zerlegungen sollen mittels geeigneten Givens–Rotationen durchgeführt werden. Das Verfahren soll abbrechen, sobald die Nebendiagonalelemente der Iterierten kleiner als 10^{−6} sind. Testen Sie Ihr Programm an der Matrix aus der 2. Aufgabe vom 9. Übungsblatt. Berechnen Sie mit Ihrem Programm die Eigenwerte der Hilbertmatrix A = (a_{ij}) mit

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

für n = 5, 10, 15, 20, 25, 30.

Hinweis:

Die Benutzer von Scilab können ihre Resultate mit denjenigen vergleichen, die die Eigenwertroutine von Scilab (Aufruf: ‘spec(A)’) liefert. Außerdem kann die Scilab– Routine für die Berechnung der Givens–Rotationen (‘givens’) verwendet werden.

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