Article Sidebar
Main Article Content
Abstract
For iterative solution of symmetric systems the conjugate gradient method (CG) is commonly used when A is positive definite, while the minimum residual method (MINRES) is typically reserved for indefinite systems. We investigate the sequence of approximate solutions generated by each method and suggest that even if A is positive definite, MINRES may be preferable to CG if iterations are to be terminated early. In particular, we show for MINRES that the solution norms are monotonically increasing when A is positive definite (as was already known for CG), and the solution errors are monotonically decreasing. We also show that the backward errors for the MINRES iterates are monotonically decreasing.
Keywords
Article Details
References
- ARIOLI, M. 2004. A stopping criterion for the conjugate gradient algorithm in a finite element method framework. Numerical Mathematics, 97: 1-24.
- CHOI, S.-C. 2006. Iterative Methods for Singular Linear Equations and Least-Squares Problems. PhD thesis, Stanford University, Stanford, California, USA.
- CHOI, S.-C., PAIGE, C.C. and SAUNDERS, M.A. 2011. MINRES-QLP: a Krylov subspace method for indefinite or singular symmetric systems. SIAM J. Sci. Comput., 33: 1810-1836.
- CONN, A.R., GOULD, N.I.M. and TOINT, PH.L. 2000. Trust-Region Methods, vol. 1. SIAM, Philadelphia, USA.
- DAVIS, T.A. 2007. University of Florida Sparse Matrix Collection.
- http://www.cise.ufl.edu/research/sparse/matrices.
- DONGARRA, J.J., BUNCH, J.R., MOLER, C.B. and STEWART, G.W. 1979. LINPACK Users’ Guide. SIAM, Philadelphia, USA.
- FONG, D.C.-L. 2011. Minimum-Residual Methods for Sparse Least-Squares Using Golub-Kahan Bidiagonalization. PhD thesis, Stanford University, Stanford, California, USA.
- FONG, D.C.-L. and SAUNDERS, M.A. 2010. LSMR software for linear systems and least squares. http://www.stanford.edu/group/SOL/software.html.
- FONG, D.C.-L. and SAUNDERS, M.A. 2011. LSMR: An iterative algorithm for sparse least-squares problems. SIAM Journal on Scientific Computing, 33: 2950-2971.
- FREUND, R.W., GOLUB, G.H. and NACHTIGAL, N.M. 1992. Iterative solution of linear systems. Acta Numerica, 1: 57-100.
- GREENBAUM, A. 1997. Iterative Methods for Solving Linear Systems. SIAM, Philadelphia, USA.
- HESTENES, M.R. and STIEFEL, E. 1952. Methods of conjugate gradients for solving linear systems. Journal of Research of the National Bureau of Standards, 49: 409-436.
- HIGHAM, N.J. 2002. Accuracy and Stability of Numerical Algorithms. (second Edition) SIAM, Philadelphia, USA.
- LANCZOS, C. 1950. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, Journal of Research of the National Bureau of Standards, 45: 255-282.
- LUENBERGER, D.G. 1969. Hyperbolic pairs in the method of conjugate gradients. SIAM Journal on Applied Mathematics, 17: 1263-1267.
- LUENBERGER, D.G. 1970. The conjugate residual method for constrained minimization problems. SIAM Journal on Numerical Analysis, 7: 390-398.
- MEURANT, G.A. 2006. The Lanczos and Conjugate Gradient Algorithms: From Theory to Finite Precision Computations, vol. 19 of Software, Environments, and Tools, SIAM, Philadelphia, USA.
- PAIGE, C.C. and SAUNDERS, M.A. 1975. Solution of sparse indefinite systems of linear equations. SIAM Journal on Numerical Analysis, 12: 617-629.
- PAIGE, C.C. and SAUNDERS, M.A. 1982a. LSQR: An algorithm for sparse linear equations and sparse least squares. ACM Transactions on Mathematical Software, 8: 43-71.
- PAIGE, C.C. and SAUNDERS, M.A. 1982b. Algorithm 583; LSQR: Sparse linear equations and least-squares problems. ACM Transactions on Mathematical Software, 8: 195-209.
- STEIHAUG, T. 1983. The conjugate gradient method and trust regions in large scale optimization. SIAM Journal on Numerical Analysis, 20: 626-637.
- STEWART, G.W. 1977. Research, development and LINPACK, in Mathematical Software III, J.R. RICE, ed., Academic Press, New York, USA, 1-14.
- STIEFEL,E. 1955. Relaxationsmethoden bester strategie zur l¨osung linearer gleichungssysteme. Comm. Math. Helv., 29: 157-179.
- SUN, Y. 2003. The Filter Algorithm for Solving Large-Scale Eigenproblems from Accelerator Simulations. PhD thesis, Stanford University, Stanford, California, USA.
- TITLEY-PELOQUIN, D. 2010. Backward Perturbation Analysis of Least Squares Problems. PhD thesis, School of Computer Science, McGill University, Canada.
- TITLEY-PELOQUIN, D. 2011. Convergence of backward error bounds in LSQR and LSMR. Private communication.
- VAN DER VORST, H.A. 2003. Iterative Krylov Methods for Large Linear Systems. (1st Edition) Cambridge University Press, Cambridge, UK.
- WATKINS, D.S. 2010. Fundamentals of Matrix Computations. (3rd Edition) Pure and Applied Mathematics, Wiley, Hoboken, New Jersey, USA.
References
ARIOLI, M. 2004. A stopping criterion for the conjugate gradient algorithm in a finite element method framework. Numerical Mathematics, 97: 1-24.
CHOI, S.-C. 2006. Iterative Methods for Singular Linear Equations and Least-Squares Problems. PhD thesis, Stanford University, Stanford, California, USA.
CHOI, S.-C., PAIGE, C.C. and SAUNDERS, M.A. 2011. MINRES-QLP: a Krylov subspace method for indefinite or singular symmetric systems. SIAM J. Sci. Comput., 33: 1810-1836.
CONN, A.R., GOULD, N.I.M. and TOINT, PH.L. 2000. Trust-Region Methods, vol. 1. SIAM, Philadelphia, USA.
DAVIS, T.A. 2007. University of Florida Sparse Matrix Collection.
http://www.cise.ufl.edu/research/sparse/matrices.
DONGARRA, J.J., BUNCH, J.R., MOLER, C.B. and STEWART, G.W. 1979. LINPACK Users’ Guide. SIAM, Philadelphia, USA.
FONG, D.C.-L. 2011. Minimum-Residual Methods for Sparse Least-Squares Using Golub-Kahan Bidiagonalization. PhD thesis, Stanford University, Stanford, California, USA.
FONG, D.C.-L. and SAUNDERS, M.A. 2010. LSMR software for linear systems and least squares. http://www.stanford.edu/group/SOL/software.html.
FONG, D.C.-L. and SAUNDERS, M.A. 2011. LSMR: An iterative algorithm for sparse least-squares problems. SIAM Journal on Scientific Computing, 33: 2950-2971.
FREUND, R.W., GOLUB, G.H. and NACHTIGAL, N.M. 1992. Iterative solution of linear systems. Acta Numerica, 1: 57-100.
GREENBAUM, A. 1997. Iterative Methods for Solving Linear Systems. SIAM, Philadelphia, USA.
HESTENES, M.R. and STIEFEL, E. 1952. Methods of conjugate gradients for solving linear systems. Journal of Research of the National Bureau of Standards, 49: 409-436.
HIGHAM, N.J. 2002. Accuracy and Stability of Numerical Algorithms. (second Edition) SIAM, Philadelphia, USA.
LANCZOS, C. 1950. An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, Journal of Research of the National Bureau of Standards, 45: 255-282.
LUENBERGER, D.G. 1969. Hyperbolic pairs in the method of conjugate gradients. SIAM Journal on Applied Mathematics, 17: 1263-1267.
LUENBERGER, D.G. 1970. The conjugate residual method for constrained minimization problems. SIAM Journal on Numerical Analysis, 7: 390-398.
MEURANT, G.A. 2006. The Lanczos and Conjugate Gradient Algorithms: From Theory to Finite Precision Computations, vol. 19 of Software, Environments, and Tools, SIAM, Philadelphia, USA.
PAIGE, C.C. and SAUNDERS, M.A. 1975. Solution of sparse indefinite systems of linear equations. SIAM Journal on Numerical Analysis, 12: 617-629.
PAIGE, C.C. and SAUNDERS, M.A. 1982a. LSQR: An algorithm for sparse linear equations and sparse least squares. ACM Transactions on Mathematical Software, 8: 43-71.
PAIGE, C.C. and SAUNDERS, M.A. 1982b. Algorithm 583; LSQR: Sparse linear equations and least-squares problems. ACM Transactions on Mathematical Software, 8: 195-209.
STEIHAUG, T. 1983. The conjugate gradient method and trust regions in large scale optimization. SIAM Journal on Numerical Analysis, 20: 626-637.
STEWART, G.W. 1977. Research, development and LINPACK, in Mathematical Software III, J.R. RICE, ed., Academic Press, New York, USA, 1-14.
STIEFEL,E. 1955. Relaxationsmethoden bester strategie zur l¨osung linearer gleichungssysteme. Comm. Math. Helv., 29: 157-179.
SUN, Y. 2003. The Filter Algorithm for Solving Large-Scale Eigenproblems from Accelerator Simulations. PhD thesis, Stanford University, Stanford, California, USA.
TITLEY-PELOQUIN, D. 2010. Backward Perturbation Analysis of Least Squares Problems. PhD thesis, School of Computer Science, McGill University, Canada.
TITLEY-PELOQUIN, D. 2011. Convergence of backward error bounds in LSQR and LSMR. Private communication.
VAN DER VORST, H.A. 2003. Iterative Krylov Methods for Large Linear Systems. (1st Edition) Cambridge University Press, Cambridge, UK.
WATKINS, D.S. 2010. Fundamentals of Matrix Computations. (3rd Edition) Pure and Applied Mathematics, Wiley, Hoboken, New Jersey, USA.