Potenzmethode

Die Potenzmethode, Vektoriteration oder von-Mises-Iteration (nach Richard von Mises ^[1]) ist ein numerisches Verfahren zur Berechnung des betragsgrößten Eigenwertes und des dazugehörigen Eigenvektors einer Matrix. Der Name kommt daher, dass Matrixpotenzen A^kx gebildet werden, wesentlicher Aufwand sind also Matrix-Vektor-Produkte. Deswegen ist das Verfahren insbesondere für dünnbesetzte Matrizen geeignet.

Die Potenzmethode lässt sich als nicht-optimales Krylow-Unterraum-Verfahren interpretieren, welches nur den jeweils letzten berechneten Vektor zur Eigenwertnäherung verwendet. Die Potenzmethode ist hinsichtlich der Konvergenzgeschwindigkeit den anderen Krylow-Raum-Verfahren, wie etwa dem Verfahren von Lanczos oder dem Verfahren von Arnoldi unterlegen. Dafür schneidet die Potenzmethode hinsichtlich der Stabilitätsanalyse ^[2] 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 \frac{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. Theoretisch muss der Startvektor einen Nichtnull-Anteil an dem zugehörigen Eigenraum haben, aufgrund von Rundungsfehlern ergibt sich dies in der Praxis in der Regel von selber.

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|$. Diese Voraussetzung ist zum Beispiel nach dem Satz von Perron-Frobenius bei Matrizen mit positiven Einträgen erfüllt.

Varianten

Hat man einen Eigenwert λ ausgerechnet, kann man das Verfahren auf die Matrix A − λI anwenden, um ein weiteres Eigenwert-Eigenvektor-Paar zu bestimmen. Darüber hinaus gibt es die inverse Iteration, bei der das Verfahren auf (A − λI) ^{− 1} angewandt wird, indem in jedem Schritt lineare Gleichungssysteme gelöst werden.

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.

Einzelnachweise

1. ↑ R. von Mises und H. Pollaczek-Geiringer, Praktische Verfahren der Gleichungsauflösung, ZAMM - Zeitschrift für Angewandte Mathematik und Mechanik 9, 152-164 (1929)
2. ↑ J. H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford University Press (1965)