The worst-case GMRES for normal matrices

Source file is available as :   Postscript Document

Author(s) : Jörg Liesen , Petr Tichy

Preprint series of the Institute of Mathematics, Technische Universität Berlin
Preprint 27-2003

MSC 2000

65F10 Iterative methods for linear systems
65F15 Eigenvalues, eigenvectors
65F20 Overdetermined systems, pseudoinverses
15A06 Linear equations
15A09 Matrix inversion, generalized inverses
15A18 Eigenvalues, singular values, and eigenvectors

Abstract :
We study the convergence of GMRES for linear algebraic systems with normal matrices. In particular, we explore the standard bound based on a min-max approximation problem on the discrete set of the matrix eigenvalues. We completely characterize the worst-case GMRES-related quantities in the next-to-last iteration step and evaluate the standard bound in terms of explicit polynomials involving the matrix eigenvalues. For a general iteration step, we develop a computable lower and upper bound on the standard bound. Our bounds allow to study the worst-case GMRES residual norm in dependence of the eigenvalue distribution. For hermitian matrices the lower bound is equal to the worst-case residual norm. In addition, numerical experiments show that the lower bound is generally very tight, and support our conjecture that it is to within a constant factor of the actual worst-case residual norm. Since the worst-case residual norm in each step is to within a factor of the square root of the matrix size to what is considered an ``average'' residual norm, our results are of relevance beyond the worst case.

Keywords : GMRES, evaluation of convergence, ideal GMRES, normal matrices, min-max problem