power iteration

Concept

Convergent rate

where is eigenvalue having 2nd largest modulus

Limitations

• may not converge
• bad initial guess vector
• more than on eigenvector, so it will converge to linear combination of those two

Variants

normalized power iteration

Concept

where every iteration it been multiply by a matrix and normalized.
It’s goal is to find a eigenvector of .

Code

import numpy as np
 
def power_iter(A, num_iter, tol=1e-6):
	x_k = np.random.rand(A.shape[1])
	for _ in range(num_iter):
		y_k = np.dot(A, x_k)
		x_k_o = x_k
		x_k = y_k / np.linalg.norm(y_k)
		if np.linalg.norm(x_k - x_k_o) < tol:
			break
	return x_k

power iteration with Shift

in order to accelerate the convergence speed, we can pick a shift where and

everything else keep same. After all, you need to add shift into result.