Volume 26, pp. 453-473, 2007.

On worst-case GMRES, ideal GMRES, and the polynomial numerical hull of a Jordan block

Petr Tichý, Jörg Liesen, and Vance Faber

Abstract

When solving a linear algebraic system $Ax=b$ with GMRES, the relative residual norm at each step is bounded from above by the so-called ideal GMRES approximation. This worst-case bound is sharp (i.e. 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. Characterizing the tightness of this bound for nonnormal matrices~$A$ represents an important and largely open problem in the convergence analysis of Krylov subspace methods. In this paper we address this problem in case~$A$ is a single Jordan block. We study the relation between ideal and worst-case GMRES as well as the problem of estimating the ideal GMRES approximation. Furthermore, we prove new results about the radii of the polynomial numerical hulls of Jordan blocks. Using these, we discuss the closeness of the lower bound on the ideal GMRES approximation that is derived from the radius of the polynomial numerical hull.

Full Text (PDF) [354 KB], BibTeX

Key words

GMRES convergence, ideal GMRES, polynomial numerical hull, Jordan block.

AMS subject classifications

65F10, 65F35, 49K35.

Links to the cited ETNA articles

[5]	Vol. 18 (2004), pp. 81-90 Anne Greenbaum: Some theoretical results derived from polynomial numerical hulls of Jordan blocks