inverse iteration

Concept

$$A{y}_k=x_{k-1}$$ $$x_k=\frac{y_k}{||y_k|{|}_{\infty }}$$

which is equivalent to power iteration with $A^{-1}$.

Code

import numpy as np
 
def inverse_iteration(A, num_iter, tol=1e-6):
	x_k = np.random.rand(A.shape[1])
	for _ in range(num_iter):
		y_k = np.linalg.solve(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

Or we can also reuse LU factorization with Forward-backward substitution instead of linalg.solve.

Variants

with Shift

use $A^{\prime }=A-\sigma I$ for scalar $\sigma$.