Potenzmethode

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 besser ab.[2]

Der Algorithmus[Bearbeiten]

Naiver Ansatz[Bearbeiten]

Aus der Stochastik abgeleitet gibt es folgenden naiven Ansatz zur Eigenwertberechnung. Betrachtet man einen stochastischen Startvektor v_0 und eine spaltenstochastische Matrix S, dann ist die Wahrscheinlichkeitsverteilung einer Markow-Kette zum Zeitpunkt t genau v_t=Sv_{t-1}. Falls nun die v_t gegen einen Vektor v konvergieren, so ist Sv=v und wir haben eine vom Anfangszustand unabhängige Stationäre Verteilung und damit auch einen Eigenvektor zum Eigenwert 1 gefunden. Formal ist also v=\lim_{i \rightarrow \infty}S^iv_0, es wurden Matrixpotenzen gebildet. Dieses Verfahren lässt sich nun für beliebige Matrizen verallgemeinern.

Allgemeiner Algorithmus[Bearbeiten]

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 die Matrix A auf die aktuelle Näherung r_k 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 halbeinfach ist und alle anderen Eigenwerte einen echt kleineren Betrag haben. Es existiert also ein Index  d , so dass für die Eigenwerte gilt \lambda_1= \ldots = \lambda_d und |\lambda_d| > |\lambda_{d+1}|\geq\ldots\geq|\lambda_n|. Hierbei ist  d die geometrische (und algebraische) Vielfachheit des Eigenwerts  \lambda_1 .

Der zum Vektor  r_k gehörende approximierte Eigenwert kann auf zwei Arten berechnet werden:

  1. Bildet man die Skalare \theta_k=\frac{\langle r_k,\,A r_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.
  2. 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).

Beweis der Konvergenz[Bearbeiten]

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^kV^{-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_1v_1 + \ldots + \beta_dv_d \neq 0

Dann ist

\displaystyle
\begin{align}
A^kr_0 &= VD^kV^{-1}r_0 \\
      &= VD^k(\beta_1e_1+\ldots+\beta_ne_n) \\
      &= \lambda_1^kV\left(\beta_1e_1+\ldots+\beta_de_d+\sum_{i=d+1}^n\left(\frac{\lambda_i}{\lambda_1}\right)^ke_i\right) \\
      &= \lambda_1^k\left(\beta_1v_1+\ldots+\beta_dv_d+  \underbrace{ \sum_{i=d+1}^n \left( \frac{\lambda_i}{\lambda_1} \right)^kv_i}_{\to 0 \text{ für } k \to \infty} \right)            
\end{align}

Da nach der Voraussetzung gilt, dass \tfrac{|\lambda_i|}{|\lambda_1|}<1 \; \text{für} \; i\geq d+1. Wegen


\lim_{k \to \infty}\lambda_1^k=
\begin{cases}
\pm \infty  &\;\text{für}\; |\lambda_1|>1\\
0 &\;\text{für}\; |\lambda_1|<1
\end{cases}

wird in jedem Schritt die Normierung des Vektors auf 1 durchgeführt. Die oben angegebene Bedingung an den Startvektor besagt, dass er einen Nichtnullanteil in Richtung des Eigenvektors haben muss. Dies ist aber meist nicht einschränkend, da sich diese Bedingung durch Rundungsfehler in der Praxis oftmals von alleine ergibt.

Konvergenzgeschwindigkeit[Bearbeiten]

Konvergenzgeschwindigkeit der Potenzmethode für die Matrizen A (blau) und B (grün). Es ist jeweils \Vert r_k-e \Vert_\infty gegen die Anzahl der Iterationsschritte aufgetragen.

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. Des Weiteren haben noch Jordanblöcke einen Einfluss auf die Konvergenzgeschwindigkeit. Betrachte dazu als Beispiel die Matrizen

 A=
\begin{pmatrix} 
1 & 0   & 0   & 0  \\ 
0 & 0.8 & 0   & 0  \\
0 & 0   & 0.8 & 0  \\
0 & 0   & 0   & 0.8
\end{pmatrix} 
\quad\text{mit}\quad
A^n=
\begin{pmatrix} 
1 & 0     & 0     & 0    \\ 
0 & 0.8^n & 0     & 0    \\
0 & 0     & 0.8^n & 0    \\
0 & 0     & 0     & 0.8^n
\end{pmatrix}

und

 B=
\begin{pmatrix} 
1 & 0   & 0   & 0  \\ 
0 & 0.8 & 1   & 0  \\
0 & 0   & 0.8 & 1  \\
0 & 0   & 0   & 0.8
\end{pmatrix} 
\quad\text{mit}\quad
B^n=
\begin{pmatrix} 
1 &   0   &        0         & 0                      \\ 
0 & 0.8^n & n\cdot 0.8^{n-1} & \tfrac{n(n-1)}{2}\cdot 0.8^{n-2}  \\
0 &   0   &        0.8^n     &      n\cdot 0.8^{n-1}   \\
0 &   0   &          0       &             0.8^n
\end{pmatrix}

Beide haben den Eigenvektor e=(1,0,0,0)^T zum betragsgrößten Eigenwert \lambda_1=1 und die Separation der Eigenwerte ist |\lambda_2 / \lambda_1|=0.8. Unter Verwendung der Maximumsnorm \|x\|_{\infty} := \max(|x_1|, \ldots , |x_n|) und des Startvektors r_0=(1,1,1,1)^T konvergiert die Matrix A mit linearer Konvergenzgeschwindigkeit, während die Matrix B erst nach ca. 60 Iterationsschritten ein brauchbares Ergebnis liefert (vergleiche Bild).

Verwendung[Bearbeiten]

Da zur Berechnung des Gleichgewichtszustandes großer Markow-Ketten nur der Eigenvektor zum betragsgrößten Eigenwert bestimmt werden muss, kann hierfür die Potenzmethode verwendet werden, wie bereits im Abschnitt „naiver Ansatz“ beschrieben wurde. Insbesondere kann hier auf die Normierung in jedem Rechenschritt verzichtet werden, da die betrachtete Matrix stochastisch ist und damit die Betragsnorm des stochastischen Vektors erhält. Ein Beispiel dafür ist die Berechnung der PageRanks eines großen gerichteten Graphen als betragsgrößten Eigenvektor der Google-Matrix. Insbesondere sind bei der Google-Matrix die Eigenwerte gut separiert, sodass eine schlechte Konvergenzgeschwindigkeit ausgeschlossen werden kann.[3]

Varianten[Bearbeiten]

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 Krylowraum-Verfahren[Bearbeiten]

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[Bearbeiten]

Einzelnachweise[Bearbeiten]

  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)
  3. The Second Eigenvalue of the Google Matrix . Website der Stanford University . Abgerufen am 30. August 2013.