Potenzmethode

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 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 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, |\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)

Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • QR-Algorithmus — Der QR Algorithmus ist ein numerisches Verfahren zur Berechnung aller Eigenwerte und eventuell der Eigenvektoren einer quadratischen Matrix. Das auch QR Verfahren oder QR Iteration genannte Verfahren basiert auf der QR Zerlegung und wurde im… …   Deutsch Wikipedia

  • Von-Mises-Iteration — Die Potenzmethode oder von Mises Iteration (nach Richard von Mises) ist ein numerisches Verfahren zur Berechnung des betragsgrößten Eigenwertes einer Matrix. Es ist ein nicht optimales Krylow Unterraum Verfahren, welches nur den jeweils letzten… …   Deutsch Wikipedia

  • Deflation (Mathematik) — Deflation bezeichnet eine Technik aus der numerischen Mathematik, mit der eine Matrix in Blockdreiecksform gebracht wird, so dass das Spektrum von A gerade die Vereinigung der Spektren der Diagonalblöcke ist. Inhaltsverzeichnis 1… …   Deutsch Wikipedia

  • Numerische Verfahren — Die Liste numerischer Verfahren führt Verfahren der numerischen Mathematik nach Anwendungsgebieten auf. Inhaltsverzeichnis 1 Lineare Gleichungssysteme 2 Nichtlineare Gleichungssysteme 3 Numerische Integration 4 Approximation und Interpolation …   Deutsch Wikipedia

  • Wielandt-Iteration — Die inverse Iteration ist ein numerisches Verfahren zur Berechnung von Eigenwerten von Matrizen. Sie ist eine Variante der von Mises Iteration, mit deren Hilfe allerdings beliebige Eigenwerte berechnet werden können. Das Verfahren wurde 1944 von… …   Deutsch Wikipedia

  • Algebraische Vielfachheit — In dieser Scherung der Mona Lisa wurde das Bild so verformt, dass der rote Pfeil (Vektor) entlang der vertikalen Achse seine Richtung nicht geändert hat, während der blaue Pfeil dies tut. Der rote Vektor ist ein Eigenvektor der Sch …   Deutsch Wikipedia

  • Eigenfunktion — In dieser Scherung der Mona Lisa wurde das Bild so verformt, dass der rote Pfeil (Vektor) entlang der vertikalen Achse seine Richtung nicht geändert hat, während der blaue Pfeil dies tut. Der rote Vektor ist ein Eigenvektor der Sch …   Deutsch Wikipedia

  • Eigenfunktionen — In dieser Scherung der Mona Lisa wurde das Bild so verformt, dass der rote Pfeil (Vektor) entlang der vertikalen Achse seine Richtung nicht geändert hat, während der blaue Pfeil dies tut. Der rote Vektor ist ein Eigenvektor der Sch …   Deutsch Wikipedia

  • Eigenvektor — In dieser Scherung der Mona Lisa wurde das Bild so verformt, dass der rote Pfeil (Vektor) entlang der vertikalen Achse seine Richtung nicht geändert hat, während der blaue Pfeil dies tut. Der rote Vektor ist ein Eigenvektor der Sch …   Deutsch Wikipedia

  • Eigenvektoren — In dieser Scherung der Mona Lisa wurde das Bild so verformt, dass der rote Pfeil (Vektor) entlang der vertikalen Achse seine Richtung nicht geändert hat, während der blaue Pfeil dies tut. Der rote Vektor ist ein Eigenvektor der Sch …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”