# Inverse power iteration and solving singular system

The algorithm for the inverse power iteration works as following : \begin{align} &v^{(0)} =\text{ some vector with }\|v^{(0)}\|=1\\ &\text{for }k = 1, 2, \ldots\\ &\qquad\text{Solve } (A - \mu I)w = v^{(k-1)}\text{ for }w\\ &\qquad v^{(k)}= w/\|w\|\\ &\qquad \lambda^{(k)} = (v^{(k)})^TAv^{(k)}\\ \end{align}

However, If we use the exact (or a very close) eigenvalue $$\mu$$ of the matrix $$A$$, wouldn't solving $$(A - \mu I)w = v^{(k-1)}$$ be impossible/ill-conditioned? How is this handled?

edit : for example $$\begin{bmatrix}2 & 1\\1 & 2\end{bmatrix}$$ has eigenvalues $$1$$ and $$3$$ but if we have as input $$\mu=1$$ or $$\mu=3$$ to the algorithm it would not work (julia script).

using LinearAlgebra

function invIter(A, n, mu)
v = [1;0]
lambda = 0
for k = 1:n
w = (A-mu*I)\v
v = w/norm(w)
lambda = v'*A*v
end
return lambda, v
end

A = [2 1;1 2]
lambda, v = invIter(A, 100, 1)
println("lambda, v are : ", lambda, v)


In practice the ill-conditioning does not matter in this application, because the perturbations to the computed solution $$w$$ caused by the ill-conditioning are in the direction of the eigenvector that you wish to find.
To better understand this, take an SVD $$A-\mu I = U\Sigma V^T$$, and assume $$\sigma_n \approx 0$$ and $$\sigma_n \ll \sigma_{n-1}$$. Then, the change in the solution of a linear system $$(A-\mu I)w = b$$ due to a perturbation $$b \to b+f$$ of small norm is $$(A-\mu I)^{-1}f = V\Sigma^{-1}U^Tf$$ and has a large component in the direction of $$v_n$$ (the last column of $$V$$ and smaller components in the orthogonal directions. However, $$(A-\mu I)v_n = U\Sigma e_n = u_n \sigma_n \approx 0$$, so $$v_n$$ is close to the eigenvector of $$A$$ with eigenvalue $$\mu$$.
• Thank you for the answer. I confess it is still not 100% clear but I am going te reread and reread the answer. Quick question : how can I assume $\sigma_n \ll\sigma_{n-1}$? Dec 14, 2022 at 15:17
• Good question -- it's not something that holds in general; I was analyzing that case in particular. If there is more than one singular value that is very small, then it means that $A$ is close to a matrix that has a double eigenvalue in $\mu$, and you have uncertainty in a subspace of larger dimension, but they are all close to eigenvectors. Dec 14, 2022 at 15:31