Modified Gram-Schmidt (MGS), Least Squares, and Backward Stability of MGS-GMRES

• ID: 2340, RIV: 10032007
• ISSN: 0895-4798, ISBN: not specified
• source: SIAM Journal on Matrix Analysis and Applications
• keywords: Modified; Gram-Schmidt; Least; Squares; Backward; Stability; MGS-GMRES
• authors: Zdeněk Strakoš
• authors from KNM: Strakoš Zdeněk

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.