Potenzmethode

Die Potenzmethode, Vektoriteration oder von-Mises-Iteration (nach Richard von Mises ) ist ein numerisches Verfahren zur Berechnung des betragsgrößten Eigenwertes und des dazugehörigen Eigenvektors einer Matrix. Der Name kommt daher, dass Matrixpotenzen $A^{k}x$ 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 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 $Ar_{0}\neq 0$. In jedem Iterationsschritt wird einfach die aktuelle Näherung $r_{k}$ auf die Matrix A angewandt und dann normiert.

$r_{k+1}={\frac {Ar_{k}}{\Vert Ar_{k}\Vert }}$

oder in geschlossener Form

$r_{k+1}={\frac {A^{k+1}r_{0}}{\Vert A^{k+1}r_{0}\Vert }}$

Die Vektoren $r_{k}$ konvergieren gegen einen Eigenvektor zum betragsgrößten Eigenwert, sofern dieser Eigenwert dem Betrage nach einfach ist und seine algebraische Vielfachheit gleich seiner geometrischen Vielfachheit ist, d.h. es existiert ein index $r$ so dass für die Eigenwerte gilt $|\lambda _{1}|=\ldots =|\lambda _{r}|>|\lambda _{r+1}|\geq \ldots \geq |\lambda _{n}|$. Hierbei ist $r$ dei geometrische (und algebraische) Vielfachheit des Eigenwerts $\lambda _{1}$

Der zum Vektor $r_{k}$ gehörende approximierte Eigenwert kann auf 2 Arten berechnet werden:

1. Bildet man die Skalare $\theta _{k}={\frac {\langle r_{k},\,Ar_{k}\rangle }{\langle r_{k},\,r_{k}\rangle }}={\frac {\langle r_{k},\,r_{k+1}\rangle }{\Vert r_{k}\Vert _{2}^{2}}}$ (den sogenannten Rayleigh-Quotient), so konvergiert $\theta _{k}$ gegen $\lambda _{1}$. Dies folgt direkt aus der Konvergenz von $r_{k}$ gegen einen Eigenvektor.

1. Ist man nicht am Vorzeichen des Eigenwertes interessiert, so bietet sich ein einfacher Ansatz an: Da $r_{k}$ gegen einen Eigenvektor konvergiert und in jedem Schritt auf 1 normiert wird, konvergiert $\Vert Ar_{k}\Vert$ gegen $|\lambda _{1}|$ (unabhängig von der verwendeten Norm).

Beweiß der Konvergenz

Wir geben hier einen Beweis unter der Annahme, dass die Matrix $A$ diagonalisierbar ist. Der Beweis für den nichtdiagonalisierbaren fall läuft analog.

O.B.d.A. seien die Eigenwerte wie oben angeordnet. Sei V die Basiswechselmatrix zur Matrix $A$. Dann ist $A^{k}=VD^{k}V^{-1}$ wobei $D$ nach voraussetzung eine Diagonalmatrix ist, welche die Eigenwerte enthält. Sei nun $v_{1},\ldots ,v_{n}$ eine Basis aus Eigenvektoren (die Spaltenvektoren von $V$) und $r_{0}$ ein Startvektor mit

$r_{0}=\sum _{i=1}^{n}\beta _{i}v_{i}\quad {\text{mit}}\;\beta _{1}v_{1}+\ldots +\beta _{r}v_{r}\neq 0$

Dann ist $A^{k}r_{0}=VD^{k}V^{-1}r_{0}=VD^{k}(\beta _{1}e_{1}+\ldots +\beta _{n}e_{n})=\lambda _{1}^{k}V\left(\beta _{1}e_{1}+\ldots +\beta _{r}e_{r}+\sum _{i=r+1}^{n}\left({\frac {\lambda _{i}}{\lambda _{1}}}\right)^{k}e_{i}\right)=\lambda _{1}^{k}\left(\beta _{1}v_{1}+\ldots +\beta _{r}v_{r}+\sum _{i=r+1}^{n}\left({\frac {\lambda _{i}}{\lambda _{1}}}\right)^{k}v_{i}\right)$

Da nach der Voraussetzung gilt, dass ${\frac {|\lambda _{i}|}{|\lambda _{1}|}}<1$ für $i\geq r+1$ konvergiert der rechte Teil der Gleichung gegen 0.

Konvergenzgeschwindigkeit

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 $|\lambda _{2}|/|\lambda _{1}|$, 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.

Verwendung

Da die Potenzmethode nur den Eigenvektor zum betragsgrößten Eigenwert liefert bietet sie zich z.B. zur Lösung des PageRankAlgorithmus an

Varianten

Hat man einen Eigenwert $\lambda$ ausgerechnet, kann man das Verfahren auf die Matrix $A-\lambda I$ anwenden, um ein weiteres Eigenwert-Eigenvektor-Paar zu bestimmen. Darüber hinaus gibt es die inverse Iteration, bei der das Verfahren auf $(A-\lambda 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.
• Peter Knabner, Wolf Barth: Lineare Algebra. 1. Auflage. Springer Spektrum, Berlin Heidelberg 2012
• Josef Stoer, Roland Bulirsch: Numerische Mathematik 2, 5. Auflage Springer Verlag Berlin Heidelberg New York 2005