13
$\begingroup$

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.

  • 0
    You've seen [this](http://books.google.com/books?hl=en&id=mlOa7wPX6OYC&pg=PA499), haven't you?2011-12-23
  • 0
    @J.M. No I haven't. Thank you. I will give it a read.2011-12-24
  • 1
    What are you expecting to see that isn't covered by Golub/Van Loan or [Meurant](http://books.google.com/books?hl=en&id=kvW1Q2CRJRQC) or [Saad](http://books.google.com/books?hl=en&id=FAkNAQAAIAAJ)?2011-12-30
  • 2
    Saad's book is freely [available](http://www-users.cs.umn.edu/~saad/books.html)2011-12-30
  • 0
    I don't want to buy a book. That's good news Tapu. I thought the suggested weren't free.2011-12-30
  • 0
    I take it that you've no access to a university library that might have these?2011-12-30
  • 0
    I'm currently in the wrong city to do that. But you are right, I should make more use of the uni library.2012-01-02

1 Answers 1