Author(s) :
Petr Tichy
,
Jörg Liesen
Preprint series of the Institute of Mathematics, Technische Universität Berlin
Preprint 34-2006
MSC 2000
- 65F10 Iterative methods for linear systems
-
49K35 Minimax problems
Abstract :
Consider a system of linear algebraic equations with a nonsingular $n$ by $n$ matrix~$A$. When solving this system with GMRES, the relative residual norm at the step $k$ is bounded from above by the so called ideal GMRES approximation. This bound is sharp (it is attainable by the relative GMRES residual norm) in case of a normal matrix $A$, but it need not characterize the worst-case GMRES behavior if $A$ is nonnormal. In this paper we consider an $n$ by $n$ Jordan block $J$, and study the relation between ideal and worst-case GMRES as well as the problem of estimating the ideal GMRES approximations. Under some assumptions, we show that ideal and worst-case GMRES are identical at steps $k$ and $n-k$ such that $k$ divides $n$, and we derive explicit expressions for the $(n-k)$th ideal GMRES approximation. Furthermore, we extend previous results in the literature by proving new results about the radii of the polynomial numerical hulls of Jordan blocks. Using these, we discuss the tightness of the lower bound on the ideal GMRES approximation that is derived from the radius of the polynomial numerical hull of $J$.
Keywords :
Krylov subspace methods, GMRES convergence, polynomial numerical hull, Jordan block