Inverse Iteration

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

Die inverse Iteration ist ein numerisches Verfahren zur Berechnung von Eigenwerten und Eigenvektoren 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 Helmut Wielandt bei der Stabilitätsanalyse von Strukturen, die kleine Störungen bekannter Systeme sind, eingeführt. In diesem Fall sind gute Approximationen für die relevanten Eigenwerte bekannt, und man erhält rasche Konvergenz.

Beschreibung[Bearbeiten]

Ist \lambda ein Eigenwert der quadratischen Matrix A \in \mathbb{C}^{n \times n} und x der zugehörige Eigenvektor, so ist \lambda-\theta ein Eigenwert von (A-\theta I) zum Eigenvektor x, wobei I die Einheitsmatrix ist. Des Weiteren ist dann \frac{1}{\lambda-\theta} ein Eigenwert von (A-\theta I)^{-1} zum Eigenvektor x. Ist \lambda nun der Eigenwert von A, der \theta am nächsten liegt, so ist \frac{1}{\lambda-\theta} der betragsmäßig größte Eigenwert von (A-\theta I)^{-1}. Wendet man nun auf (A-\theta I)^{-1} die Potenzmethode an, so konvergiert x_k gegen den Eigenvektor zum Eigenwert \lambda von A, der \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 (A-\theta I)^{-1} nicht explizit verfügbar ist. Diese Matrix ist schlechter konditioniert, je näher \lambda an \theta liegt, allerdings hat der Fehler eine dominante Komponente in Richtung des gesuchten Eigenvektors, so dass das Verfahren praktisch nutzbar ist.

Algorithmus[Bearbeiten]

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

Für k=1,2,...

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

Über den Rayleigh-Quotienten erhält man eine Näherung für den zugehörigen Eigenwert.

\lambda_k=\frac{x_k^TAx_k}{x_k^Tx_k}

Erweiterungen[Bearbeiten]

Wählt man in jedem Schritt über \theta=\lambda_k einen neuen Shift so erhält man die Rayleigh-Quotienten-Iteration.

Literatur[Bearbeiten]