"""ch08_power_method.py Find the dominant eigenvalue and eigenvector by the power method. Origin: Python translation of ch08_power_method.f90 by Alexander Godunov, based on Power.f90. The iteration y <- A*y / ||A*y|| is retained. A signed Rayleigh quotient estimates the eigenvalue, and the eigenpair residual tests convergence. Example: A = [ 1 2 3; 2 2 -2; 3 -2 4 ], y0 = [ 1, 1, 1 ]. Its eigenvalues are approximately -2.54138127, 3.54138127, and 6.00000000. The dominant eigenvalue in magnitude is 6. The method finds one eigenpair. It generally requires a unique dominant eigenvalue in magnitude and an initial vector with a nonzero component along its eigenvector. A small change in the eigenvalue estimate alone does not verify the eigenvector. """ from math import sqrt def main(): """Run the three-dimensional example and print the eigenpair.""" a = [[1.0, 2.0, 3.0], [2.0, 2.0, -2.0], [3.0, -2.0, 4.0]] y = [1.0, 1.0, 1.0] eps = 1.0e-7 max_iter = 1000 print("Power method for the dominant eigenpair") print("\nMatrix A:") for row in a: print("".join(f"{value:12.6f}" for value in row)) print("\nInitial vector:" + "".join(f"{value:12.6f}" for value in y)) print(f"Residual tolerance = {eps:.4e}") y, eigenvalue, iterations, residual, info = power_method( a, y, eps, max_iter) if info == 1: raise ValueError("Invalid input: check the initial vector and controls") if info == 2: raise ArithmeticError("A*y is zero; the iteration cannot be normalized") print(f"\nDominant eigenvalue = {eigenvalue:12.6f}") print("Unit eigenvector:") for i, value in enumerate(y, start=1): print(f"y({i}) = {value:12.6f}") print(f"Iterations = {iterations}") print(f"Eigenpair residual ||A*y-lambda*y|| = {residual:.4e}") if info == 3: raise ArithmeticError("Iteration limit reached before the tolerance was met") def power_method(a, y, eps, max_iter): """Approximate the eigenpair of largest eigenvalue magnitude. Input: a - square real matrix, left unchanged y - nonzero initial vector, left unchanged eps - positive tolerance for the eigenpair residual max_iter - maximum number of normalized power iterations Output: y - unit vector approximating an eigenvector eigenvalue - signed Rayleigh quotient y^T*A*y / (y^T*y) iterations - completed power iterations residual - Euclidean norm of A*y - eigenvalue*y info - 0 if residual <= eps; 1 for invalid input; 2 if A*y is zero; 3 at the iteration limit Normalize the initial vector. Repeatedly multiply by A and normalize as in Power.f90. The quotient retains the sign of a negative dominant eigenvalue. A small residual verifies an eigenpair but cannot establish dominance if the starting vector misses the dominant eigendirection. """ eigenvalue = 0.0 iterations = 0 residual = float("inf") n = len(y) if (n == 0 or len(a) != n or any(len(row) != n for row in a) or eps <= 0.0 or max_iter < 1): return y.copy(), eigenvalue, iterations, residual, 1 y = y.copy() # An eigenvector has no preferred length, so start with ||y|| = 1. norm_y = sqrt(sum(value*value for value in y)) if norm_y == 0.0: return y, eigenvalue, iterations, residual, 1 y = [value/norm_y for value in y] for k in range(1, max_iter+1): # Power step: multiply by A, then normalize to prevent growth. z = matrix_vector(a, y) norm_z = sqrt(sum(value*value for value in z)) if norm_z == 0.0: return y, eigenvalue, iterations, residual, 2 y = [value/norm_z for value in z] # Estimate the signed eigenvalue for this normalized vector. ay = matrix_vector(a, y) eigenvalue = sum(y[i]*ay[i] for i in range(n)) # Check the full eigenpair, not only the change in eigenvalue. residual = sqrt(sum((ay[i]-eigenvalue*y[i])**2 for i in range(n))) iterations = k if residual <= eps: return y, eigenvalue, iterations, residual, 0 return y, eigenvalue, iterations, residual, 3 def matrix_vector(a, v): """Compute A*v explicitly, without calling a matrix library.""" n = len(v) w = [0.0] * n for i in range(n): for j in range(n): w[i] += a[i][j]*v[j] return w if __name__ == "__main__": main()