Thumbnail Image

GMRES convergence and the polynomial numerical hull for a Jordan block

Tichy, Petr; Liesen, Jörg

Inst. Mathematik

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$.