Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For a linear algebra class, we are currently learning about finding the largest/smallest eigenvalues of a matrix using the power method and inverse iteration methods. I just want to make sure that I am understand how this works because the notes I have are a little confusing. Here are the notes I have found on the power method.

Power Method:

  • So you begin with an approximation vector, and this can be just about anything nonzero(?).

  • Then you keep multiplying the approximation matrix by the vector for however many iterations, each time factoring some scalar out from your resulting vector. For example in this book they seem to always use the y component of the vector to factor out from each iterations results when getting the approximation, but how are they choosing that? Are they just arbitrarily picking something? This is the part I don't understand the most.

  • Finally after the approximation seems to approach some limiting numbers, those are the numbers that make up the dominant eigenvector, and you can use that to find the corresponding eigenvalues

Inverse Iteration

  • So as I understand it, this is exactly the same idea as power method except you subtract some number multiplied by the identity matrix from A, invert all of that, and that some number dictates that the approximated eigenvalue resulting from the algorithm will be the eigenvalue that is closest to whatever number you picked.

  • For example if I wanted the smallest eigenvalue, I would just set that number as 0, and the formula would be the exact same as power method except I multiply each iteration by the inverse of A rather than A. Am I understanding this correctly?

Sorry if my explanations or questions are bad; it's just that I had a hard time understanding it from class or reading the notes and I wanted some clarification.

Thanks!

share|improve this question
    
You are a tad confused. What you do with the power method is to take some random vector (or a good estimate, if you have one), and repeatedly multiply it by the matrix whose dominant eigenvector you're finding. The catch is that you have to periodically rescale the successive estimates of the eigenvector, lest you hit overflow. This rescaling is fine, since if $\mathbf x$ is an eigenvector of $\mathbf A$ corresponding to an eigenvalue $\lambda$, then $c\mathbf v$ for some nonzero scalar $c$ is an eigenvector corresponding to $\lambda$ as well. One customarily uses the max-norm for scaling. –  J. M. Dec 8 '11 at 9:16
    
For the second: what you formally have is shifted inverse iteration. The usual version takes the form $\mathbf A\mathbf x_{i+1}=c\mathbf x_i$. Mind you, one does not actually multiply by the inverse; one instead performs Gaussian elimination with some form of pivoting to obtain the next iterate. This works for finding the eigenvector corresponding to the smallest eigenvalue. The reason why we perform shifting is due to the fact that we can always shift the matrix we start with such that the eigenvector we want corresponds to the smallest eigenvalue of the new matrix. –  J. M. Dec 8 '11 at 9:26
    
Inverse iteration, in practice, is usually done only when you already have good eigenvalues, and you only want to find the corresponding eigenvectors. You might worry that $\mathbf A-c\mathbf I$ is (nearly) singular, and might spell trouble during the solution of the linear equations; this is in fact not a problem, and the (near-)singularity helps in converging to the eigenvector. See this article by Ilse Ipsen for more details. –  J. M. Dec 8 '11 at 9:31
    
To second J.M. first comment: the clue is, that in the approximation-vector only the ratio of its entries are relevant. Thus you can permanently divide by any scalar you like - by the iteration process that ratios approximate something constant - and once this is constant, then this is an eigenvector. The "length" of this vector (squareroot of squares of its entries) is completely irrelevant. –  Gottfried Helms Dec 9 '11 at 14:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.