Von-Mises-Iteration

Die Potenzmethode oder von-Mises-Iteration (nach Richard von Mises) ist ein numerisches Verfahren zur Berechnung des betragsgrößten Eigenwertes einer Matrix. Es ist ein nicht-optimales Krylow-Unterraum-Verfahren, welches nur den jeweils letzten berechneten Vektor zur Eigenwertnäherung verwendet. Die Potenzmethode ist hinsichtlich der Konvergenzgeschwindigkeit den anderen Krylovraum-Verfahren, wie etwa dem Verfahren von Lanczos oder dem Verfahren von Arnoldi unterlegen. Dafür schneidet die Potenzmethode hinsichtlich der Stabilitätsanalyse besser ab.

Der Algorithmus

Gegeben sei eine quadratische Matrix $A\in\mathbb{C}^{n\times n}$ und ein Startvektor $r_0\in\mathbb{C}^n$ mit $A r_0 \neq 0$. In jedem Iterationsschritt wird einfach die aktuelle Näherung normiert und dann die Matrix A auf den normierten Vektor angewandt:

1. $q_k\leftarrow r_{k-1}/\|r_{k-1}\|$
2. $r_k\leftarrow Aq_k$
3. $\theta_k\leftarrow \langle q_k,r_k\rangle$

Konvergenz

Die Skalare θ_k konvergieren gegen den betragsgrößten Eigenwert und die Vektoren q_k gegen den zugehörigen normierten Eigenvektor, sofern der Eigenwert dem Betrage nach einfach ist und der Startvektor einen Nichtnull-Anteil an dem zugehörigen Eigenraum hat.

Unter der häufigen starken Voraussetzung, dass der Eigenwert einfach, betragsmäßig einfach und gut separiert ist, konvergieren sowohl die Eigenwertnäherungen als auch die Eigenvektornäherungen linear mit der Konvergenzgeschwindigkeit | λ₂ | / | λ₁ | , wobei die Eigenwerte dem Betrage nach abfallend sortiert angenommen werden, $|\lambda_1|>|\lambda_2|\geq\ldots\geq|\lambda_n|$.

Vergleiche mit anderen Krylovraum-Verfahren

Die Potenzmethode ist zu den anderen Krylowraum-Verfahren sehr ähnlich. Es finden sich die typischen Ingredienzien der komplexeren Verfahren wieder, so etwa die Normierung der konstruierten Basisvektoren, die Erweiterung des Krylowraumes und die Berechnung von (Elementen von) Projektionen im letzten Schritt.

Literatur

• Hans R. Schwarz, Norbert Köckler: Numerische Mathematik, 5. Aufl., Teubner, Stuttgart 2004, ISBN 3-519-42960-8.