Power Iteration

Find the dominant eigenvalue and eigenvector of a matrix with power iteration.

Multiply any vector by A again and again, and normalise it each time. The part of the vector along the eigenvector with the largest |eigenvalue| grows fastest, so the vector turns towards that eigenvector. PageRank and many large scale eigen solvers are built on this loop.

Start from v = ones(n) / sqrt(n). Repeat at most num_iters times:

w = A @ v
v_new = w / norm(w)

Stop early when norm(v_new - v) < tol. Then estimate the eigenvalue with the Rayleigh quotient v^T A v, since v has unit length.

An eigenvector is only defined up to sign. Return the one whose entry with the largest absolute value is positive.

Function signature

def power_iteration(A, num_iters=1000, tol=1e-10):

Example

Input

power_iteration(np.array([[2.0, 1.0], [1.0, 2.0]]))

Output

(3.0, array([0.70710678, 0.70710678]))

Reasoning

The eigenvalues of this matrix are 3 and 1. The start vector [0.707, 0.707] is already the eigenvector for 3, so one multiplication gives [2.121, 2.121], which normalises back to the same vector and stops the loop. The Rayleigh quotient is 3.

Constraints and notes

• A is square. You can assume its largest eigenvalue in absolute value is real, positive and strictly larger in absolute value than all the others.
• You can assume the start vector is not orthogonal to the dominant eigenvector.
• Do not call np.linalg.eig or np.linalg.eigh.