Properties of Worst-Case GMRES

DOI10.1137/13091066XMaRDI QIDQ5413659zbMATH OpenFDO

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

Publication date 30 April 2014

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.5535

zbMATH Keywords

cross equalitygeneralized minimal residual (GMRES) methodGMRES iterative methodideal GMRESmatrix approximation problemsminmax characterizationworst-case convergenceworst-case GMRES polynomialsworst-case initial vectors

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10)

Abstract: Given a matrix $A$ and iteration step $k$, we study a best possible attainable upper bound on the GMRES residual norm that does not depend on the initial vector $b$. This quantity is called the worst-case GMRES approximation. We show that the worst case behavior of GMRES for the matrices $A$ and $A^T$ is the same, and we analyze properties of initial vectors for which the worst-case residual norm is attained. In particular, we show that such vectors satisfy a certain "cross equality", and we characterize them as right singular vectors of the corresponding GMRES residual matrix. We show that the worst-case GMRES polynomial may not be uniquely determined, and we consider the relation between the worst-case and the ideal GMRES approximations, giving new examples in which the inequality between the two quantities is sharp at all iteration steps $kgeq3$. Finally, we give a complete characterization of how the values of the approximation problems in the context of worst-case and ideal GMRES for a real matrix change, when one considers complex (rather than real) polynomials and initial vectors in these problems.

Recommendations

• Expressions and bounds for the GMRES residual
• Prescribing the behavior of early terminating GMRES and Arnoldi iterations
• GMRES convergence bounds that depend on the right-hand-side vector
• The superlinear convergence behaviour of GMRES
• The worst-case GMRES for normal matrices
• scientific article; zbMATH DE number 2154408
• Computable Convergence Bounds for GMRES
• A note on the convergence behavior of GMRES
• Some Remarks on the Elman Estimate for GMRES
• Convergence in Backward Error of Relaxed GMRES

Cited in

(9)

• The worst-case GMRES for normal matrices
• GMRES algorithms over 35 years
• The coefficients of the FOM and GMRES residual polynomials
• GMRES vs. Ideal GMRES
• On the Forsythe conjecture
• Towards understanding CG and GMRES through examples
• GMRES, pseudospectra, and Crouzeix's conjecture for shifted and scaled Ginibre matrices
• Matrix best approximation in the spectral norm
• On worst-case GMRES, ideal GMRES, and the polynomial numerical hull of a Jordan block

This page was built for publication: Properties of Worst-Case GMRES

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5413659)