/*======================================================================= ch08_jacobi_eigen.cpp Find all eigenvalues and eigenvectors of a real symmetric matrix. Origin: C++ translation of ch08_jacobi_eigen.f90 by Alexander Godunov, based on Jacobi.f90 (December 2009). The cyclic, thresholded Jacobi rotations and the original formulas for c and s are retained. Example: A = [ 1 2 3; 2 2 -2; 3 -2 4 ]. Its eigenvalues are approximately -2.54138127, 3.54138127, and 6.00000000. Columns of X correspond to eigenvalues on the diagonal of the transformed matrix, in the order produced by Jacobi. Eigenvectors may differ by an overall sign. This method is useful for small symmetric matrices; use library routines for larger problems. =======================================================================*/ #include #include #include #include #include #include using Matrix = std::vector>; int jacobi(Matrix& a, Matrix& x, double abserr, int max_sweeps, int& sweeps, int& rotations, double& offdiag_norm); int main() { const Matrix a = {{1.0, 2.0, 3.0}, {2.0, 2.0, -2.0}, {3.0, -2.0, 4.0}}; const int n = static_cast(a.size()); // The tolerance bounds the SUM OF SQUARED off-diagonal entries. const double abserr = 1.0e-18; const int max_sweeps = 100; std::cout << "Eigenvalues and eigenvectors (Jacobi method)\n" << "\nOriginal symmetric matrix A:\n" << std::fixed << std::setprecision(6); for (const auto& row : a) { for (double value : row) std::cout << std::setw(12) << value; std::cout << '\n'; } std::cout << "Squared off-diagonal tolerance = " << std::scientific << std::setprecision(4) << abserr << '\n'; // Jacobi changes its matrix, so preserve A for an independent check. Matrix a_work = a, x; int sweeps, rotations; double offdiag_norm; const int info = jacobi(a_work, x, abserr, max_sweeps, sweeps, rotations, offdiag_norm); if (info == 1) { std::cerr << "\nInvalid input: A must be symmetric and controls positive.\n"; return 1; } std::cout << "\nEigenvalues and corresponding unit eigenvectors:\n" << std::fixed << std::setprecision(6); for (int j = 0; j < n; ++j) { std::cout << "lambda(" << j + 1 << ") = " << std::setw(12) << a_work[j][j] << '\n'; for (int i = 0; i < n; ++i) std::cout << " v(" << i + 1 << ") = " << std::setw(12) << x[i][j] << '\n'; } // Check A*X-X*D and X^T*X-I, using the original A. double max_residual = 0.0, max_orthogonality = 0.0; for (int j = 0; j < n; ++j) { for (int i = 0; i < n; ++i) { double value = 0.0; for (int k = 0; k < n; ++k) value += a[i][k] * x[k][j]; max_residual = std::max(max_residual, std::abs(value - a_work[j][j]*x[i][j])); value = 0.0; for (int k = 0; k < n; ++k) value += x[k][i] * x[k][j]; max_orthogonality = std::max(max_orthogonality, std::abs(value - (i == j ? 1.0 : 0.0))); } } std::cout << "\nSweeps = " << sweeps << '\n' << "Rotations = " << rotations << '\n' << "Off-diagonal norm of final matrix = " << std::scientific << std::setprecision(4) << offdiag_norm << '\n' << "Maximum |A*X-X*D| component = " << max_residual << '\n' << "Maximum |X^T*X-I| component = " << max_orthogonality << '\n'; if (info == 2) { std::cerr << "Sweep limit reached before the tolerance was met.\n"; return 1; } return 0; } int jacobi(Matrix& a, Matrix& x, double abserr, int max_sweeps, int& sweeps, int& rotations, double& offdiag_norm) /*======================================================================= Diagonalize a small real symmetric matrix by Jacobi rotations. Input/output: a - square symmetric matrix, overwritten by a nearly diagonal similar matrix with eigenvalues on its diagonal Output: x - orthonormal eigenvectors in columns sweeps - completed passes over all off-diagonal pairs rotations - number of rotations performed offdiag_norm - square root of the sum of off-diagonal squares Return value: 0 converged; 1 invalid input; 2 sweep limit reached. Controls: abserr - positive bound on SUM of squared off-diagonal entries max_sweeps - positive maximum number of complete passes Start X as the identity. For each pair above the threshold, rotate rows and columns of A and columns of X. Orthogonal similarity preserves eigenvalues. Recompute the actual off-diagonal sum at the start of each sweep to avoid accumulated bookkeeping roundoff. The c and s formulas follow the original Jacobi.f90. =======================================================================*/ { const int n = static_cast(a.size()); sweeps = rotations = 0; offdiag_norm = std::numeric_limits::infinity(); if (n == 0 || !(abserr > 0.0) || max_sweeps < 1) return 1; for (const auto& row : a) if (static_cast(row.size()) != n) return 1; for (int i = 0; i < n; ++i) for (int j = i+1; j < n; ++j) if (a[i][j] != a[j][i]) return 1; x.assign(n, std::vector(n, 0.0)); for (int i = 0; i < n; ++i) x[i][i] = 1.0; while (true) { // Measure the actual off-diagonal entries at each sweep. double b2 = 0.0; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (i != j) b2 += a[i][j]*a[i][j]; offdiag_norm = std::sqrt(b2); if (b2 <= abserr) return 0; if (sweeps >= max_sweeps) return 2; // Half the mean off-diagonal square sets the skip threshold. double bar = 0.5*b2 / (n*n); for (int i = 0; i < n-1; ++i) { for (int j = i+1; j < n; ++j) { if (a[j][i]*a[j][i] <= bar) continue; b2 = std::max(0.0, b2 - 2.0*a[j][i]*a[j][i]); bar = 0.5*b2 / (n*n); // Same angle selection as Jacobi.f90. const double beta = (a[j][j]-a[i][i])/(2.0*a[j][i]); const double coeff = 0.5*beta/std::sqrt(1.0+beta*beta); const double s = std::sqrt(std::max(0.5+coeff, 0.0)); const double c = std::sqrt(std::max(0.5-coeff, 0.0)); // Rotate rows i and j of A. for (int k = 0; k < n; ++k) { const double cs = c*a[i][k] + s*a[j][k]; const double sc = -s*a[i][k] + c*a[j][k]; a[i][k] = cs; a[j][k] = sc; } // Rotate columns i and j of A and X. for (int k = 0; k < n; ++k) { double cs = c*a[k][i] + s*a[k][j]; double sc = -s*a[k][i] + c*a[k][j]; a[k][i] = cs; a[k][j] = sc; cs = c*x[k][i] + s*x[k][j]; sc = -s*x[k][i] + c*x[k][j]; x[k][i] = cs; x[k][j] = sc; } ++rotations; } } ++sweeps; } }