20 Jacobi Eigenvalue Algorithm
Iterative algorithm for symmetric matrices using plane rotations to zero off-diagonal entries.
20.1 Givens Rotations
\(G(p, q, \theta)\) is an identity matrix with a \(2 \times 2\) rotation block at \((p, p), (p, q), (q, p), (q, q)\).
Similarity Transform: \(\bA' = G^T \bA G\).
Effect: Modifies only rows/columns \(p\) and \(q\). Preserves eigenvalues (\(\bA'\) is orthogonally similar to \(\bA\)).
To set \(A'_{pq} = 0\), let \(\tau = (A_{qq} - A_{pp}) / (2A_{pq})\). The optimal tangent \(t = \tan\theta\) is: \[ \begin{align} t = \frac{\text{sign}(\tau)}{|\tau| + \sqrt{1 + \tau^2}}, \quad c = \frac{1}{\sqrt{1+t^2}}, \quad s = ct. \end{align} \] Choosing the smaller root \(|t| \leq 1\) ensures numerical stability and minimal perturbation.
20.2 Convergence and Cost
Let \(\sigma^2_{\text{off}}(\bA) = \sum_{p < q} A_{pq}^2\) be the Frobenius norm of the off-diagonal entries. Each rotation \(G(p, q, \theta)\) reduces this norm: \[ \begin{align} \sigma^2_{\text{off}}(\bA') = \sigma^2_{\text{off}}(\bA) - A_{pq}^2. \end{align} \] Convergence: Off-diagonals decrease monotonically. Convergence is ultimately quadratic (errors square each sweep).
The orthogonal transform \(\bA' = G^T\bA G\) preserves the Frobenius norm: \(\|\bA'\|_F^2 = \|\bA\|_F^2\). Let \(d(\bA) = \sum A_{ii}^2\) be the sum of squares of diagonal entries. Then: \[ \begin{align} \|\bA\|_F^2 = d(\bA) + 2\sigma_{\text{off}}^2(\bA). \end{align} \] A Jacobi rotation \(G(p,q,\theta)\) only affects rows and columns \(p\) and \(q\). For the \(2 \times 2\) submatrix at \(\{p,q\}\), the transformation is an eigendecomposition, so: \[ \begin{align} (A'_{pp})^2 + (A'_{qq})^2 &= A_{pp}^2 + A_{qq}^2 + 2A_{pq}^2 \\ d(\bA') &= d(\bA) + 2A_{pq}^2. \end{align} \] Substituting this into the norm conservation \(\|\bA'\|_F^2 = \|\bA\|_F^2\): \[ \begin{align} d(\bA') + 2\sigma_{\text{off}}^2(\bA') &= d(\bA) + 2\sigma_{\text{off}}^2(\bA) \\ (d(\bA) + 2A_{pq}^2) + 2\sigma_{\text{off}}^2(\bA') &= d(\bA) + 2\sigma_{\text{off}}^2(\bA) \\ \sigma_{\text{off}}^2(\bA') &= \sigma_{\text{off}}^2(\bA) - A_{pq}^2. \end{align} \] Thus each rotation reduces the off-diagonal mass by exactly \(A_{pq}^2\).
Performance vs. Accuracy:
Cost: \(O(n^3)\) per sweep. Typically 5–15 sweeps for convergence. More expensive than QR.
Accuracy: Unlike QR, Jacobi achieves high relative accuracy on small eigenvalues.
Apply one Jacobi rotation to zero \(A_{12}\) in \(\bA = \begin{pmatrix}2 & 1 \\ 1 & 3\end{pmatrix}\).
Show that after zeroing \(A_{pq}\), the new diagonal entries \(A'_{pp}\) and \(A'_{qq}\) are the eigenvalues of the \(2 \times 2\) submatrix at \(\{p, q\}\).
Perform one full cyclic sweep on \(\bA = \begin{pmatrix}1&1&0\\1&2&1\\0&1&3\end{pmatrix}\) by hand.