Numerische Berechnung von Eigenwerten

Verfahren für einen Eigenwert oder das vollständige Spektrum

Ein Eigenpaar einer quadratischen Matrix $A$ erfüllt

Av=\lambda v,\qquad v\ne0

Bei einer kleinen symbolischen Matrix kann man $\det(A-\lambda I)=0$ lösen. Numerische Software $bildet das charakteristische Polynom meist nicht$ , weil seine Koeffizienten empfindlich auf Rundung reagieren können. Wird nur ein Teil des Spektrums einer großen dünn besetzten Matrix benötigt, verwenden Krylow-Verfahren Matrix-Vektor-Produkte, ohne dieses Polynom zu bilden. Algorithmen für das vollständige Spektrum einer dichten Matrix arbeiten stattdessen mit Matrixfaktorisierungen.

Der benötigte Teil des Spektrums und die Matrixstruktur bestimmen das passende Verfahren:

Die Potenziteration schätzt einen Eigenwert mit größtem Betrag.
Die verschobene inverse Iteration zielt auf einen Eigenwert nahe einer gewählten Verschiebung.
Der $\mathrm{QR}$ -Algorithmus berechnet das vollständige Spektrum einer dichten Matrix.
Lanczos- und Arnoldi-Verfahren zielen auf einen kleinen Teil des Spektrums einer großen dünn besetzten Matrix.

Potenziteration

Die folgenden Formeln verwenden reelle Matrizen und Iterierte. Bei komplexen Iterierten ersetzt du die Transponierte im Rayleigh-Quotienten durch die konjugiert Transponierte. Für $z_k=0$ ist keine Normierung möglich. Prüfe, ob der vorherige Vektor ein Eigenvektor zum Eigenwert null ist.

Wähle einen von null verschiedenen Startvektor $q_0$ und normiere ihn. Wiederhole

z_k=Aq_{k-1}

Der Skalar $\mu_k$ ist der Rayleigh-Quotient. Für eine diagonalisierbare Matrix mit $eindeutig größtem Betrag$ ,

|\lambda_1|>|\lambda_2|\ge\cdots\ge|\lambda_n|

Wenn die angezeigte Ungleichung gilt und der Startvektor eine von null verschiedene Komponente in dominanter Eigenrichtung hat, nähert sich $q_k$ dieser Richtung. Der asymptotische Fehler schrumpft üblicherweise proportional zu

\left|\frac{\lambda_2}{\lambda_1}\right|^k

Daraus folgen zwei mögliche Fehlerfälle. Gleiche dominante Beträge können die Konvergenz zu einem einzelnen Vektor verhindern. Ein Koeffizient null in dominanter Richtung der Eigenbasis verhindert die Konvergenz zu dieser Richtung. Bei symmetrischen Matrizen entspricht dies der Orthogonalität zum dominanten Eigenvektor. Bei nichtnormalen Matrizen muss der Koeffizient in der möglicherweise nichtorthogonalen Eigenbasis geprüft werden.

Mit dem Residuum abbrechen

Brich erst ab, nachdem du das Eigenpaarresiduum geprüft hast. Ähnliche aufeinanderfolgende Eigenwertschätzungen reichen dafür nicht aus:

r_k=Aq_k-\mu_kq_k

Eine skalierungsbewusste Bedingung lautet

\|r_k\|_2\le \tau\bigl(\|A\|_2+|\mu_k|\bigr)

Dabei ist $\tau$ die geforderte Toleranz. Ein kleines Residuum bestätigt, dass $das berechnete Paar die Eigenwertgleichung annähernd erfüllt$ . Welcher benachbarte Eigenwert gefunden wurde, muss getrennt geprüft werden.

Beispiel zur Potenziteration

Betrachte

A=\begin{pmatrix}2&1\\1&2\end{pmatrix}

Der erste Schritt ergibt

z_1=Aq_0=\begin{pmatrix}2\\1\end{pmatrix}

Der zweite Schritt ergibt

q_2=\frac{1}{\sqrt{41}}\begin{pmatrix}5\\4\end{pmatrix}

Die Iterierten nähern sich

q_*=\frac{1}{\sqrt2}\begin{pmatrix}1\\1\end{pmatrix},\qquad \lambda_*=3

Der andere Eigenwert ist $1$ . Der erwartete $Konvergenzfaktor$ beträgt daher $|1/3|$ pro Iteration, sobald der asymptotische Bereich erreicht ist.

Iteration	Rayleigh-Schätzung	Residuumsnorm
1	$14/5$	$3/5$
2	$122/41$	$9/41$

Verschobene inverse

Wähle eine Verschiebung, die $kein Eigenwert$ ist. Die Konvergenz zu einer Eigenrichtung verlangt einen eindeutig nächsten Eigenwert und einen Startkoeffizienten ungleich null in seiner Eigenbasisrichtung. Gleiche Abstände können die Konvergenz zu einer Richtung verhindern. Iteration

Die Potenziteration bevorzugt den größten Betrag. Um einen Eigenwert nahe der Verschiebung $\sigma$ zu finden, wiederholt man

(A-\sigma I)z_k=q_{k-1}

Die Eigenwerte von $(A-\sigma I)^{-1}$ sind $1/(\lambda_i-\sigma)$ . Daher wird der Eigenwert mit dem kleinsten Abstand zu $\sigma$ dominant. Bilde die Inverse niemals explizit. $Faktorisiere$ $A-\sigma I$ und löse in jeder Iteration ein lineares Gleichungssystem. Bei fester Verschiebung kann die Faktorisierung wiederverwendet werden.

Liegt $\sigma$ sehr nahe an einem Eigenwert, ist das verschobene System schlecht konditioniert. Genaue lineare Lösungen und Residuenprüfungen sind deshalb unverzichtbar.

Algorithmus mit QR für das vollständige Spektrum

Beginne mit $A_0=A$ . Berechne in Iteration $k$

A_k=Q_kR_k

Jeder Schritt ist eine $orthogonale Ähnlichkeitstransformation$ und erhält daher die Eigenwerte. Praktische $\mathrm{QR}$ -Algorithmen reduzieren eine dichte Matrix zuerst auf Hessenberg-Form, verwenden Verschiebungen und trennen konvergierte Blöcke ab. Bei einer reellen unsymmetrischen Matrix ist das Ergebnis im Allgemeinen eine reelle Schur-Form mit diagonalen $1\times1$ - und $2\times2$ -Blöcken. Eine symmetrische Matrix wird auf Tridiagonalform reduziert und konvergiert zu einer Diagonalmatrix.

Das passende Verfahren wählen

Ziel und Matrixstruktur	Geeignetes Verfahren	Wichtige Prüfung
Ein dominantes Eigenpaar	Potenziteration	eindeutig größter Betrag und Startkomponente ungleich null
Eigenpaar nahe $\sigma$	Verschobene inverse Iteration	stabile Lösungen mit $A-\sigma I$
Mehrere extreme Eigenpaare einer großen symmetrischen dünn besetzten Matrix	Lanczos	Verlust der Orthogonalität und Residuen
Mehrere Eigenpaare einer großen unsymmetrischen dünn besetzten Matrix	Arnoldi	Unterraumgröße, Neustarts und Residuen
Vollständiges Spektrum einer dichten Matrix	Verschobenes $\mathrm{QR}$ -Verfahren zur Schur-Form	konvergierte diagonale oder quasidiagonale Blöcke

Die abschließende Prüfung richtet sich immer nach den gesuchten Eigenpaaren: $Kontrolliere die Residuen$ , erhalte komplex konjugierte Paare reeller Matrizen und prüfe die Genauigkeit eines Eigenvektors getrennt von einer stabilen Eigenwertschätzung.