power iteration

Concept

$$b_{k+1}=A{b}_k$$

Convergent rate

$$\frac{{\lambda }_2}{{\lambda }_1}$$

where ${\lambda }_2$ 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

$$y_k=A{x}_{k-1}$$ $$x_k=\frac{y_k}{||y_k|{|}_{\infty }}$$

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

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 $\sigma$ where $A^{\prime }=A-\sigma I$ and

$$\frac{{\lambda }_2-\sigma }{{\lambda }_1-\sigma }<\frac{{\lambda }_2}{{\lambda }_1}$$

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