/*======================================================================= ch08_shifted_inverse_iteration.cpp Find an eigenpair near a chosen shift by inverse iteration. Origin: C++ translation of ch08_shifted_inverse_iteration.f90 by Alexander Godunov. Each step solves (A-shift*I)*z=y and then normalizes z. Pivoted LU factors are computed once and reused. Example: A = [ 1 2 3; 2 2 -2; 3 -2 4 ], shift = 3.4. Eigenvalues are approximately -2.54138127, 3.54138127, and 6.00000000. The nearest eigenvalue to 3.4 is 3.54138127. A shift at an eigenvalue makes A-shift*I singular; a nearby shift can be ill-conditioned. The initial vector must have a component along the desired eigenvector. =======================================================================*/ #include #include #include #include #include #include using Matrix = std::vector>; void matrix_vector(const Matrix& a, const std::vector& v, std::vector& w); int lu_factor(Matrix& lu, std::vector& ipiv); void lu_solve(const Matrix& lu, const std::vector& ipiv, const std::vector& b, std::vector& z); int shifted_inverse(const Matrix& a, std::vector& y, double shift, double eps, int max_iter, double& lambda, int& iterations, double& residual, int& pivot_step); int main() { const Matrix a = {{1.0, 2.0, 3.0}, {2.0, 2.0, -2.0}, {3.0, -2.0, 4.0}}; std::vector y = {1.0, 1.0, 1.0}; const double shift = 3.4, eps = 1.0e-10; const int max_iter = 100; std::cout << "Shifted inverse iteration for one eigenpair\n" << "\nMatrix 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 << "\nInitial vector:"; for (double value : y) std::cout << std::setw(12) << value; std::cout << "\nShift = " << std::setw(12) << shift << "\nEigenpair residual tolerance = " << std::scientific << std::setprecision(4) << eps << '\n'; double lambda, residual; int iterations, pivot_step; const int info = shifted_inverse(a, y, shift, eps, max_iter, lambda, iterations, residual, pivot_step); if (info == 1) { std::cerr << "\nInvalid input: check symmetry, initial vector, and controls.\n"; return 1; } if (info == 2) { std::cerr << "\nA-shift*I is singular or nearly singular at pivot step " << pivot_step << ". Choose a different shift.\n"; return 1; } if (info == 3) { std::cerr << "\nThe inverse iteration vector is zero; cannot normalize.\n"; return 1; } std::cout << "\nEigenvalue near shift = " << std::fixed << std::setprecision(6) << std::setw(12) << lambda << '\n' << "Unit eigenvector:\n"; for (std::size_t i = 0; i < y.size(); ++i) std::cout << "y(" << i+1 << ") = " << std::setw(12) << y[i] << '\n'; std::cout << "Iterations = " << iterations << '\n' << "Eigenpair residual ||A*y-lambda*y|| = " << std::scientific << std::setprecision(4) << residual << '\n'; if (info == 4) { std::cerr << "Iteration limit reached before the tolerance was met.\n"; return 1; } return 0; } int shifted_inverse(const Matrix& a, std::vector& y, double shift, double eps, int max_iter, double& lambda, int& iterations, double& residual, int& pivot_step) /*======================================================================= Approximate the eigenvalue of a real symmetric A nearest shift. Input: a - square symmetric matrix, left unchanged y - nonzero starting vector, replaced by a unit vector shift - fixed estimate of the desired eigenvalue eps - positive tolerance for ||A*y-lambda*y||_2 max_iter - maximum number of inverse iterations Output: lambda - signed Rayleigh quotient y^T*A*y / (y^T*y) iterations - completed inverse iterations residual - Euclidean norm of the eigenpair residual pivot_step - one-based small-pivot step if return value is 2 Return value: 0 converged; 1 invalid input; 2 singular shifted matrix; 3 zero inverse vector; 4 iteration limit. Factor A-shift*I once and reuse its factors. The Rayleigh quotient and the residual use the ORIGINAL matrix A, not the shifted one. =======================================================================*/ { const int n = static_cast(y.size()); lambda = 0.0; residual = std::numeric_limits::infinity(); iterations = pivot_step = 0; if (n < 1 || static_cast(a.size()) != n || !(eps > 0.0) || max_iter < 1 || !std::isfinite(shift)) 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; double norm_y = 0.0; for (double value : y) norm_y += value*value; norm_y = std::sqrt(norm_y); if (norm_y == 0.0) return 1; for (double& value : y) value /= norm_y; Matrix lu = a; for (int i = 0; i < n; ++i) lu[i][i] -= shift; std::vector ipiv(n); pivot_step = lu_factor(lu, ipiv); if (pivot_step != 0) return 2; std::vector z(n), ay(n); for (int k = 1; k <= max_iter; ++k) { // Solve with the same LU factors at every step. lu_solve(lu, ipiv, y, z); double norm_z = 0.0; for (double value : z) norm_z += value*value; norm_z = std::sqrt(norm_z); if (norm_z == 0.0) return 3; for (int i = 0; i < n; ++i) y[i] = z[i]/norm_z; matrix_vector(a, y, ay); lambda = 0.0; for (int i = 0; i < n; ++i) lambda += y[i]*ay[i]; double residual_sq = 0.0; for (int i = 0; i < n; ++i) residual_sq += (ay[i]-lambda*y[i])*(ay[i]-lambda*y[i]); residual = std::sqrt(residual_sq); iterations = k; if (residual <= eps) return 0; } return 4; } int lu_factor(Matrix& lu, std::vector& ipiv) /*======================================================================= Factor B in place as P*B=L*U with partial row pivoting. Below-diagonal entries store L multipliers; diagonal and upper entries store U. ipiv[k] records the row swapped with k. Exchange entire rows, including multipliers from preceding columns. Return zero on success, or the one-based step of a small pivot. =======================================================================*/ { const int n = static_cast(lu.size()); double scale = 0.0; for (const auto& row : lu) for (double value : row) scale = std::max(scale, std::abs(value)); const double pivot_tol = 10.0*n*std::numeric_limits::epsilon()*scale; for (int k = 0; k < n; ++k) { int pivot_row = k; double best = std::abs(lu[k][k]); for (int i = k+1; i < n; ++i) { if (std::abs(lu[i][k]) > best) { best = std::abs(lu[i][k]); pivot_row = i; } } ipiv[k] = pivot_row; if (best <= pivot_tol) return k+1; if (pivot_row != k) std::swap(lu[k], lu[pivot_row]); for (int i = k+1; i < n; ++i) { lu[i][k] /= lu[k][k]; for (int j = k+1; j < n; ++j) lu[i][j] -= lu[i][k]*lu[k][j]; } } return 0; } void lu_solve(const Matrix& lu, const std::vector& ipiv, const std::vector& b, std::vector& z) /* Apply saved row swaps, then solve L*w=P*b and U*z=w. */ { const int n = static_cast(b.size()); z = b; for (int i = 0; i < n; ++i) if (ipiv[i] != i) std::swap(z[i], z[ipiv[i]]); for (int i = 0; i < n; ++i) for (int j = 0; j < i; ++j) z[i] -= lu[i][j]*z[j]; for (int i = n-1; i >= 0; --i) { for (int j = i+1; j < n; ++j) z[i] -= lu[i][j]*z[j]; z[i] /= lu[i][i]; } } void matrix_vector(const Matrix& a, const std::vector& v, std::vector& w) /* Form A*v explicitly, without a matrix library. */ { const int n = static_cast(v.size()); for (int i = 0; i < n; ++i) { w[i] = 0.0; for (int j = 0; j < n; ++j) w[i] += a[i][j]*v[j]; } }