Analysis of GMRES for Low-Rank and Small-Norm Perturbations of the Identity Matrix

In many applications, linear systems arise where the coefficient matrix takes the special form I + K + E, where I is the identity matrix of dimension n, rank(K) = p ≪ n, and ∥E∥ ≤ ϵ < 1. GMRES convergence rates for linear systems with coefficient matrices of the forms I+K and I+E are guaranteed by well-known theory, but only relatively weak convergence bounds specific to matrices of the form I + K + E currently exist. In this paper, we explore the convergence properties of linear systems with such coefficient matrices by considering the pseudospectrum of I + K. We derive a bound for the GMRES residual in terms of ϵ when approximately solving the linear system (I + K + E)x = b and identify the eigenvalues of I + K that are sensitive to perturbation. In particular, while a clustered spectrum away from the origin is often a good indicator of fast GMRES convergence, that convergence may be slow when some of those eigenvalues are ill-conditioned. We show there can be at most 2p eigenvalues of I + K that are sensitive to small perturbations. We present numerical results when using GMRES to solve a sequence of linear systems of the form (I + K_j + E_j)x_j = b_j that arise from the application of Broyden's method to solve a nonlinear partial differential equation.