134.60.67.135: /* Beweis der Konvergenz */

2025-03-20T16:25:13Z

Beweis der Konvergenz

Neue Seite

Die '''Potenzmethode''', '''Vektoriteration''' oder '''Von-Mises-Iteration''' (nach [[Richard von Mises]])<ref name="VonMises">R. von Mises und H. Pollaczek-Geiringer, ''Praktische Verfahren der Gleichungsauflösung'', ZAMM - Zeitschrift für Angewandte Mathematik und Mechanik 9, 152–164 (1929).</ref> ist ein [[Numerische Mathematik|numerisches Verfahren]] zur Berechnung des betragsgrößten [[Eigenwert]]es und des dazugehörigen Eigenvektors einer [[Matrix (Mathematik)|Matrix]]. Der Name kommt daher, dass Matrixpotenzen <math>A^kx</math> gebildet werden, wesentlicher Aufwand sind also [[Matrix-Vektor-Produkt]]e. Deswegen ist das Verfahren insbesondere für [[Dünnbesetzte Matrix|dünnbesetzte Matrizen]] geeignet. Eine direkte Verallgemeinerung zur Berechnung mehrerer betragsgrößter Eigenwerte [[Dünnbesetzte Matrix|dünnbesetzter Matrizen]] ist die [[Unterraumiteration]].

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-Verfahren|Lanczos]] oder dem Verfahren von [[Arnoldi-Verfahren|Arnoldi]] unterlegen. Dafür schneidet die Potenzmethode hinsichtlich der [[Stabilität (Numerik)|Stabilitätsanalyse]] besser ab.<ref name="Wilkinson">J. H. Wilkinson, ''The Algebraic Eigenvalue Problem'', Oxford University Press (1965).</ref>

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

=== Allgemeiner Algorithmus ===
Gegeben sei eine [[quadratische Matrix]] <math>A\in\mathbb{C}^{n\times n}</math> und ein Startvektor <math>r_0\in\mathbb{C}^n</math>. Der Algorithmus approximiert den betragsmäßig größten Eigenwert <math>\lambda_1</math> von <math>A</math> unter der Voraussetzung, dass der Eigenwert [[halbeinfach]] ist und sein Betrag strikt größer als der aller anderen Eigenwerte. Zudem sei der Startvektor nicht [[orthogonal]] zum Eigenraum von <math>\lambda_1</math>. In jedem [[Iteration|Iterationsschritt]] wird die [[Matrix (Mathematik)|Matrix]] <math>A</math> auf die aktuelle Näherung <math>r_k</math> angewandt und dann [[Norm (Mathematik)|normiert]].

:<math>r_{k+1}= \frac{Ar_k}{\Vert Ar_k \Vert}</math>

oder in geschlossener Form

:<math>r_{k+1}= \frac{A^{k+1}r_0}{\Vert A^{k+1}r_0 \Vert}</math>

Die [[Vektor|Vektoren]] <math>r_k</math> konvergieren gegen einen [[Eigenvektor]] zum betragsgrößten Eigenwert, sofern dieser Eigenwert [[Halbeinfacher Eigenwert|halbeinfach]] ist und alle anderen Eigenwerte einen echt kleineren Betrag haben. Es existiert also ein Index <math> d </math>, so dass für die Eigenwerte gilt <math>\lambda_1= \ldots = \lambda_d</math> und <math>|\lambda_d| > |\lambda_{d+1}|\geq\ldots\geq|\lambda_n|</math>. Hierbei ist <math> d </math> die geometrische (und algebraische) Vielfachheit des Eigenwerts <math> \lambda_1 </math>.

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

# Bildet man die Skalare <math>\theta_k=\frac{\langle r_k,\,A r_k\rangle}{\langle r_k,\, r_k\rangle}=\frac{\langle r_k,\,A r_k\rangle}{\Vert r_k \Vert_2^2}</math> (den sogenannten [[Rayleigh-Quotient]]en), so konvergiert <math>\theta_k</math> gegen <math>\lambda_1</math>. Dies folgt direkt aus der Konvergenz von <math>r_k</math> gegen einen Eigenvektor.
# Ist man nicht am Vorzeichen des Eigenwertes interessiert, so bietet sich ein einfacher Ansatz an: Da <math>r_k</math> gegen einen Eigenvektor konvergiert und in jedem Schritt auf 1 normiert wird, konvergiert <math>\Vert Ar_k \Vert</math> gegen <math>|\lambda_1|</math> (unabhängig von der verwendeten Norm).
Ist <math>A = VJV^{-1}</math> die Darstellung der [[Quadratische Matrix|quadratischen Matrix]] in der [[Jordansche Normalform|jordanschen Normalform]], dann ergibt sich daraus <math>A^k = (VJV^{-1})^k = VJ^kV^{-1}</math>, also <math>A^kV = VJ^k</math>. Ist nun <math>x = V\tilde{x} \in \mathbb{C}</math> ein zufälliger Vektor, dann gilt

:<math>A^kx = A^kV \tilde{x} = VJ^k \tilde{x} = \sum_{i=1}^n v_i \lambda_i^k \tilde{x}_i</math>

Ausklammern eines konstanten Faktors ergibt

:<math>A^kx = \lambda_1^k \sum_{i=1}^n v_i \left(\frac{\lambda_i}{\lambda_1}\right)^k \tilde{x}_i</math>

Dann gilt <math>\lim_{k\to\infty} \left(\frac{\lambda_i}{\lambda_1}\right)^k = 0</math> für jedes <math>i>1</math> und für große <math>k</math> ist <math>A^kx</math> und damit <math>r_k</math> fast [[Parallelität (Geometrie)|parallel]] zu <math>(\lambda_1/|\lambda_1|)^kv_1</math>, da nach Voraussetzung <math>\tilde{x}_1 \neq 0</math> (was z. B. durch eine zufällige Wahl des Vektors sichergestellt werden kann). Somit konvergiert <math>r_k</math> gegen einen normierten Eigenvektor zum Eigenwert <math>\lambda_1</math>.<ref>{{Literatur |Titel=Grundlagen der Numerischen Mathematik und des Wissenschaftlichen Rechnens |Autor=Martin Hanke-Bourgeois |Verlag=Vieweg+Teubner Verlag |Ort=Wiesbaden |Datum=2008 |ISBN=978-3-8348-0708-3 |Fundstelle=S. 218ff |Online={{Google Buch|BuchID=KdojBAAAQBAJ|Seite=218}}}}</ref><ref>Cornell University: [https://www.cs.cornell.edu/~bindel/class/cs6210-f16/lec/2016-10-17.pdf Power iteration].</ref>

== Beweis der Konvergenz ==
Wir geben hier einen Beweis unter der Annahme, dass die Matrix <math>A</math> diagonalisierbar ist. Der Beweis für den nichtdiagonalisierbaren Fall läuft analog.

[[O.B.d.A.]] seien die Eigenwerte wie oben angeordnet. Sei <math>V</math> die [[Basiswechselmatrix]] zur Matrix <math>A</math>. Dann ist <math>A^k=VD^kV^{-1}</math> wobei <math>D</math> nach Voraussetzung eine Diagonalmatrix ist, welche die Eigenwerte enthält.
Sei nun <math> v_1,\ldots, v_n </math> eine Basis aus Eigenvektoren (die Spaltenvektoren von <math>V</math>) und <math>r_0</math> ein Startvektor mit

:<math>r_0=\sum_{i=1}^n \beta_i v_i \quad \text{mit} \; \beta_1v_1 + \ldots + \beta_dv_d \neq 0</math>

Dann ist
:<math>\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\bigg(\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} \bigg),
\end{align}
</math>
da nach Voraussetzung gilt, dass <math>\tfrac{|\lambda_i|}{|\lambda_1|}<1</math> für <math>i\geq d+1</math>. Wegen

:<math>
\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}
</math>
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 ==

[[Datei:Poweriteration speed.jpg|mini|Konvergenzgeschwindigkeit der Potenzmethode für die Matrizen A (blau) und B (grün). Es ist jeweils <math>\Vert r_k-e \Vert_\infty</math> 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 <math>|\lambda_2|/|\lambda_1|</math>, wobei die Eigenwerte dem Betrage nach abfallend sortiert angenommen werden, <math>|\lambda_1|>|\lambda_2|\geq\ldots\geq|\lambda_n|</math>. 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

:<math> 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}
</math>

und

:<math> 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}
</math>

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

== Verwendung ==

Da zur Berechnung des Gleichgewichtszustandes großer [[Markow-Kette]]n nur der Eigenvektor zum betragsgrößten Eigenwert bestimmt werden muss, kann hierfür die Potenzmethode verwendet werden, wie bereits im Abschnitt „Motivation“ beschrieben wurde. Insbesondere kann hier auf die Normierung in jedem Rechenschritt verzichtet werden, da die betrachtete Matrix [[Stochastische Matrix|stochastisch]] ist und damit die Betragsnorm des stochastischen Vektors erhält. Ein Beispiel dafür ist die Berechnung der [[PageRank]]s eines großen [[Gerichteter Graph|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.<ref>[https://nlp.stanford.edu/pubs/secondeigenvalue.pdf ''The Second Eigenvalue of the Google Matrix'' ]. Website der Stanford University
. Abgerufen am 30. August 2013.</ref>

== Varianten ==

Hat man einen Eigenwert <math>\lambda</math> ausgerechnet, kann man das Verfahren auf die Matrix <math>A-\lambda V</math> anwenden, um ein weiteres Eigenwert-Eigenvektor-Paar zu bestimmen. Hierbei sei <math>V</math> das [[Kronecker-Produkt]] des Eigenvektors zum jeweiligen Eigenwert <math>\lambda</math> mit sich selbst. Dabei wird vorausgesetzt, dass <math>A</math> unitär diagonalisierbar ist. <math>A-\lambda V</math> erhält dabei alle Eigenwerte von <math>A</math> mit Ausnahme von <math>\lambda</math> (<math>\lambda=0</math>).

Darüber hinaus gibt es die [[inverse Iteration]], bei der das Verfahren auf <math>(A-\lambda I)^{-1}</math> angewandt wird, indem in jedem Schritt lineare Gleichungssysteme gelöst werden.

== Vergleiche mit anderen Krylowraum-Verfahren ==
Die Potenzmethode ist den anderen [[Krylowraum]]-Verfahren sehr ähnlich. Es finden sich die typischen Bestandteile 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. Auflage. Teubner, Stuttgart 2004, ISBN 3-519-42960-8.
* {{Literatur | Autor=[[Peter Knabner]], [[Wolf Barth (Mathematiker)|Wolf Barth]] | Titel=Lineare Algebra | Reihe=Springer-Lehrbuch |TitelErg=Grundlagen und Anwendungen|Auflage= | Verlag=Springer| Ort=Berlin| Jahr=2012| ISBN=978-3-642-32185-6 }}
* Josef Stoer, [[Roland Bulirsch]]: ''Numerische Mathematik 2.'' 5. Auflage. Springer, Berlin/Heidelberg/New York 2005, ISBN 978-3-540-23777-8.

== Einzelnachweise ==
<references/>

[[Kategorie:Numerische lineare Algebra]]

Potenzmethode - Versionsgeschichte

134.60.67.135: /* Beweis der Konvergenz */