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.

I'm trying to obtain a general understanding of this algorithm which determines the k-largest eigenvalues of a matrix $A\in \mathbb{R}^{n\times n}$. How I see it:

power iteration:

  • take random starting vector $b \in \mathbb{R}^{1\times n}$
  • find $K_{n} = \begin{bmatrix}b & Ab & A^{2}b & \cdots & A^{n-1}b \end{bmatrix}.$
  • find orthogonal basis $Q_n$ of $K_{n}$ using Gramm-Schmidt (Numerically unstable)
  • n-th column vector of $Q_n$ is an approximation of n-th eigenvector of $A$ and corresponds to n-th largest eigenvalue $\lambda_n$ of $A$

Arnoldi Iteration:

Is a numerically stable implementation of power iteration.

  • take random starting vector $b \in \mathbb{R}^{1\times n}$

  • find first $q_1..q_n$ arnoldi vectors to form $Q_n$

    • $Q_n$ is an orthonormal basis of $K_n$
    • numerically stable Gramm-schmidt process is used
  • determine Hessenberg Matrix $H_n=Q_n^*AQ_n$
  • solve eig($H_n$) which is now simple because $H_n$ is a Hessenberg matrix, upper triangular, we can use the QR algorithm

Is this the general gist of it? A good, reliable link would already be great.

Any help would be greatly appreciated. Thank you.

share|improve this question
    
You've seen this, haven't you? –  J. M. Dec 23 '11 at 23:59
    
@J.M. No I haven't. Thank you. I will give it a read. –  Flying Swissman Dec 24 '11 at 9:15
1  
What are you expecting to see that isn't covered by Golub/Van Loan or Meurant or Saad? –  J. M. Dec 30 '11 at 3:33
2  
Saad's book is freely available –  Tapu Dec 30 '11 at 7:43
    
I don't want to buy a book. That's good news Tapu. I thought the suggested weren't free. –  Flying Swissman Dec 30 '11 at 12:18
show 2 more comments

1 Answer 1

There is a really good exposition of the Arnoldi Method given by Prof. Gilbert Strang in his Video lectures found in MIT Open Course Ware.

Here is the link to the lecture where he describes Arnoldi method:

http://ocw.mit.edu/courses/mathematics/18-086-mathematical-methods-for-engineers-ii-spring-2006/video-lectures/lecture-18-krylov-methods-multigrid-continued/

share|improve this answer
add comment

Your Answer

 
discard

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

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