GMRES vs. Ideal GMRES
Kim-Chuan Toh · SIAM Journal on Matrix Analysis and Applications · 1997
The GMRES algorithm minimizes $ orm{p(A)b}$ over polynomials p of degree n normalized at $z=0$. The ideal GMRES problem is obtained if one considers minimization of $ orm{p(A)}$ instead. The ideal problem forms an upper bound for the worst-case true problem, where the GMRES norm $ orm{p_b(A)b}$ is maximized over b. In work not yet published, Faber, Joubert, Knill, and Manteuffel have shown that this upper bound need not be attained, constructing a $4 \times 4$ example in which the ratio of the true to ideal GMRES norms is $0.9999$. Here, we present a simpler $4 \times 4$ example in which the ratio approaches zero when a certain parameter tends to zero. The same example also leads to the same conclusion for Arnoldi vs. ideal Arnoldi norms.