×

Error estimation in preconditioned conjugate gradients. (English) Zbl 1095.65029

The authors deal with the problem of convergence in the preconditioned conjugate gradient method for the solution of a linear system \(Ax=b\), where \(A\) is a symmetric positive definite \(n\times n\) matrix. Indeed, the problem of this convergence was the subject of many papers in literature. However, they always assume exact arithmetic and consequently, they assume preserving orthogonality and exploiting the finite termination property (i.e. getting the exact solution in a finite number of steps, which does not exceed the dimension \(n\) of the problem).
Unfortunately, most practical computations violate these assumptions. Taking this fact into account, the authors focus on estimating the \(A\)-norm of the error and present a practical estimate for such norm. It is simple and numerically stable. Eventually, they propose to combine their results with the standard quantities, which are already used, to establish a convenient stopping criteria. Some nice numerical experiments are reported to illustrate how this new estimate works.

MSC:

65F10 Iterative numerical methods for linear systems
65F35 Numerical computation of matrix norms, conditioning, scaling
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] M. Arioli, A stopping criterion for the conjugate gradient algorithms in a finite element method framework, Numer. Math., 97 (2004), pp. 1–24. · Zbl 1048.65029
[2] M. Arioli, J. W. Demmel and I. S. Duff, Solving sparse linear systems with sparse backward error, SIAM J. Matrix Anal. Appl., 10 (1989), pp. 165–190. · Zbl 0684.65022
[3] M. Arioli, I. Duff and D. Ruiz, Stopping criteria for iterative solvers, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 138–144. · Zbl 0749.65023
[4] M. Arioli, E. Noulard and A. Russo, Stopping criteria for iterative methods: applications to PDE’s, Calcolo, 38 (2001), pp. 97–112. · Zbl 1072.65045
[5] O. Axelsson, Iterative Solution Methods, Cambridge University Press, 1994. · Zbl 0795.65014
[6] O. Axelsson and I. Kaporin, Error norm estimation and stopping criteria in preconditioned conjugate gradient iterations, Numer. Linear Algebra Appl., 8 (2001), pp. 265–286. · Zbl 1051.65024
[7] I. Babuška, Mathematics of the verification and validation in computational engineering, in Mathematical and Computer Modelling in Science and Engineering, M. Kočandrlová and V. Kelar, eds., pp. 5–12, Union of Czech Mathematicians and Physicists, Prague, 2003.
[8] R. Barrett, M. Berry, T. F. Chan et al., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM, Philadelphia, PA, 1994.
[9] P. Benner, Solving large-scale control problems, to appear in IEEE Control Syst. Magazine, 24 (2004), pp. 44–59.
[10] G. Dahlquist, S. Eisenstat and G. H. Golub, Bounds for the error of linear systems of equations using the theory of moments, J. Math. Anal. Appl., 37 (1972), pp. 151–166. · Zbl 0238.65012
[11] G. Dahlquist, G. H. Golub and S. G. Nash, Bounds for the error in linear systems, in Proc. Workshop on Semi-Infinite Programming, R. Hettich, ed., pp. 154–172, Springer, Berlin, 1978.
[12] P. Deuflhard, Cascadic conjugate gradient methods for elliptic partial differential equations: algorithm and numerical results, in Domain decomposition methods in scientific and engineering computing (University Park, PA, 1993), Contemp. Math., vol. 180, pp. 29–42, Am. Math. Soc., Providence, RI, 1994. · Zbl 0817.65090
[13] V. Frayssé, L. Giraud, S. Gratton and J. Langou, A set of GMRES routines for real and complex arithmetics on on high performance computers, TR/PA/03/3, CERFACS, Toulouse Cedex, France, 2003. · Zbl 1070.65527
[14] G. H. Golub and G. Meurant, Matrices, moments and quadrature, in Proc. 15-th Dundee Conf., June 1993, D. Sciffeths and G. Watson, eds., pp. 105–156, Longman Sci. Tech. Publ., 1994. · Zbl 0795.65019
[15] G. H. Golub and G. Meurant, Matrices, moments and quadrature. II. How to compute the norm of the error in iterative methods, BIT, 37 (1997), pp. 687–705. · Zbl 0888.65050
[16] G. H. Golub and Z. Strakoš, Estimates in quadratic formulas, Numer. Algorithms, 8 (1994), pp. 241–268. · Zbl 0822.65022
[17] G. H. Golub and C. van Loan, Matrix Computation, The Johns Hopkins University Press, Baltimore MD, third edn., 1996. · Zbl 0865.65009
[18] A. Greenbaum, Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences, Linear Algebra Appl., 113 (1989), pp. 7–63. · Zbl 0662.65032
[19] A. Greenbaum, Estimating the attainable accuracy of recursively computed residual methods, SIAM J. Matrix Anal. Appl., 18 (1997), pp. 535–551. · Zbl 0873.65027
[20] A. Greenbaum, Iterative methods for solving linear systems, Frontiers in Applied Mathematics, vol. 17, SIAM, Philadelphia, PA., 1997. · Zbl 0883.65022
[21] A. Greenbaum and Z. Strakoš, Predicting the behavior of finite precision Lanczos and conjugate gradient computations, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 121–137. · Zbl 0755.65037
[22] M. R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bureau Stand., 49 (1952), pp. 409–435. · Zbl 0048.09901
[23] N. J. Higham, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. · Zbl 0847.65010
[24] R. Kouhia, Description of the CYLSHELL set, Laboratory of Structural Mechanics, Finland, May 1998. Matrix Market.
[25] Matrix Market, http://math.nist.gov/MatrixMarket/. The Matrix Market is a service of the Mathematical and Computational Sciences Division of the Information Technology Laboratory of the National Institute of Standards and Technology.
[26] G. Meurant, Computer solution of large linear systems, Studies in Mathematics and its Applications, vol. 28, North-Holland Publishing Co., Amsterdam, 1999. · Zbl 0934.65032
[27] G. Meurant, Numerical experiments in computing bounds for the norm of the error in the preconditioned conjugate gradient algorithm, Numer. Algorithms 22, 3–4 (1999), pp. 353–365. · Zbl 0954.65025
[28] G. Meurant, Towards a reliable implementation of the conjugate gradient method, Invited plenary lecture at the Latsis Symposium: Iterative Solvers for Large Linear Systems, Zurich, February 2002.
[29] E. Noulard and M. Arioli, Vector stopping criteria for iterative methods: Theoretical tools, pubblicazioni n. 956, Instituto di Analisi Numerica, Pavia, Italy, 1995.
[30] W. Oettli and W. Prager, Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides, Numer. Math., 6 (1964), pp. 405–409. · Zbl 0133.08603
[31] C. C. Paige, Error analysis of the lanczos algorithm for tridiagonalizing a symmetric matrix, J. Inst. Math. Appl, 18 (1976), pp. 341–349. · Zbl 0347.65018
[32] C. C. Paige and M. A. Saunders, LSQR: an algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Softw., 8 (1982), pp. 43–71. · Zbl 0478.65016
[33] C. C. Paige and Z. Strakoš, Residual and backward error bounds in minimum residual Krylov subspace methods, SIAM J. Sci. Comput., 23 (2002), pp. 1898–1923 (electronic). · Zbl 1035.65031
[34] Y. Saad, Iterative Methods for Sparse Linear Systems, SIAM, Philadelphia, PA, second edn., 2003. · Zbl 1031.65046
[35] R. D. Skeel, Iterative refinement implies numerical stability for Gaussian elimination, Math. Comp., 35 (1980), pp. 817–832. · Zbl 0441.65027
[36] G. L. G. Sleijpen, H. A. van der Vorst and D. R. Fokkema, BiCGstab(l) and other hybrid Bi-CG methods, Numer. Algorithms, 7 (1994), pp. 75–109. · Zbl 0810.65027
[37] Z. Strakoš, Theory of Convergence and Effects of Finite Precision Arithmetic in Krylov Subspace Methods, thesis for the degree doctor of science, Institute of Computer Science, Academy of Sciences of the Czech Republic, Prague, February 2001.
[38] Z. Strakoš and P. Tichý, On error estimation in the conjugate gradient method and why it works in finite precision computations, Electron. Trans. Numer. Anal., 13 (2002), pp. 56–80 (electronic). · Zbl 1026.65027
[39] Z. Strakoš and P. Tichý, On estimation of the A-norm of the error in CG and PCG, PAMM, 3 (2003), pp. 553–554 (published online). · Zbl 1354.90173
[40] H. A. van der Vorst, Iterative Krylov methods for large linear systems, Cambridge Monographs on Applied and Computational Mathematics, vol. 13, Cambridge University Press, Cambridge, 2003. · Zbl 1023.65027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.