- 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 Akx 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.
Inhaltsverzeichnis
Der Algorithmus
Gegeben sei eine quadratische Matrix und ein Startvektor mit . In jedem Iterationsschritt wird einfach die aktuelle Näherung normiert und dann die Matrix A auf den normierten Vektor angewandt:
Konvergenz
Die Skalare θk konvergieren gegen den betragsgrößten Eigenwert und die Vektoren qk 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 | λ2 | / | λ1 | , wobei die Eigenwerte dem Betrage nach abfallend sortiert angenommen werden, . 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
Wikimedia Foundation.