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

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.

Keywords

• Modified
• Gram-Schmidt
• Least
• Squares
• Backward
• Stability
• MGS-GMRES