A GMRES Convergence Analysis for Localized Invariant Subspace Ill-Conditioning
Giulia Sacchi, Valeria Simoncini · SIAM Journal on Matrix Analysis and Applications · 2019
The Generalized Minimal RESidual (gmres) method is a well-established strategy for iteratively solving a large linear system $A x = b$, where $A\in\mathbb{R}^{n\times n}$ is a nonsymmetric and nonsingular coefficient matrix, and $b\in\mathbb{R}^n$. In the analysis of its convergence for $A$ diagonalizable, a much used upper bound for the relative residual norm involves a min-max polynomial problem over the set of eigenvalues of $A$, magnified by the condition number of the eigenvector matrix of $A$. This latter factor may cause a huge overestimation of the residual norm, making the bound nondescriptive in practice. We show that when a large condition number is caused by the almost linear dependence of a few of the eigenvectors, a more descriptive analysis of the method's behavior can be performed, irrespective of the location of the corresponding eigenvalues. The new analysis aims at capturing how the gmres polynomial deals with the ill-conditioning; as a by-product, a new upper bound for the gmres residual norm is obtained. A variety of numerical experiments illustrate our findings.