Convergence of Laczos method

Question

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?

Answer 1

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.

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.

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.

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.