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

Abstract

We consider the convergence of the algorithm GMRES of Saad and Schultz for solving linear equations Bx=b, where B ∈ ℂ^{n × n} is nonsingular and diagonalizable, and b ∈ ℂⁿ. Our analysis explicitly includes the initial residual vector r₀. 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.

GMRES, convergence analysis, iterative methods, linear systems, Krylov subspace methods