Article Sidebar

Submitted
Apr 26, 2017
Published
Apr 1, 2012
Download
PDF
Statistic
Read Counter : 755 Download : 593

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

Conjugate gradient method (CG) Conjugate residual method (CR) Iterative method Krylov subspace method Linear equations Minimum residual method (MINRES) Sparse matrix Trust-region method.

Article Details

References

  1. ARIOLI, M. 2004. A stopping criterion for the conjugate gradient algorithm in a finite element method framework. Numerical Mathematics, 97: 1-24.
  2. CHOI, S.-C. 2006. Iterative Methods for Singular Linear Equations and Least-Squares Problems. PhD thesis, Stanford University, Stanford, California, USA.
  3. 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.
  4. CONN, A.R., GOULD, N.I.M. and TOINT, PH.L. 2000. Trust-Region Methods, vol. 1. SIAM, Philadelphia, USA.
  5. DAVIS, T.A. 2007. University of Florida Sparse Matrix Collection.
  6. http://www.cise.ufl.edu/research/sparse/matrices.
  7. DONGARRA, J.J., BUNCH, J.R., MOLER, C.B. and STEWART, G.W. 1979. LINPACK Users’ Guide. SIAM, Philadelphia, USA.
  8. FONG, D.C.-L. 2011. Minimum-Residual Methods for Sparse Least-Squares Using Golub-Kahan Bidiagonalization. PhD thesis, Stanford University, Stanford, California, USA.
  9. 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.
  10. 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.
  11. FREUND, R.W., GOLUB, G.H. and NACHTIGAL, N.M. 1992. Iterative solution of linear systems. Acta Numerica, 1: 57-100.
  12. GREENBAUM, A. 1997. Iterative Methods for Solving Linear Systems. SIAM, Philadelphia, USA.
  13. 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.
  14. HIGHAM, N.J. 2002. Accuracy and Stability of Numerical Algorithms. (second Edition) SIAM, Philadelphia, USA.
  15. 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.
  16. LUENBERGER, D.G. 1969. Hyperbolic pairs in the method of conjugate gradients. SIAM Journal on Applied Mathematics, 17: 1263-1267.
  17. LUENBERGER, D.G. 1970. The conjugate residual method for constrained minimization problems. SIAM Journal on Numerical Analysis, 7: 390-398.
  18. 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.
  19. PAIGE, C.C. and SAUNDERS, M.A. 1975. Solution of sparse indefinite systems of linear equations. SIAM Journal on Numerical Analysis, 12: 617-629.
  20. 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.
  21. 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.
  22. STEIHAUG, T. 1983. The conjugate gradient method and trust regions in large scale optimization. SIAM Journal on Numerical Analysis, 20: 626-637.
  23. STEWART, G.W. 1977. Research, development and LINPACK, in Mathematical Software III, J.R. RICE, ed., Academic Press, New York, USA, 1-14.
  24. STIEFEL,E. 1955. Relaxationsmethoden bester strategie zur l¨osung linearer gleichungssysteme. Comm. Math. Helv., 29: 157-179.
  25. SUN, Y. 2003. The Filter Algorithm for Solving Large-Scale Eigenproblems from Accelerator Simulations. PhD thesis, Stanford University, Stanford, California, USA.
  26. TITLEY-PELOQUIN, D. 2010. Backward Perturbation Analysis of Least Squares Problems. PhD thesis, School of Computer Science, McGill University, Canada.
  27. TITLEY-PELOQUIN, D. 2011. Convergence of backward error bounds in LSQR and LSMR. Private communication.
  28. VAN DER VORST, H.A. 2003. Iterative Krylov Methods for Large Linear Systems. (1st Edition) Cambridge University Press, Cambridge, UK.
  29. WATKINS, D.S. 2010. Fundamentals of Matrix Computations. (3rd Edition) Pure and Applied Mathematics, Wiley, Hoboken, New Jersey, USA.