6
$\begingroup$

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)
$\endgroup$

1 Answer 1

2
$\begingroup$

I don't have much detail here but I'm posting a quick answer because it seems one else steps in.

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$.

$\endgroup$
5
  • $\begingroup$ 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}$? $\endgroup$
    – edamondo
    Dec 14, 2022 at 15:17
  • $\begingroup$ 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. $\endgroup$ Dec 14, 2022 at 15:31
  • $\begingroup$ But just to be sure. Using the reverse power iteration with the exact eigenvalue as input would not work right (which is a bit frustrating)? (see the edit to my post) $\endgroup$
    – edamondo
    Dec 15, 2022 at 10:03
  • $\begingroup$ Also how do you deal in the case of the double eigenvalue in order to find both eigenvectors? $\endgroup$
    – edamondo
    Dec 15, 2022 at 10:06
  • $\begingroup$ No, it would not work, you are right. And in the case of a double eigenvalue v does not converge in the usual sense. $\endgroup$ Dec 15, 2022 at 10:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.