Modified Gram-Schmidt, Least Squares and backward stability of Modified Gram-Schmidt - generalized minimum residual method

CHRISTOPHER C. PAIGE, MIROSLAV ROZLOZNIK, AND ZDENEK STRAKOS
Abstract. The generalized minimum residual method (GMRES) [Y. Saad and M. Schultz, SIAM
J. Sci. Statist. Comput., 7 (1986), pp. 856–869] for solving linear systems Ax = b is implemented
as a sequence of least squares problems involving Krylov subspaces of increasing dimensions. The
most usual implementation is Modified Gram-Schmidt GMRES (MGS-GMRES). Here we show that
MGS-GMRES is backward stable. The result depends on a more general result on the backward
stability of a variant of the MGS algorithm applied to solving a linear least squares problem, and uses
other new results on MGS and its loss of orthogonality, together with an important but neglected
condition number, and a relation between residual norms and certain singular values.