Abstract
In practical computations, the (preconditioned) conjugate gradient (P)CG method is the iterative method of choice for solving systems of linear algebraic equations Ax = b with a real symmetric positive definite matrix A. During the iterations, it is important to monitor the quality of the approximate solution xk so that the process could be stopped whenever xk is accurate enough. One of the most relevant quantities for monitoring the quality of xk is the squared A-norm of the error vector x − xk. This quantity cannot be easily evaluated; however, it can be estimated. Many of the existing estimation techniques are inspired by the view of CG as a procedure for approximating a certain Riemann–Stieltjes integral. The most natural technique is based on the Gauss quadrature approximation and provides a lower bound on the quantity of interest. The bound can be cheaply evaluated using terms that have to be computed anyway in the forthcoming CG iterations. If the squared A-norm of the error vector decreases rapidly, then the lower bound represents a tight estimate. In this paper, we suggest a heuristic strategy aiming to answer the question of how many forthcoming CG iterations are needed to get an estimate with the prescribed accuracy. Numerical experiments demonstrate that the suggested strategy is efficient and robust.
Similar content being viewed by others
References
Hestenes, M.R., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Research Nat. Bur. Stand. 49, 409–436 (1952)
Arioli, M.: A stopping criterion for the conjugate gradient algorithms in a finite element method framework. Numer. Math. 97(1), 1–24 (2004)
Jiránek, P., Strakoš, Z., Vohralík, M.: A posteriori error estimates including algebraic error and stopping criteria for iterative solvers. SIAM J. Sci. Comput. 32(3), 1567–1590 (2010)
Arioli, M., Georgoulis, E.H., Loghin, D.: Stopping criteria for adaptive finite element solvers. SIAM J. Sci. Comput. 35(3), A1537–A1559 (2013)
Dolejší, V., Tichý, P.: On efficient numerical solution of linear algebraic systems arising in goal-oriented error estimates. J. Sci. Comput. 83(1), 1–29 (2020)
Greenbaum, A.: Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences. Linear Algebra Appl. 113, 7–63 (1989)
Greenbaum, A., Strakoš, Z: Predicting the behavior of finite precision Lanczos and conjugate gradient computations. SIAM J. Matrix Anal. Appl. 13 (1), 121–137 (1992)
Paige, C.C.: Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem. Linear Algebra Appl. 34, 235–258 (1980)
Meurant, G.: The Lanczos and conjugate gradient algorithms: From theory to finite precision computations, Software, Environments, and Tools, vol. 19. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2006)
Meurant, G., Strakoš, Z.: The Lanczos and conjugate gradient algorithms in finite precision arithmetic. Acta Numer. 15, 471–542 (2006)
Golub, G.H., Meurant, G.: Matrices, moments and quadrature. In: Numerical analysis 1993 (Dundee, 1993). Longman Sci. Tech., Harlow, vol. 303, pp 105–156. Pitman Res. Notes Math. Ser. (1994)
Golub, G.H., Strakoš, Z.: Estimates in quadratic formulas. Numer. Algorithm. 8(2-4), 241–268 (1994)
Golub, G.H., Meurant, G.: Matrices, moments and quadrature. II. How to compute the norm of the error in iterative methods. BIT 37(3), 687–705 (1997)
Strakoš, Z., Tichý, P.: On error estimation in the conjugate gradient method and why it works in finite precision computations. Electron. Trans. Numer. Anal. 13, 56–80 (2002)
Meurant, G., Tichý, P.: On computing quadrature-based bounds for the A-norm of the error in conjugate gradients. Numer. Algorithm. 62(2), 163–191 (2013)
Meurant, G., Tichý, P.: Approximating the extreme Ritz values and upper bounds for the A-norm of the error in CG. Numer. Algorithm. 82(3), 937–968 (2019)
Strakoš, Z., Tichý, P.: Error estimation in preconditioned conjugate gradients. BIT 45(4), 789–817 (2005)
Meurant, G.: Numerical experiments in computing bounds for the norm of the error in the preconditioned conjugate gradient algorithm. Numer. Algorithm. 22(3-4), 353–365 (1999)
Gergelits, T., Mardal, K.-A., Nielsen, B.F., Strakoš, Z.: Laplacian preconditioning of elliptic PDEs: localization of the eigenvalues of the discretized operator. SIAM J. Numer. Anal. 57(3), 1369–1394 (2019)
Gergelits, T., Nielsen, B.F., Strakoš, Z.: Generalized spectrum of second order differential operators. SIAM J. Numer. Anal. 58(4), 2193–2211 (2020)
Kubínová, M., Pultarová, I.: Block preconditioning of stochastic Galerkin problems: new two-sided guaranteed spectral bounds. SIAM/ASA J. Uncertain. Quantif. 8(1), 88–113 (2020)
Kouhia, R.: Description of the CYLSHELL set. Technical Report, Laboratory of Structural Mechanics, Finland. Matrix Market (1998)
Funding
The work of J. Papež and P. Tichý was supported by the Grant Agency of the Czech Republic under grant no. 20-01074S.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendix
Algorithm 2 (MATLAB code, preconditioned version)
Rights and permissions
About this article
Cite this article
Meurant, G., Papež, J. & Tichý, P. Accurate error estimation in CG. Numer Algor 88, 1337–1359 (2021). https://doi.org/10.1007/s11075-021-01078-w
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-021-01078-w