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}$ . Alle Eigenwerte sind reell, und die Eigenvektoren können als Orthonormalbasis gewählt werden.

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.

Der gesuchte Eigenwert muss $eindeutig am nächsten an der Verschiebung liegen$ . Bei gleichen Abständen entsteht kein eindeutig dominanter transformierter Betrag. Gemeint ist Konvergenz der Eigenrichtung. Ein negativer transformierter Eigenwert kann das Vorzeichen des Vektors wechseln.

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)

Für ein Eigenpaar mit $Av_i=\lambda_i v_i$ wirkt die verschobene Inverse wie folgt.

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

Diese Beziehung zeigt, dass der Eigenwert nahe $\mu$ den größten transformierten Betrag erzeugt. In der Implementierung lösen wir das lineare Gleichungssystem, ohne $(A-\mu I)^{-1}$ explizit zu bilden.

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 erfordert die Konvergenz zum dominanten Eigenvektor die folgende Spektrallücke.

|\lambda_1|>|\lambda_2|

Der Startvektor muss außerdem eine von null verschiedene Komponente in Richtung des Eigenvektors zu $\lambda_1$ besitzen. 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.

Der Eigenwert jedes Verfahrens

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$ und invertierbarem $A$	Von null verschiedener Eigenwert mit dem kleinsten Betrag
Verschobene inverse Iteration	Eigenwert mit dem geringsten Abstand zu $\mu$
Inverse Iteration auf einer positiv definiten Matrix	Kleinster algebraischer Eigenwert, der zugleich den kleinsten Betrag hat

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$ .

Prüfe auch das erste Residuum: Die Schätzung verbessert sich, ist aber noch nicht konvergiert:

r_1=\frac1{17\sqrt{17}}\begin{pmatrix}-12\\48\end{pmatrix},\qquad \|r_1\|_2=\frac{12}{17}

Praktische Prüfungen

Mit diesen Prüfungen entscheidest du, ob ein berechnetes Paar aus Eigenwert und Eigenvektor stimmt, ohne die ganze Determinante erneut zu rechnen. Arbeite sie der Reihe nach für dein Ergebnis ab.

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, mit Lanczos bei symmetrischen Problemen und Arnoldi- oder $\mathrm{QR}$ -basierte Eigenwertlöser.