Author(s) :
Jörg Liesen
,
Petr Tichy
Preprint series of the Institute of Mathematics, Technische Universität Berlin
Preprint 272003
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 minmax approximation problem on the discrete set of the matrix eigenvalues. We completely characterize the worstcase
GMRESrelated quantities in the nexttolast 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 worstcase GMRES residual norm in dependence of the eigenvalue distribution.
For hermitian matrices the lower bound is equal to the worstcase 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 worstcase residual norm.
Since the worstcase 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, minmax problem