Eigenwerte von Matrizen zu berechnen ist ein Problem, das häufig in naturwissenschaftlich-technischen Anwendungen auftritt. In der Theorie kann man mit Hilfe von Eigenwerten unter anderem Aussagen über die Stabilität von dynamischen Systemen machen. Außerdem spielen sie in der Stochastik, z.B. bei Markov-Ketten (Übergangswahrscheinlichkeiten, Brownsche Bewegung), eine wichtige Rolle. Nun einige Beispiele aus praktischen Anwendungen:
- in der Physik bei Schwingungsproblemen
- in der Chemie bei Verbrennungsprozessen
- in der Makroökonomie bei der Überprüfung von Marktstabilität
- in der Biologie bei Populationsmodellen
Die hierbei auftretenden Fragen bzw. Aufgaben sind z.B.: Wie berechnet man
- alle Eigenwerte und/oder alle Eigenvektoren für eine kleine Matrix (bis 10^3*10^3)?
- einen Eigenwert und/oder den zugehörigen Eigenvektor (betragsgrößter, -kleinster, mit größtem Realteil,...)?
- einige wenige Eigenwerte und gegebenenfalls die zugehörigen Eigenvektoren?
- einen Eigenvektor zu einem bekannten Eigenwert (Markov-Ketten)
Bei kleinen Matrizen, das heißt Matrizen der Größenordnung bis etwa 10^3*10^3, können diese mittels Householder-Transformationen auf Hessenberg-Form bzw. im hermiteschen
Fall auf Tridiagonal-Form zurückgeführt werden. Dann kann man z.B. mit der QR-Zerlegung die gewünschten Eigenwerte und/oder die zugehörigen Eigenvektoren berechnen.
In dieser Arbeit sollen Matrizen in der Größenordnung 10^3*10^3 bis 10^6*10^6 betrachtet werden. Da die erwähnten Standard-Algorithmen einen zu hohen Rechen- und Speicheraufwand verursachen, versucht man mittels Projektionsverfahren dieses große Problem auf ein kleines zu reduzieren, um darauf die Standardtechniken wieder anwenden und somit einen Teil des Spektrums approximieren zu können. Diese Arbeit hat die "Konvergenz von Krylov-Verfahren für Eigenwertprobleme" zum Thema.
Konvergenz von Krylov-Verfahren
für Eigenwertprobleme
Diplomarbeit
Vorgelegt von:
Alexander Weiß
Eberhard-Karls-Universität Tübingen
Fakultät für Mathematik
September 1998
Inhaltsverzeichnis
1 Einleitung ... 1
2 Iterationsverfahren ... 3
2.1 Abstand zwischen Unterräumen ... 3
2.2 Konvergenz von Unterraumiterationen ... 12
3 Ritz-Werte ... 21
3.1 Rayleigh-Ritz-Methode ... 21
3.2 Fehlerabschätzungen ... 28
4 Krylov-Methoden ... 39
4.1 Nichthermitesches Lanczos-Verfahren ... 39
4.2 Konvergenz der Eigenpaare ... 41
5 Hermitesche Eigenwertprobleme ... 49
5.1 Courant-Fischer-Theorem ... 49
[...]