0
$\begingroup$

In general it is a well established result that the Lanczos method, as a Krylov subspace method, can converge quadratically faster than the simple power method. In particular, the proof (using the Kaniel–Paige convergence theory) proceeds by demonstrating that the Krylov subspace which is formed by the iterative process form a subspace that is equivalent to a subspace of polynomials in the input matrix $A$. In many book, it suffices to show the existence of the Chebysev polynomials, i.e., the optimal polynomials (in terms of degree and approximation error) to give an upper bound on the convergence rates.

I was wondering, however, why this is sufficient? Is it because this shows that we Lanczos can be quadratically better (in principal) and that's what we want or am I missing something and this is proof that it does in general better? My interpretation is that indeed it does not always converge to this solution (since it might not "find" these optimal polynomials). Is this correct?

$\endgroup$
  • $\begingroup$ My rough understanding is that Krylov methods minimize the residual in the Krylov subspace, thus they perform at least as if the iterations go over any given set of polynomials. Thus, these methods perform not worse than chebyshev polynomials $\endgroup$ – VorKir Sep 8 '18 at 23:14
  • $\begingroup$ @VorKir, thanks for the thoughts, could you explain to me why the minimising the residual implies that the iterations go over any given set of polynomials and in particularly why they converge? Since in all proofs I have seen the convergence is always proven through usage of the optimal polynomials themselves? Perhaps I am missing something? $\endgroup$ – LeoW. Sep 8 '18 at 23:25
1
$\begingroup$

In many book, it suffices to show the existence of the Chebysev polynomials, i.e., the optimal polynomials (in terms of degree and approximation error) to give an upper bound on the convergence rates.

There is some confusion between approximation error and convergence rate I think. The reason why the Lanczos method is faster than the power method because it uses the Rayleigh quotient. Also, it is a separate idea. It technically uses the QR iteration which uses the QR iteration. There is a shift inside the QR for that.

When you cover this there is part on convergence for the power iteration. I'm going to write this briefly. The power iteration is like this.

enter image description here

Ok, now you can use this for the Lanczos. What we're doing is the following.

$$ c_{k}\lambda_{1}^{k}\bigg( a_{1}q_{1} + a_{2}(\frac{\lambda_{2}}{\lambda_{1}})^{k}q_{2} + \cdots + a_{m}(\frac{\lambda_{m}}{\lambda_{1}})^{k}q_{m} \bigg) \tag{2}$$

the reason this fails is because $\lambda_{2}$ is too close to $\lambda_{1}$ we're trying to approximate the first eigenvalue so it will take more iterations $k$ to get rid of it.

The difference between the next two algorithms is pretty subtle. The inverse iteration follows. enter image description here

The inverse iteration just makes the brilliant idea to subtract $\mu$ and invert right. That way if we are close then we won't have as many iterations. The next step is Rayleigh, it's essentially intuitive. I'm sorry for posting so many pictures but this is needed here.

enter image description here

Ok, the Rayleigh iteration simply approximates $\mu$ each step. The Chebyshev polynomials are used to form the basis for approximating error, however the power method typically only actually gets one eigenvalue. This is because the Chebyshev polynomials are the best approximation I believe.

The Lanczos iteration is making use of this as well as another algorithm called Arnoldi. The Lanczos algorithm is simply Arnoldi for symmetric matrices.

$\endgroup$
  • 1
    $\begingroup$ Yes, indeed! I got confused with convergence vs. error rate! :) Thanks for clarification! $\endgroup$ – LeoW. Sep 16 '18 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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