[Math] Power method for finding all eigenvectors

eigenvalues-eigenvectorsmatricesnumerical linear algebrapositive definitesymmetric matrices

This is my homework. I was asked to find all eigenvectors of a symmetric and positive definite matrix by inverse power method with shifted. I encountered three problems:

  1. The eigenvalues to the matrix may not be distinct. In this case, how to find all eigenvectors corresponding to one eigenvalue?

  2. By the inverse power method, I can find the smallest eigenvalue and eigenvector. However, it seems the inverse power method with deflation does not work for finding other eigenvalues. I think the reason is the deflation shift the largest eigenvalue to zero, and after I inverse the matrix, this eigenvalue goes to infinity and therefore it is impossible to find an infinite large eigenvalue. How to modified power method with deflation in the inverse case?

  3. How to use power method with deflation to find all eigenvector? I can find the largest (power method) and second largest (power method with deflation). My question is how to construct the "modifed matrix", i.e. $B = A$ minus some modifying term?

$${}$$

Best Answer

Since the matrix is symmetric, there exists an orthogonal basis of eigenvectors. Once you have found an eigenvector, extend it to an orthogonal basis, rewrite the matrix in terms of this basis and restrict to the orthogonal space of the known eigenvector.

This is comprised in the method of deflation: You first find the first eigenvector $v_1$ (with a maximal $\lambda_1$), by iterating $x_{n+1}=\frac{Ax_n}{|Ax_n|}$ with a "random" initial $x_0$. Once you have found a good approximation for $v_1$, you consider $B=A-\frac{\lambda_1}{|v_1|^2}v_1v_1^T$ (this simple step replaces the "rewrite in terms of this basis" above). This is a matrix that behaves like $A$ for anything orthogonal to $v_1$ and zeroes out $v_1$. Use the power method on $B$ again, which will reveal $v_2$, an eigenvector of a largest eigenvalue of $B$. Then switch to $C=B-\frac{\lambda_2}{|v_2|^2}v_2v_2^T$ and so on. For the sake of numerical stability, it may be better not to actually use the matrices $B,C,$ etc., but instead to implement these linear maps as "apply $A$ and then make the result orthogonal to $v_1,v_2,\ldots$".

Related Question