GMRES convergence bounds that depend on the right-hand-side vector

We consider the convergence of the algorithm GMRES of Saad and Schultz for solving linear equations Bx=b, where B ∈ Cn × n is nonsingular and diagonalizable, and b ∈ Cn. Our analysis explicitly includes the initial residual vector r0. 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-1 modification of the diagonal matrix of eigenvalues of B. Numerical experiments show that the new bounds can accurately describe GMRES convergence. © The authors 2013.