Hessenberg-Form, von-Mises-Iteration und Deflation

Hessenberg-Form: Sei \(A\) eine \(n \times n\)-Matrix. Dann kann man die Einträge \((a_{j,k})\) mit \(j > k + 1\) durch \(n - 2\) Householder-Transformationen annullieren:

\begin{align*} A \mapsto Q_{n-2} \dotsm Q_1 A Q_1 \dotsm Q_{n-2}. \end{align*} Dabei erzeugt die \(\ell \)-te Transformation \(Q_\ell \) Nullen unterhalb von Position \((\ell + 1, \ell )\). Die so transformierte Matrix heißt (obere) Hessenberg-Matrix.
Ist \(A\) symmetrisch, so ist auch \(Q_{n-2} \dotsm Q_1 A Q_1 \dotsm Q_{n-2}\) symmetrisch und daher tridiagonal (nur Einträge ungleich \(0\) auf der Haupt- und den beiden Nebendiagonalen).
Bei der Transformation in die Hessenberg-Form bleiben die Eigenwerte erhalten, daher ist die Transformation eine nützliche Vorbereitung auf jede Eigenwert-Routine.

\(\ell \)-ter Schritt der Hessenberg-Transformation:

\begin{align*} & \left (\begin{array}{cccc|cccc} & & & & \ast & \ast & \cdots & \ast \\ & & & & \ast & \ast & \cdots & \ast \\ & H & & & \vdots & \vdots & & \vdots \\ & & & & \ast & \ast & \cdots & \ast \\ \hline & & & \boldsymbol{\ast } & \ast & \ast & \cdots & \ast \\ & & & \boldsymbol{\ast } & \ast & \ast & \cdots & \ast \\ & 0 & & \boldsymbol{\vdots } & \vdots & \vdots & & \vdots \\ & & & \boldsymbol{\ast } & \ast & \ast & \cdots & \ast \end {array}\right ) \xrightarrow {Q_i \cdot } \left (\begin{array}{cccc|cccc} & & & & \ast & \ast & \cdots & \ast \\ & & & & \ast & \ast & \cdots & \ast \\ & H & & & \vdots & \vdots & & \vdots \\ & & & & \ast & \ast & \cdots & \ast \\ \hline & & & \ast ’ & \ast ’ & \ast ’ & \cdots & \ast ’ \\ & & & 0 & \ast ’ & \ast ’ & \cdots & \ast ’ \\ & 0 & & \vdots & \vdots & \vdots & & \vdots \\ & & & 0 & \ast ’ & \ast ’ & \cdots & \ast ’ \end {array}\right ) \xrightarrow {\cdot Q_i} \left (\begin{array}{ccccc|ccc} \ast & \cdots & \ast & \ast & \ast ” & \ast ” & \cdots & \ast ” \\ \ast & \cdots & \ast & \ast & \ast ” & \ast ” & \cdots & \ast ” \\ & \ddots & \vdots & \vdots & \vdots & \vdots & & \vdots \\ 0 & & \ast & \ast & \ast ” & \ast ” & \cdots & \ast ” \\ & & & \ast ’ & \ast ” & \ast ” & \cdots & \ast ” \\ \hline & & & 0 & \ast ” & \ast ” & \cdots & \ast ” \\ & 0 & & \vdots & \vdots & \vdots & & \vdots \\ & & & 0 & \ast ” & \ast ” & \cdots & \ast ” \end {array}\right ) \\ & \text {mit } Q_\ell = \left (\begin{array}{c|c} E_\ell & 0 \\ \hline 0 & \widetilde {Q}_\ell \end {array}\right ) \text { und } H \text { ist } \ell \times \ell \text {-Matrix bereits in Hessenbergform} \end{align*} Beispiel:

\begin{align*} \left (\begin{array}{c|ccc} x & x & x & x \\ \hline \boldsymbol{x} & x & x & x \\ \boldsymbol{x} & x & x & x \\ \boldsymbol{x} & x & x & x \end {array}\right ) \xrightarrow {Q_1 \cdot } \left (\begin{array}{c|ccc} x & x & x & x \\ \hline y & y & y & y \\ 0 & y & y & y \\ 0 & y & y & y \end {array}\right ) \xrightarrow {\cdot Q_1} \left (\begin{array}{cc|cc} x & z & z & z \\ y & z & z & z \\ \hline 0 & \boldsymbol{z} & z & z \\ 0 & \boldsymbol{z} & z & z \end {array}\right ) \xrightarrow {Q_2 \cdot } \left (\begin{array}{cc|cc} x & z & z & z \\ y & z & z & z \\ \hline 0 & u & u & u \\ 0 & 0 & u & u \end {array}\right ) \xrightarrow {\cdot Q_2} \left (\begin{array}{ccc|c} x & z & v & v \\ y & z & v & v \\ 0 & u & v & v \\ \hline 0 & 0 & \boldsymbol{v} & v \end {array}\right ) \end{align*}

von-Mises-Iteration: Die von-Mises-Iteration (auch Potenzmethode) wendet Potenzen einer Matrix \(A\) auf einen Startvektor \(x\) an. Die resultierende normierte Folge

\begin{align*} u_n = \frac {A^n x}{\norm {A^n x}_2} \end{align*} konvergiert i. A. gegen einen dominanten Eigenvektor. Hinreichend für Konvergenz ist, dass \(A\) diagonalisierbar ist und einen betragsmäßig größten Eigenwert \(\lambda \) besitzt. Dann gilt für jeden Vektor \(x\) mit einer nicht-trivialen Komponente \(u \in V_\lambda (A)\), dass

\begin{align*} \norm {e^{-in\varphi }u_n - \frac {u}{\norm {u}_2}}_2 = \O \left (\left |\frac {\rho }{\lambda }\right |^n\right ), \end{align*} wobei \(e^{i\varphi } = \frac {\lambda }{|\lambda |}\) und \(\rho \) ein Eigenwert von \(A\) mit zweitgrößtem Betrag ist.

Bei einer einfachen (diagonalisierbaren) Matrix mit separierten Eigenwerten nähert sich so \(u_n\) dem normierten Eigenvektor des betragsmäßig größten Eigenwerts an. Die Konvergenzrate ist mit \(\O \left (\left |\frac {\rho }{\lambda }\right |^n\right )\) gegeben, für \(\lambda = 10\) und \(\rho = 1\) ist also z. B. \(\O \left (\left |\frac {1}{10}\right |^n\right )\), d. h. ungefähr eine Dezimalstelle pro Schritt.

Deflation: Sei eine \(n \times n\)-Matrix \(A\) gegeben. Ist \(\lambda \) ein Eigenwert von \(A\) mit einem Eigenvektor \(v\) der Form

\begin{align*} v = \begin{pmatrix}1 \\ u_1 \\ \vdots \\ u_{n-1}\end {pmatrix}, \text { dann gilt } \underbrace {\left (\begin{array}{c|ccc} 1 & 0 & \cdots & 0 \\ \hline & & & \\ -u & & E & \\ & & & \end {array}\right )}_{Q^{-1}} A \underbrace {\left (\begin{array}{c|ccc} 1 & 0 & \cdots & 0 \\ \hline & & & \\ u & & E & \\ & & & \end {array}\right )}_{Q} = \left (\begin{array}{c|ccc} \lambda & & A(1, 2:n) & \\ \hline 0 & & & \\ \vdots & & B & \\ 0 & & & \end {array}\right ), \end{align*} wobei \(B = A(2:n, 2:n) - u \cdot A(1, 2:n)\). Die restlichen Eigenwerte von \(A\) sind nun die Eigenwerte der Matrix \((n - 1) \times (n - 1)\)-Matrix \(B\).
Ist für alle Eigenvektoren \(v\) zu \(\lambda \) die erste Komponente \(0\), so wird die Deflation auf
\(\widetilde {A} = PAP\) angewandt, wobei \(P = P^{-1}\) ein Permutationsmatrix ist, die eine von \(0\) verschiedene Komponente von \(v\) mit der \(0\) in Position \(1\) vertauscht (diese gibt es, da Eigenvektoren immer ungleich Nullvektor sind).

Wielandt- und QR-Iteration

Wielandt-Iteration: Die Wielandt-Iteration ist eine Variante (Verbesserung) der von-Mises-Iteration. Dabei kann die Wielandt-Iteration beliebige Eigenwerte berechnen. Sie berechnet eine Folge von Approximationen zu einem Eigenwert \(\lambda \) und einem entsprechenden normierten Eigenvektor \(u\) einer Matrix \(A\). Dabei geht man von einer hinreichend guten Startnäherung \(\lambda _0\) und \(u_0\) (\(u_0\) kann auch zufällig gewählt sein) aus. Die Wielandt-Iteration konvergiert zu einem normierten Eigenvektor \(u\), der zum Eigenwert \(\lambda \) von \(A\) gehört, der am nächsten bei \(\lambda _0\) liegt.
Ein Iterationsschritt hat die Form

\begin{align*} \lambda _\ell = u_\ell ^t A u_\ell , \qquad v_\ell = (A - \lambda _\ell E)^{-1} u_\ell , \qquad u_{\ell + 1} = \frac {v_\ell }{\norm {v_\ell }_2}. \end{align*} In der Implementierung wird \(v_\ell \) als Lösung eines LGS berechnet. Für einen einfachen Eigenwert einer symmetrischen Matrix konvergiert die Iteration kubisch, d. h. \(\Delta _{\ell +1} \le c \Delta _\ell ^3\), wobei
\(\Delta _\ell = \max \{|\lambda _\ell - \lambda |, \norm {u_\ell - \sigma _\ell u}_2\}\) mit \(\sigma _\ell = \sgn (u_\ell ^t u)\).

QR-Iteration: Sei eine Matrix \(A\) in Hessenberg-Form gegeben. Die QR-Iteration approximiert einen Eigenwert von \(A\) mit Hilfe orthogonaler Ähnlichkeitstransformationen

\begin{align*} A_\ell \rightarrow A_{\ell +1} = Q_{\ell +1}^t A_\ell Q_\ell , \quad A_0 = A, \end{align*} wobei die Matrix \(Q_{\ell +1}\) durch die QR-Zerlegung

\[\begin {array}{c} A_\ell - \lambda _\ell E = Q_{\ell +1} R_{\ell +1}, \quad \lambda _\ell = \frac {d_+}{2} + \frac {\sigma }{2} \sqrt {d_-^2 + 4 A_\ell (n, n - 1) A_\ell (n - 1, n)},\\ d_\pm = A_\ell (n, n) \pm A_\ell (n - 1, n - 1), \quad \sigma = \begin {cases}1 & d_- \ge 0 \\ -1 & d_- < 0\end {cases} \end {array}\]

definiert wird. Dabei ist der Shift \(\lambda _\ell \) der am nächsten bei \(A_\ell (n, n)\) gelegene Eigenwert der \(2 \times 2\)-Untermatrix \(A_\ell (n - 1:n, n - 1:n)\) (man kann auch \(A_\ell (n, n)\) nehmen).

Die Null-Diagonalen der Hessenberg-Form bleiben bei der QR-Iteration erhalten. Ist \(A\) symmetrisch, so sind daher alle Matrizen \(A_\ell \) tridiagonal. Für \(\ell \to \infty \) geht der unterste nebendiagonale Eintrag \(A_\ell (n, n - 1)\) gegen \(0\), deswegen nähert sich \(A_\ell (n, n)\) einem Eigenwert \(\lambda \) von \(A\).
Ist \(A\) symmetrisch, so ist die Konvergenz kubisch.

Hat die Iteration konvergiert (d. h. ist der unterste nebendiagonale Eintrag von \(A_\ell \) innerhalb der Toleranz \(\approx 0\)), so wird das Verfahren auf die Untermatrix \(A_\ell (1 : n - 1, 1 : n - 1)\) angewandt. So können schließlich alle Eigenwerte von \(A\) berechnet werden.