Inverse Iteration

Die inverse Iteration i​st ein numerisches Verfahren z​ur Berechnung v​on Eigenwerten u​nd Eigenvektoren v​on Matrizen. Sie i​st eine Variante d​er Von-Mises-Iteration, m​it deren Hilfe allerdings beliebige Eigenwerte berechnet werden können. Das Verfahren w​urde 1944 v​on Helmut Wielandt b​ei der Stabilitätsanalyse v​on Strukturen, d​ie kleine Störungen bekannter Systeme sind, eingeführt. In diesem Fall s​ind gute Approximationen für d​ie relevanten Eigenwerte bekannt, u​nd man erhält rasche Konvergenz.

Beschreibung

Ist ${\displaystyle \lambda }$ ein Eigenwert der quadratischen Matrix ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ und ${\displaystyle x}$ der zugehörige Eigenvektor, so ist ${\displaystyle \lambda -\theta }$ ein Eigenwert von ${\displaystyle (A-\theta I)}$ zum Eigenvektor ${\displaystyle x}$, wobei ${\displaystyle I}$ die Einheitsmatrix ist. Des Weiteren ist dann ${\displaystyle {\frac {1}{\lambda -\theta }}}$ ein Eigenwert von ${\displaystyle (A-\theta I)^{-1}}$ zum Eigenvektor ${\displaystyle x}$. Ist ${\displaystyle \lambda }$ nun der Eigenwert von ${\displaystyle A}$, der ${\displaystyle \theta }$ am nächsten liegt, so ist ${\displaystyle {\frac {1}{\lambda -\theta }}}$ der betragsmäßig größte Eigenwert von ${\displaystyle (A-\theta I)^{-1}}$. Wendet man nun auf ${\displaystyle (A-\theta I)^{-1}}$ die Potenzmethode an, so konvergiert ${\displaystyle x_{k}}$ gegen den Eigenvektor zum Eigenwert ${\displaystyle \lambda }$ von ${\displaystyle A}$, der ${\displaystyle \theta }$ am nächsten liegt.

Statt wie bei der Potenzmethode in jedem Schritt die Matrix mit einem Vektor zu multiplizieren, wird nun ein lineares Gleichungssystem gelöst, da ${\displaystyle (A-\theta I)^{-1}}$ nicht explizit verfügbar ist. Diese Matrix ist schlechter konditioniert, je näher ${\displaystyle \lambda }$ an ${\displaystyle \theta }$ liegt, allerdings hat der Fehler eine dominante Komponente in Richtung des gesuchten Eigenvektors, so dass das Verfahren praktisch nutzbar ist.

Algorithmus

Gegeben sei eine quadratische Matrix ${\displaystyle A\in \mathbb {C} ^{n\times n}}$, ein Startvektor ${\displaystyle x_{0}\in \mathbb {R} ^{n}}$ und ein Shift ${\displaystyle \theta \in \mathbb {R} }$ so dass ${\displaystyle (A-\theta I)}$ regulär ist. Der Startvektor kann bis auf eine Lebesgue-Nullmenge beliebig gewählt werden.

Für ${\displaystyle k=1,2,...}$

1. ${\displaystyle q_{k}={\frac {x_{k-1}}{\|x_{k-1}\|}}}$
2. Löse ${\displaystyle (A-\theta I)x_{k}=q_{k}}$

Über d​en Rayleigh-Quotienten erhält m​an eine Näherung für d​en zugehörigen Eigenwert.

${\displaystyle \lambda _{k}={\frac {x_{k}^{T}Ax_{k}}{x_{k}^{T}x_{k}}}}$

Erweiterungen

Wählt man in jedem Schritt über ${\displaystyle \theta =\lambda _{k}}$ einen neuen Shift so erhält man die Rayleigh-Quotienten-Iteration.

Literatur

• Gene H. Golub, Charles F. van Loan: Matrix Computations
• James H. Wilkinson: The Algebraic Eigenvalue Problem
• Hans-Rudolf Schwarz, Norbert Köckler: Numerische Mathematik. 5., überarbeitete Auflage. Teubner, Stuttgart u. a. 2004, ISBN 3-519-42960-8.