文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 数学 > GMRES A generalized minimal residual algorithm for solving nonsymmetric linear systems
侵权投诉

GMRES A generalized minimal residual algorithm for solving nonsymmetric linear systems

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

GMRES A generalized minimal residual algorithm for solving nonsymmetric linear systems

第1页

你可能喜欢

热门文档

相关文档

  • krylov子空间法

    Schultz, GMRES a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comp., 7 (1986), pp. 856–869. N...

  • for

    Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Comp., 7, 856{869 (1986). H.A. Van ...

  • 免停滞的GMRESm算法研究

    (8条) 1.Sand Y.Schultz M H GMRES:A generalized minimal residual algorithm for solving nonsymmetric linear systems 1986 2.Jinxi Zhao The generalized ...

  • [25]M.D.Gunzburger,FiniteElementMethodsforViscousIn...

    H. Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7 (1986), pp. 856{...

  • 具有适当参数的再开始的GMRES算法

    具有适当参数的再开始的GMRES算法_理学_高等教育_教育专区。求解大型非对称线性...GMRES : A generalized minimal residual algorit hm for solving nonsymmetric ...

  • ...systems by quasi-minimal residual iterations_免...

    Schultz, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems , SIAM J. Sci. Statist. Comput. 7 (1986), 856{869. 22...

  • systems

    Schultz. GMRes: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput., 7:856{869, 1986. 6] Lu...

  • ProblemsfromDopant-Di usion Schmid,W.Hoppe,R.H.W._...

    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....

  • AIAA-J-Vol39No3-PlungingAirfoilZeroFreeStreamVeloci...

    H., “GMRES: a Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Problems,” SIAM Journal on Scienti c and Statistical Computing, Vol....

  • PRECORRECTED-FFT METHODS FOR ELECTROMAGNETIC ANALYS...

    Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Statist. Comput., 7 (1986), pp. 856{869...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email