Numerik I Wintersemester 97/98 Dr. Walter Oevel 20. Januar 1998

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

Aufgabe 37: (Implementierung der Wielandt-Rayleigh-Iteration) Berechne die 10 größten Eigenwerte der 1000 × 1000-Matrix

A = ( \begin{matrix}1 & α & 0 & … & 0 \\ α & 2 & α & ... & ⋮ \\ 0 & ... & ... & ... & 0 \\ ⋮ & ... & ... & ... & α \\ 0 & … & 0 & α & 1000 \end{matrix} ) , α = 0.26

auf mindestens 10 Dezimalstellen relativer Genauigkeit:

a) Seien λ_{1} ≤ λ_{2} ≤ … die Eigenwerte. Zeige:

λ_{i} ∈ (i − 0.33, i + 0.33) , i = 1, …, 1000 .  (2)

Anleitung: Betrachte DAD^{−1} mit D = diag(1, …, 1, ϵ, 1, …, 1). Es gibt einen Wertebereich für ϵ, sodaß der Gerschgorin-Kreis um das i.te Diagonalelement von den restlichen Kreisen separiert.

b) Implementiere die inverse Wielandt-Iteration x^{(j+1)} = \frac{(A − μ^{(j)} I 1)^{−1}x^{(j)}}{||(A − μ^{(j)} I 1)^{−1}x^{(j)}||_{2}} mit

Rayleigh-Beschleunigung μ^{(j)} = r_{A}(x^{(j)}). Benutze für den Schritt x^{(j)} → x^{(j+1)} eine QR-Zerlegung von A − μ^{(j)} I 1 gemäß Aufgabe 28 (es existiert eine Musterlösung zu Aufgabe 28 im Web). Zur Bestimmung des Eigenwertes λ_{i} ≈ i (i = 991, …, 1000) führe zunächst einen einzelnen inversen Wielandt-Schritt mit dem Spektralparameter μ = i und x^{(0)} = (1, …, 1)^{T} durch, dann gehe zur beschleunigten Iteration über, bis die gewünschte relative Genauigkeit erreicht ist.

Der (wohlkommentierte) Quelltext ist mit abzugeben, notiere die benötigte Rechenzeit, die in der Größenordnung weniger Sekunden liegen sollte. (15)

Anmerkung: Vorsicht bei der Implementierung der Fehlerabschätzung aus Satz 6.3.b): die Fehlerschranke r_{A^{2}}(x⃗) − r_{A}(x⃗)^{2} ist durch Auslöschung gefährdet! Verwende die Darstellung

r_{A^{2}}(x⃗) − r_{A}(x⃗)^{2} = \frac{⟨y⃗, y⃗⟩}{⟨x⃗, x⃗⟩} , y⃗ = (A − r_{A}(x⃗) I 1) x⃗ .

Diese Programmieraufgabe ist einzeln (nicht in Kleingruppen!) zu bearbeiten. Bei (nicht unabhängig erarbeiteten) Mehrfachlösungen werden die erreichten Punkte verteilt!

Abgabe: Mittwoch, 4. 2., in den Übungsgruppen