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 The Jacobi Algorithm
The Jacobi eigenvalue algorithm repeatedly applies orthogonal similarity transformations \[ \begin{align} \bA^{(k+1)} = \bG_k^T \bA^{(k)} \bG_k \end{align} \] to a symmetric matrix. Each rotation zeros one off-diagonal entry while preserving eigenvalues. As the off-diagonal entries converge to zero, \(\bA^{(k)}\) converges to a diagonal matrix whose diagonal entries are the eigenvalues.
Input: Symmetric matrix \(\bA\in\fR^{n\times n}\) and tolerance tol.\ Initialize: \(\bA^{(0)}=\bA\), \(\bV^{(0)}=\bI\).\ Repeat:
Choose an off-diagonal pivot \((p,q)\) with \(p<q\).
Compute \(c=\cos\theta\) and \(s=\sin\theta\) using the stable tangent formula so that \((\bG^T\bA^{(k)}\bG)_{pq}=0\).
Update the matrix by orthogonal similarity: \[ \begin{align} \bA^{(k+1)}=\bG^T\bA^{(k)}\bG. \end{align} \]
Accumulate eigenvectors: \[ \begin{align} \bV^{(k+1)}=\bV^{(k)}\bG. \end{align} \]
Stop: when \(\sigma_{\text{off}}(\bA^{(k)}) \leq `tol`\|\bA^{(k)}\|_F\).\ Output: Diagonal entries of \(\bA^{(k)}\) approximate eigenvalues; columns of \(\bV^{(k)}\) approximate eigenvectors.
(Pivot choices)
Classical Jacobi: choose the largest off-diagonal entry \(|A_{pq}|\).
Cyclic Jacobi: sweep through all pairs \((p,q)\) in a fixed order.
The largest-entry rule gives the clearest convergence proof. Cyclic sweeps are simpler to implement and often used in practice.
(Why eigenvectors accumulate) After \(k\) rotations, \[ \begin{align} \bA^{(k)} = (\bV^{(k)})^T \bA \bV^{(k)}. \end{align} \] If \(\bA^{(k)}\) is nearly diagonal, then \(\bA \bV^{(k)} \approx \bV^{(k)}\boldsymbol{\Lambda}\), so the columns of \(\bV^{(k)}\) are approximate eigenvectors of the original matrix.
20.3 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.