zbMATH — the first resource for mathematics

The idea behind Krylov methods. (English) Zbl 0982.65034
Introduction: We explain why Krylov methods make sense, and why it is natural to represent a solution to a linear system as a member of a Krylov space. In particular, we show that the solution to a nonsingular linear system \(Ax= b\) lies in a Krylov space whose dimension is the degree of the minimal polynomial of \(A\). Therefore, if the minimal polynomial of \(A\) has low degree then the space in which a Krylov method searches for the solution can be small. In this case a Krylov method has the opportunity to converge fast.
When the matrix is singular, however, Krylov methods can fail. Even if the linear system does have a solution, it may not lie in a Krylov space. In this case we describe a class of right-hand sides for which a solution lies in a Krylov space. As it happens, there is only a single solution that lies in a Krylov space, and it can be obtained from the Drazin inverse.
Our discussion demonstrates that eigenvalues play a central role when it comes to ensuring existence and uniqueness of Krylov solutions; they are not merely an artifact of convergence analyses.

65F10 Iterative numerical methods for linear systems
65F20 Numerical solutions to overdetermined systems, pseudoinverses
Full Text: DOI