|
Article information
2015 , Volume 20, ¹ 2, p.44-55
Kireev I.V.
Inexpensive stopping criteria in the conjugate gradient method
In the paper, some aspects of the numerical implementation of the conjugate gradient method (CGM) for systems of linear algebraic equations with symmetric positive definite matrix in the presence of round-off errors are discussed. With exact calculations, CGM provides an exact solution in a finite number of iteration steps. But in fact CGM is an iterative process and the weak point in an iterative process is in a stopping criterion. It is required to determine the number of the iteration step, after which the accuracy of an approximation to a solution of a system of linear equations may not be considerably improved with a particular computer. Hence, the construction of inexpensive stopping criteria for CGM being the aim of this paper is an urgent problem. For four popular versions of CGM, the step-by-step behavior as well as stopping criteria for an iterative process are considered. Numerical results show that the most accurate approximation is achieved by the CGM-version where descent directions and residual vectors are orthogonal in the energy and Euclidean metrics, respectively, at each iteration step. A practical stopping criteria for CGM is proposed as a formula that enables one to determine the number of the CGM iteration step, starting with which the progress is no longer being made. The application of the constructed criteria to the solution of specific systems of linear algebraic equations with ill-conditioned matrices is demonstrated.
[full text]
Keywords: conjugate gradient method, stopping criteria
Author(s):
Kireev Igor' Valerievich
PhD. , Associate Professor
Position: Senior Research Scientist
Office: Institute of Computational Simulation of SB RAS
Address: 660036, Russia, Krasnoyarsk, Akademgorodok str, 50, build 44
Phone Office: (391) 249 47 39
E-mail: kiv@icm.krasn.ru
SPIN-code: 3804-0901 References:
[1] Hestenes, M.R. and Stiefel, E. Methods of conjugate gradients for solving linear systems. Journal of research of the National Bureau of Standards. 1952; 49(5):409–435.
[2] Wilkinson, J.H. and Reinsch, Ñ. Handbook for Automatic Computation. Vol. II. Linear Algebra. New York: Springer-Verlag; 1971: 450.
[3] Cipra, B.A. The best of the 20th century: Editors name top 10 algorithms. SIAM News (Society for Industrial and Applied Mathematics); 33(4):1-2.
[4] Krylov, A.N. On the numerical solution of the equation by which in technical questions frequencies of small oscillations of material systems are determined. Izvestiya AN SSSR Otdelenie matematicheskikh i estestvennykh nauk. 1931; (4):491–539. (In Russ.)
[5] Golub, G.H. and O’Leary, D.P. Some history of the conjugate gradient and Lanczos algorithms: 1948–1976. SIAM Review. 1989; 31(1):50–102.
[6] Voevodin, V.V. Vychislitel'nye osnovy lineynoy algebry [Numerical Foundations of Linear Algebra]. Moscow: Nauka; 1977: 304. (In Russ.)
[7] Greenbaum, A. Estimating the attainable accuracy of recursively computed residual methods. SIAM Journal on Matrix Analysis and Applications. 1997; (18):535–551.
[8] Greenbaum, A., Strakos, Z. Predicting the âehavior of finite precision lanczos and conjugate gradient computations. SIAM Journal on Matrix Analysis and Applications. 1992; 13(1):121-137.
[9] Voevodin, V.V. Lineynaya algebra [Linear Algebra]. Moscow: Nauka; 1980: 400. (In Russ.)
[10] Engeli, M., Ginsburg, Th., Rutishauser, H., Stiefel, E. Refined iterative Methods for Computation of the Solution and the Eigenvalues of Self-Adjoint Boundary Value Problems. Mitteilungen aus dem Institut fur angewandte Mathematik. Stuttgart: Birkha¨user Verlag; 1959: 107.
[11] Voevodin, V.V. Chislennye metody algebry. Teoriya i algorifmy [Computational Methods of Algebra. Theory and Algorithms]. Moscow: Nauka; 1966: 248. (In Russ.)
[12] Karmanov, V.G. Matematicheskoe programmirovanie [Mathematical Programming]. Uchebnoe posobie. Moscow: Fizmatlit; 2004: 264. (In Russ.)
[13] Malyshev, A.N. Vvedenie v vychislitel'nuyu lineynuyu algebru [Introduction to Computational Linear Algebra]. Novosibirsk: Nauka; 1991: 229. (In Russ.)
[14] Godunov, S.K. Reshenie sistem lineynykh uravneniy [Solving Systems of Linear Equations]. Novosibirsk: Nauka; 1980: 178. (In Russ.)
[15] Meurant, G. and Strakoˇs, Z. The Lanczos and conjugate gradient algorithms in finiteprecision arithmetic. Acta Numerica. 2006; (15):471–542.
[16] Faddeev, D.K., Faddeeva, V.N. Vychislitel'nye metody lineynoy algebry [Computational Methods in Linear Algebra]. Moscow: Fizmatgiz; 1963: 229. (In Russ.)
[17] Chernysheva, A.A., Kireev, I.V. Modification Wilkinson’s criteria stopping iterations in the conjugate gradient method. Bulletin of Krasnoyarsk State Univ. 2005; (4):173–177. (In Russ.)
[18] Kireev, I.V. Chislennaya realizatsiya metoda sopryazhennykh gradientov [The Computational Implementation of the Conjugate Gradient Method]. Krasnoyarsk, 2013; (Preprint. ICM SB RAS; ¹ 13-1. 26. (In Russ.)
Bibliography link:
Kireev I.V. Inexpensive stopping criteria in the conjugate gradient method // Computational technologies. 2015. V. 20. ¹ 2. P. 44-55
|
