📘

Power Iteration for Dominant Eigenvector

Implement the power iteration algorithm to find the dominant eigenvector of a matrix.

Power iteration is an iterative algorithm for finding the eigenvector corresponding to the largest eigenvalue of a matrix. It's used in PageRank, PCA, and spectral clustering.

Algorithm:

Start with random vector $\mathbf{v}_0$
Iterate: $\mathbf{v}_{k+1} = \frac{A \mathbf{v}_k}{\|A \mathbf{v}_k\|}$
Converges when $\mathbf{v}_{k+1} \approx \mathbf{v}_k$

Convergence: The rate depends on $|\lambda_1/\lambda_2|$ - larger ratio means faster convergence.

After convergence, the dominant eigenvalue is: $\lambda_1 = \frac{\mathbf{v}^T A \mathbf{v}}{\mathbf{v}^T \mathbf{v}} = \mathbf{v}^T A \mathbf{v}$ (when $\mathbf{v}$ is normalized)

Example:

Input:

matrix = [[2, 1], [1, 2]]
max_iter = 100

Output:

{'eigenvector': [0.7071, 0.7071], 'eigenvalue': 3.0}

Reasoning:

Matrix analysis: The matrix [[2,1],[1,2]] has eigenvalues 3 and 1. Dominant eigenvalue: $\lambda_1 = 3$ Corresponding eigenvector: $[1, 1]$ (normalized: $[0.7071, 0.7071]$ )

Power iteration: Starting with $v_0 = [1, 0]$ (arbitrary):

Iteration 1: $Av_0 = [2, 1]$ , normalized: $[0.894, 0.447]$ Iteration 2: $Av_1 = [2.236, 1.789]$ , normalized: $[0.781, 0.625]$ ... Converges to $[0.7071, 0.7071]$

Eigenvalue: $v^T A v = [0.7071, 0.7071] \cdot [2.12, 2.12] = 3.0$

Constraints:

matrix: Square numpy array
max_iter: Maximum iterations (default 100)
tol: Convergence tolerance (default 1e-6)
Return: Dict with 'eigenvector' (unit norm) and 'eigenvalue'
Round to 4 decimal places

Editor

Python 3.13.1

Test Results

0/0

Run code to see test results.

📘