Ausgewählte Eigenwerte berechnen

Verschobene inverse Iteration

Die verschobene inverse Iteration zielt auf den Eigenwert, der einer gewählten Verschiebung $\mu$ am nächsten liegt. Wir beginnen mit einer reellen symmetrischen Matrix $A \in \mathbb{R}^{n \times n}$ . Ihre Eigenwerte sind reell, und das Konvergenzverhalten lässt sich besonders klar beschreiben.

Wähle ein $\mu$ , das selbst kein Eigenwert ist, und einen normierten Startvektor $q_0$ mit einer von null verschiedenen Komponente in der gesuchten Eigenvektorrichtung. Faktorisiere $A-\mu I$ einmal und verwende diese Faktorisierung wiederholt.

Ein Iterationsschritt

Führe für $k=0,1,2,\ldots$ die folgenden Schritte aus:

(A-\mu I)y_{k+1}=q_k

Der Rayleigh-Quotient $\rho_{k+1}$ schätzt den Eigenwert. Eine skalenabhängige Abbruchregel prüft das Residuum, statt lediglich aufeinanderfolgende Schätzungen zu vergleichen:

\|r_{k+1}\|_2 \leq \tau\bigl(\|A\|_2+|\rho_{k+1}|\bigr)

Aus $Av_i=\lambda_i v_i$ folgt

(A-\mu I)^{-1}v_i=\frac{1}{\lambda_i-\mu}v_i

und der Eigenwert nahe $\mu$ erzeugt damit den größten transformierten Betrag. In der Implementierung lösen wir das lineare Gleichungssystem. Wir bilden $(A-\mu I)^{-1}$ nicht explizit.

Potenziteration

Die Potenziteration zielt auf den Eigenwert mit dem größten Betrag. Ausgehend von einem normierten Vektor $q_0$ wiederholen wir:

y_{k+1}=Aq_k

Bei einer symmetrischen Matrix ist die Konvergenz zum dominanten Eigenvektor zu erwarten, wenn

|\lambda_1|>|\lambda_2|

gilt und der Startvektor eine von null verschiedene Komponente in Richtung des Eigenvektors zu $\lambda_1$ besitzt. Der asymptotische Konvergenzfaktor beträgt ungefähr $|\lambda_2/\lambda_1|$ . Gleiche oder eng beieinanderliegende dominante Beträge können die Einvektorkonvergenz verlangsamen oder verhindern.

Welchen Eigenwert findet welches Verfahren?

Das Wort „kleinster“ ist mehrdeutig. Deshalb muss das Ziel immer genau benannt werden.

Methode	Ziel
Potenziteration auf $A$	Eigenwert mit dem größten Betrag
Inverse Iteration mit $\mu=0$

Bei einer indefiniten Matrix muss der Eigenwert mit dem kleinsten Betrag nicht der negativste Eigenwert sein. Diese Unterscheidung verhindert einen häufigen Interpretationsfehler.

Beispiel zur verschobenen inversen Iteration

Betrachten wir

A=\begin{pmatrix}2&0\\0&5\end{pmatrix}

Das verschobene System liefert im ersten Schritt

y_1=(A-I)^{-1}q_0=\frac{1}{\sqrt{2}}\begin{pmatrix}1\\1/4\end{pmatrix}

Da $2$ näher an der Verschiebung $1$ liegt als $5$ , treiben weitere Iterationen die zweite Komponente gegen null und $\rho_k$ gegen $2$ .

Praktische Prüfungen

Faktorisiere die verschobene Matrix mit einem stabilen Verfahren und, falls nötig, mit Pivotisierung. Trifft die Verschiebung genau einen Eigenwert, ist die verschobene Matrix singulär. Dann muss der Lösevorgang gesondert behandelt oder die Verschiebung angepasst werden.
Verwende die Residuumsnorm als Abbruchkriterium. Eine kleine Änderung zwischen zwei Eigenwertschätzungen beweist noch kein genaues Eigenpaar.
Das Vorzeichen eines Eigenvektors ist frei: $q$ und $-q$ beschreiben dieselbe Eigenrichtung.
Für Eigenwertcluster oder allgemeine nichtnormale Matrizen eignen sich Mehrvektorverfahren oder die Schur-Form, etwa Lanczos-, Arnoldi- oder QR-basierte Eigenwertlöser.