Direkt zum Inhalt

Lexikon der Mathematik: inverse Iteration

ein iteratives Verfahren zur Bestimmung eines Eigenvektors z zu einem Eigenwert λ einer Matrix \(A\in {{\mathbb{R}}}^{n\times n}\), wenn man bereits eine Näherung μ an den Eigenwert λ kennt.

Man berechnet dabei, ausgehend von einem beliebigen Startvektor x0, x0 ≠ 0, und einer Näherung μ an den Eigenwert λ, die Folge von Vektoren \begin{eqnarray}\begin{array}{l}{y}_{m+1}={(A-\mu I)}^{-1}{x}_{m}\quad\text{und}\\ {x}_{m+1}={y}_{m+1}/||{y}_{m+1}||.\end{array}\end{eqnarray} Die inverse Iteration ist also gerade die Potenzmethode, angewendet auf (AμI)−1. Die Folge der \({\{{y}_{m}\}}_{m\in {\mathbb{N}}}\) konvergiert sehr schnell gegen einen Eigenvektor von A zur Eigenwertnäherung μ.

Die explizite Berechnung von (AμI)−1 ist nicht erforderlich. Stattdessen löst man das lineare Gleichungssystem (AμI)ym+1 = xm. Da sich in diesem Gleichungssystem nur die rechten Seiten, nicht aber die Koeffizientenmatrizen mit m ändern, ist es vorteilhaft, einmal die LR-Zerlegung von AμI zu berechnen: P(AμI) = LR. Dann erhält man die Lösung ym+1 aus den beiden gestaffelten Gleichungssystemen Lz = Pxm und Rym+1 = z. Die Eigenwertnäherung μ wird häufig mittels des QR-Algorithmus berechnet, dann hat man A typischerweise in oberer Hessenberg-Form vorliegen. L ist dann sehr dünn besetzt, denn in jeder Spalte von L sind höchstens 2 Elemente ungleich Null. R ist eine obere Dreiecksmatrix. Das Auflösen der gestaffelten Gleichungssysteme erfordert daher nur wenig Aufwand.

Typischerweise beendet man die Iteration, wenn ||dm+1|| klein genug ist, wobei \begin{eqnarray}{d}_{m+1}={x}_{m+1}-{\tau }_{m+1}{x}_{m}\end{eqnarray} und \begin{eqnarray}{\tau }_{m+1}=\mathrm{sgn}{({x}_{m+1})}_{i}/\mathrm{sgn}{({x}_{m})}_{i}\end{eqnarray} für die maximale Komponente (xm)i des Vektors xm. Man setzt dann \begin{eqnarray}\lambda =\mu +\frac{1}{{\tau }_{m+1}\Vert {y}_{m+1}\Vert }\end{eqnarray} und z = xm+1.

Die beschriebene Grundform der inversen Iteration stammt von Wielandt und wird daher oft als Vektoriteration von Wielandt bezeichnet. Man kann das Verfahren der inversen Iteration so modifizieren, daß man neben dem Eigenvektor zur Eigenwertnäherung μ gleichzeitig eine Verbesserung der Eigenwertnäherung μ selbst erhält.

Der Ansatz der inversen Iteration läßt sich modifizieren, um mehrere Eigenvektoren gleichzeitig zu berechnen. Dazu startet man die Iteration statt mit einem einzelnen Startvektor x0 mit einer Startmatrix \({X}_{0}\in {{\mathbb{C}}}^{n\times p}\) um den zu p Eigenwertnäherungen \({\mu }_{1},{\mu }_{2},\mathrm{...},{\mu }_{p}\) gehörigen Eigenraum zu bestimmen. Dies führt auf Unterraum- Iterationsmethoden.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos