Power Iteration

Problem

Estimate the leading eigenvector of a symmetric matrix A with power iteration.

Start from the unit vector with all entries 1/sqrt(n), repeatedly set v = A v and renormalize to unit length num_iters times. Return [eigenvector, rayleigh] where rayleigh = v^T A v. If A v becomes the zero vector, stop and return the current vector with 0.0. Empty A returns [[], 0.0].

Hint

Multiply by A, divide by the vector norm, and after the loop compute v^T A v.

Test cases

case 1

in: [[[2,0],[0,1]],50]

expected: [[1,8.881784197001252e-16],2]

case 2

in: [[[4,1],[1,3]],100]

expected: [[0.85065080835204,0.5257311121191337],4.618033988749896]

case 3

in: [[[2,1],[1,2]],10]

expected: [[0.7071067811865475,0.7071067811865475],2.9999999999999996]

case 4

in: [[[1,0,0],[0,1,0],[0,0,1]],5]

expected: [[0.5773502691896258,0.5773502691896258,0.5773502691896258],1.0000000000000002]

Starter codePython

def power_iteration(A, num_iters):
    # Returns [eigenvector, rayleigh_quotient]
    # Your code here
    pass

4 test cases · run your code against them in the editor