Author(s) :
Jörg Liesen
,
Petr Tichý
Preprint series of the Institute of Mathematics, Technische Universität Berlin
Preprint 282003
MSC 2000
 41A10 Approximation by polynomials

41A44 Best constants

41A50 Best approximation, Chebyshev systems

65F10 Iterative methods for linear systems
Abstract :
The worstcase residual norms of the GMRES method
for linear algebraic systems can, in case of
a normal matrix, be characterized by a minmax approximation
problem on the matrix eigenvalues. In our paper
"The worstcase GMRES for normal matrices" we derive
a lower bound on this minmax value (worstcase residual norm) for each step of the GMRES
iteration. We conjecture that the lower bound and the minmax
value agree up to a factor of $4/\pi$, i.e. that the lower bound
multiplied by $4/\pi$ represents an upper bound. In this paper we
prove for several different iteration steps that our conjecture
is true for a special set of eigenvalues, namely the roots of unity.
This case is of interest, since numerical experiments indicate that
the ratio of the minmax value and our lower bound is
maximal when the eigenvalues are the roots of unity.
Keywords :
minmax problem, polynomial approximation on discrete set, best approximation, best constants, GMRES, evaluation of convergence