2022/10/21 by Arielle Carr, Carr, Arielle K., Eric de Sturler +3 · 1 citation
Computer Science · Mathematics · #Matrix Theory and Algorithms #Holomorphic and Operator Theory #Advanced Topics in Algebra
paper · pdf · doi:10.48550/arxiv.2210.12053
In many applications, linear systems arise where the coefficient matrix takes the special form \bf I + \bf K + \bf E, where \bf I is the identity matrix of dimension n, \rm rank(\bf K) = p ≪ n, and ‖\bf E‖ ≤ ε< 1. GMRES convergence rates for linear systems with coefficient matrices of the forms \bf I + \bf K and \bf I + \bf E are guaranteed by well-known theory, but only relatively weak convergence bounds specific to matrices of the form \bf I + \bf K + \bf E currently exist. In this paper, we explore the convergence properties of linear systems with such coefficient matrices by considering the pseudospectrum of \bf I + \bf K. We derive a bound for the GMRES residual in terms of ε when approximately solving the linear system (\bf I + \bf K + \bf E)\bf x = \bf b and identify the eigenvalues of \bf I + \bf 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 \bf I + \bf K that are sensitive to small perturbations. We present numerical results when using GMRES to solve a sequence of linear systems of the form (\bf I + \bf Kj + \bf Ej)\bf xj = \bf bj that arise from the application of Broyden's method to solve a nonlinear partial differential equation.