Convergence Bounds that Depend on the Right-Hand Side Vector

Jennifer Pestana^*, David Titley-Peloquin and Andrew Wathen

The GMRES algorithm of Saad and Schultz is one of the most popular matrix-free iterative methods for solving linear systems $Bx = b$ and $b\in\mathbb{C}^n$. This makes the description of its convergence an important topic of investigation. \newline Many convergence bounds start from the ideal GMRES problem, that separates the effect of the coefficient matrix from the right-hand side vector. In contrast, we present bounds for systems with $B\in\mathbb{C}^{n\times n}$ nonsingular and diagonalizable that explicitly include the right-hand side vector. We show that the GMRES residual norm satisfies a weighted polynomial least-squares problem on the spectrum of $B$, and that GMRES convergence reduces to an ideal GMRES problem on a rank-one modification of the diagonal matrix of eigenvalues of $B$. We present numerical experiments that show that these new bounds can accurately describe the convergence of GMRES.

Mathematics Subject Classification: 65F10

Keywords: GMRES; convergence analysis; iterative methods; linear systems; Krylov subspace methods

Minisymposion: Iterative Methods for Ill-Posed Problems