RELATIONS BETWEEN GALERKIN AND NORM-MINIMIZING ITERATIVE METHODS FOR SOLVING LINEAR-SYSTEMS

Several iterative methods for solving linear systems Ax = b first cons truct a basis for a Krylov subspace and then use the basis vectors, to gether with the Hessenberg (or tridiagonal) matrix generated during th at construction, to obtain an approximate solution to the linear syste m. To determine the approximate solution, it is necessary to solve eit her a linear system with the Hessenberg matrix as coefficient matrix o r an extended Hessenberg least squares problem. In the first case, ref erred to as a Galerkin method, the residual is orthogonal to the Krylo v subspace, whereas in the second case, referred to as a norm-minimizi ng method, the residual (or a related quantity) is minimized over the Krylov subspace. Examples of such pairs include the full orthogonaliza tion method (FOM) (Arnoldi) and generalized minimal residual (GMRES) a lgorithms, the biconjugate gradient (BCG) and quasi-minimal residual ( QMR) algorithms, and their symmetric equivalents, the Lanczos and mini mal residual (MINRES) algorithms. A relationship between the solution of the linear system and that of the least squares problem is used to relate the residual norms in Galerkin processes to the norms of the qu antities minimized in the corresponding norm-minimizing processes. It is shown that when the norm-minimizing process is converging rapidly, the residual norms in the corresponding Galerkin process exhibit simil ar behavior, whereas when the norm-minimizing process is converging ve ry slowly, the residual norms in the corresponding Galerkin process ar e significantly larger. This is a generalization of the relationship e stablished between Arnoldi and GMRES residual norms in P. N. Brown, A theoretical comparison of the Arnoldi and GMRES algorithms, SIAM J. Sc i. Statist. Comput., 12, 1991, pp. 58-78. For MINRES and Lanczos, and for two nonsymmetric bidiagonalization procedures, we extend the argum ents to incorporate the effects of finite precision arithmetic.