4  Eigenwertberechnung

🏁 Ziel: Suche iterativ eine zu \(A=A_0\) ähnliche (gleiche Eigenwerte) Matrix \(A_k\), die wir mittels der QR-Zerlegung in eine obere Dreiecksmatrix \(R\) überführen können:

\[ A_k \to R = \begin{pmatrix} \lambda_1 & * & \cdots & * \\ & \lambda_2 & \ddots & \vdots \\ & & \ddots & * \\ & & & \lambda_N \end{pmatrix}, Q_k \to I_N \]

Somit lassen sich die Eigenwerte von \(A_k\) (\(k \to \infty\)) auf der Diagonalen ablesen (bzw. approximieren).

⚠️ Problem: Normale QR-Zerlegung mit \(A_{k+1} = R_k Q_k\) benötigt \(O(N^3)\) Operationen.

4.1 Hessenberg-Matrix

\[ H = \begin{pmatrix} * & * & * & * & * \\ * & * & * & * & * \\ 0 & * & * & * & * \\ 0 & 0 & * & * & * \\ 0 & 0 & 0 & * & * \end{pmatrix} \]

Eine Matrix \(H \in \mathbb{R}^{N \times N}\) heißt (obere) Hessenberg-Matrix, wenn \(H[n+2:N, n] = 0_{N-n-1}\) für \(n = 1,...,N-2\) gilt.

(4.3) Satz

Sei \(A \in \mathbb{R}^{N \times N}\). Dann existiert eine orthogonale Matrix \(Q \in \mathbb{R}^{N \times N}\), so dass \[ H = QAQ^{\top} \] eine Hessenberg-Matrix ist.

Die Berechnung von \(Q\) benötigt \(O(N^3)\) Operationen.

Berechnung der Hessenberg-Matrix
A = np.array([
    [8, 12/5, -9/5],
    [12/5, 109/25, 12/25],
    [-9/5, 12/25, 116/25]
])

print(H := scipy.linalg.hessenberg(A))

print(np.linalg.eig(A).eigenvalues)
print(np.linalg.eig(H).eigenvalues)
[[8 -3 0]
 [-3 4 0]
 [0 0 5]]
[2244241/233640 559439/233640 5]
[2244241/233640 559439/233640 5]

4.2 Inverse Iteration mit Shift

Sei \(A \in \mathbb{R}^{N \times N}\) symmetrisch.

  1. Wähle \(v^0 \in \mathbb{R}^N\) mit \(|v^0| = 1\).
    Setze \(k := 0\) und wähle \(\varepsilon > 0\).
  2. Berechne \[ \mu_k = r(A, v^k) = \frac{v^{\top} A v}{v^{\top} v}, \].
    Falls \(|Av^k - \mu_k v^k| < \varepsilon\): STOP.
  3. Berechne \[\begin{align*} w^k &= (A - \mu_k I_N)^{-1}v^k, \\ v^{k+1} &= \frac{1}{|w^k|}w^k. \end{align*}\]
  4. Setze \(k := k + 1\) und gehe zu 1..

\(r(A, w) \approx \lambda\)

4.3 QR-Iteration mit Shift

💡 Idee: Transformiere \(A\) auf ähnliche Hessenbergform und führe die QR-Zerlegung mit Shift in \(O(N^2)\) durch.

Im Folgenden sei \(A \in \mathbb{R}^{N \times N}\) symmetrisch, tridiagonal und irreduzibel (\(A\) kann z.B. eine Hessenberg-Matrix sein).

  1. Wähle \(\varepsilon \geq 0\), setze \(A_0 = A\), \(k := 0\) und \(n=N\).
  2. Falls \(|A_k[n, n-1]| \leq \varepsilon\)
    setze \(n := n - 1\),
    falls \(n = 1\): STOP
  3. Wähle \(\mu_k = A[n, n]\).
  4. Berechne eine QR-Zerlegung \(A_k - \mu_k I_N = Q_k R_k\).
  5. Setze
    \(A_{k+1} = R_k Q_k + \mu_k I_N\).
    Setze \(k := k + 1\), gehe zu 1.

Es gilt \[\begin{alignat*}{2} A_{k+1} &= R_k Q_k &&+ \mu_k I_N \\ &= Q_k^\top (A_k - \mu_k I_N) Q_k &&+ \mu_k I_N \\ &= Q_k^\top A_k Q_k \end{alignat*}\]