Vo|.
SIAM J. ScI. STAT. COMPUT. 7, No. 3, July 1986
1986 Society for Industrial and Applied Mathematics 011
GMRES: A GENERALIZED MINIMAL RESIDUAL ALGORITHM FOR SOLVING NONSYMMETRIC LINEAR SYSTEMS* YOUCEF SAAD’ AND
MARTIN H. SCHULTZ"
Abstract. We present an iterative method for solving linear systems, which has the property of minimizing at every step the norm of the residual vector over a Krylov subspace. The algorithm is derived from the Arnoldi process for constructing an/2-orthogonal basis of Krylov subspaces. It can be considered as a generalization of Paige and Saunders’ MINRES algorithm and is theoretically equivalent to the Generalized Conjugate Residual (GCR) method and to ORTHODIR. The new algorithm presents several advantages
over GCR and ORTHODIR.
Key words, nonsymmetric systems, Krylor subspaces, conjugate gradient, descent methods, minimal residual methods AMS(MOS) subject classification. 65F
1. Introduction. One of the most effective iterative methods for solving large sparse symmetric positive definite linear systems of equations is a combination of the conjugate gradient method with some preconditioning technique[3],[8]. Moreover, several different generalizations of the conjugate gradient method have been presented in the recent years to deal with nonsymmetric problems[2],[9],[5],[4],[13],[14] and symmetric indefinite problems[10],[3],[11],[14]. For solving indefinite symmetric systems, Paige and Saunders[10] proposed an approach which exploits the relationship between the conjugate gradient method and the Lanczos method. In particular, it is known that the Lanczos method for solving the eigenvalue problem for an N x N matrix A is a Galerkin method onto the Krylov subspace Kk=- span{v1, AVl,""", Ak-lvl}, while the conjugate gradient method is a Galerkin method for solving the linear system Ax=f, onto the Krylov subspace Kk with v to/II roll. Thus, the Lanczos method computes the matrix representation Tk of the linear operator PkAII, the restriction of PkA to Kk, where Pk is the 12-0rthogonal projector onto Kk. The Galerkin method for Ax=f in Kk leads to solving a linear system with the matrix Tk which is tridiagonal if A is symmetric. In general, Tk is indefinite when A is and some stable direct method must be used to solve the corresponding tridiagonal Galerkin system. The basis of Paige and Saunders’ SYMMLQ algorithm is to use the stable LQ factorization of T. Paige and Saunders also showed that it is possible to formulate an algorithm called MINRES using the Lanczos basis to compute an approximate solution Xk which minimizes the residual norm over the Krylov subspace K. In the present paper we introduce and analyse a generalization of the MINRES algorithm for solving nonsymmetric linear systems. This generalization is based on the Arnoldi process 1], 12] which is an analogue of the Lanczos algorithm for nonsymmetric matrices. Instead of a tridiagonal matrix repregenting PkAIr, as is produced by
the Lanczos method for symmetric matrices, Arnoldi’s method produces an upper Hessenberg matrix. Using the 12-0rthonormal basis generated by the Arnoldi process, we will show that the approximate solution which minimizes the residual norm over Kk, is easily computed by a technique similar to that of Paige and Saunders. We call the resulting * Received by the editors November 29, 1983, and in revised form May 8, 1985. This work was supported by the Office of Naval Research under grant N000014-82-K-0184 and by the National Science Foundation under grant MCS-8106181. f Department of Computer Science, Yale University, New Haven, Connecticut 06520. 856

Schultz, GMRES a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comp., 7 (1986), pp. 856–869. N...
Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Comp., 7, 856{869 (1986). H.A. Van ...
(8条) 1.Sand Y.Schultz M H GMRES:A generalized minimal residual algorithm for solving nonsymmetric linear systems 1986 2.Jinxi Zhao The generalized ...
H. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7 (1986), pp. 856{...
具有适当参数的再开始的GMRES算法_理学_高等教育_教育专区。求解大型非对称线性...GMRES : A generalized minimal residual algorit hm for solving nonsymmetric ...
Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems , SIAM J. Sci. Statist. Comput. 7 (1986), 856{869. 22...
Schultz. GMRes: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput., 7:856{869, 1986. 6] Lu...
80, 489-497 (1989) 8] Y.Saad and M.H.Shultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J.Sci....
H., “GMRES: a Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Problems,” SIAM Journal on Scienti c and Statistical Computing, Vol....
Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7 (1986), pp. 856{869...
热门文档