×

zbMATH — the first resource for mathematics

Approximating the extreme Ritz values and upper bounds for the \(A\)-norm of the error in CG. (English) Zbl 1436.65033
Summary: In practical conjugate gradient (CG) computations, it is important to monitor the quality of the approximate solution to \(Ax = b\) so that the CG algorithm can be stopped when the required accuracy is reached. The relevant convergence characteristics, like the \(A\)-norm of the error or the normwise backward error, cannot be easily computed. However, they can be estimated. Such estimates often depend on approximations of the smallest or largest eigenvalue of \(A\). In the paper, we introduce a new upper bound for the \(A\)-norm of the error, which is closely related to the Gauss-Radau upper bound, and discuss the problem of choosing the parameter \(\mu\) which should represent a lower bound for the smallest eigenvalue of \(A\). The new bound has several practical advantages, the most important one is that it can be used as an approximation to the \(A\)-norm of the error even if \(\mu\) is not exactly a lower bound for the smallest eigenvalue of \(A\). In this case, \(\mu\) can be chosen, e.g., as the smallest Ritz value or its approximation. We also describe a very cheap algorithm, based on the incremental norm estimation technique, which allows to estimate the smallest and largest Ritz values during the CG computations. An improvement of the accuracy of these estimates of extreme Ritz values is possible, at the cost of storing the CG coefficients and solving a linear system with a tridiagonal matrix at each CG iteration. Finally, we discuss how to cheaply approximate the normwise backward error. The numerical experiments demonstrate the efficiency of the estimates of the extreme Ritz values, and show their practical use in error estimation in CG.

MSC:
65F10 Iterative numerical methods for linear systems
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F35 Numerical computation of matrix norms, conditioning, scaling
Software:
LSQR; mctoolbox
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Arioli, M., Duff, I.S., Ruiz, D.: Stopping criteria for iterative solvers. SIAM J. Matrix Anal. Appl. 13(1), 138-144 (1992) · Zbl 0749.65023
[2] Barrett, R., Berry, M., Chan, T.F., et al.: Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1994)
[3] Bischof, C.H.: Incremental condition estimation. SIAM J. Matrix Anal. Appl. 11(2), 312-322 (1990) · Zbl 0697.65042
[4] Dahlquist, G., Eisenstat, S.C., Golub, G.H.: Bounds for the error of linear systems of equations using the theory of moments. J. Math. Anal. Appl. 37, 151-166 (1972) · Zbl 0238.65012
[5] Dahlquist, G., Golub, G.H., Nash, S.G.: Bounds for the error in linear systems. In: Semi-Infinite Programming (Proc. Workshop, Bad Honnef, 1978), Lecture Notes in Control and Information Sci., vol. 15, pp. 154-172. Springer, Berlin (1979)
[6] Duff, I.S., Vömel, C.: Incremental norm estimation for dense and sparse matrices. BIT 42(2), 300-322 (2002) · Zbl 1010.65019
[7] Duintjer Tebbens, J., Tuma, M.: On incremental condition estimators in the 2-norm. SIAM J. Matrix Anal. Appl. 35(1), 174-197 (2014) · Zbl 1299.65089
[8] Eiermann, M., Ernst, O.G.: Geometric aspects of the theory of Krylov subspace methods. Acta Numer. 10, 251-312 (2001) · Zbl 1105.65328
[9] Fischer, B., Golub, G.H.: On the error computation for polynomial based iteration methods. In: Recent Advances in Iterative Methods, IMA Vol. Math. Appl., Vol. 60, pp. 59-67. Springer, New York (1994) · Zbl 0803.65034
[10] Golub, G.H., Meurant, G.: Matrices, moments and quadrature. In: Numerical Analysis 1993 (Dundee, 1993), Pitman Res. Notes Math. Ser., Vol. 303, pp. 105-156. Longman Sci. Tech., Harlow (1994) · Zbl 0795.65019
[11] 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) · Zbl 0888.65050
[12] Golub, G.H., Meurant, G.: Matrices, Moments and Quadrature with Applications. Princeton University Press, Princeton (2010) · Zbl 1217.65056
[13] Golub, G.H., Strakoš, Z.: Estimates in quadratic formulas. Numer. Algorithms 8(2-4), 241-268 (1994) · Zbl 0822.65022
[14] Golub, G.H., Van Loan, C.F.: Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences, 4th edn. Johns Hopkins University Press, Baltimore (2013)
[15] Greenbaum, A.: Estimating the attainable accuracy of recursively computed residual methods. SIAM J. Matrix Anal. Appl. 18(3), 535-551 (1997) · Zbl 0873.65027
[16] Gutknecht, M.H., Rozložník, M.: By how much can residual minimization accelerate the convergence of orthogonal residual methods? Numer. Algorithms 27(2), 189-213 (2001) · Zbl 0987.65032
[17] Gutknecht, M.H., Rozložnik, M.: Residual smoothing techniques: do they improve the limiting accuracy of iterative solvers? BIT 41(1), 86-114 (2001) · Zbl 0984.65026
[18] Hestenes, M.R., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Res. Nat. Bur. Stand. 49, 409-436 (1952) · Zbl 0048.09901
[19] Higham, N.J.: Accuracy and stability of numerical algorithms. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1996) · Zbl 0847.65010
[20] Kouhia, R.: Description of the CYLSHELL set. Laboratory of Structural Mechanics, Finland (1998)
[21] Meurant, G.: The computation of bounds for the norm of the error in the conjugate gradient algorithm. Numer. Algorithms 16(1), 77-87 (1998) · Zbl 0897.65026
[22] 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) · Zbl 1110.65029
[23] Meurant, G., Tichý, P.: On computing quadrature-based bounds for the A-norm of the error in conjugate gradients. Numer. Algo. 62(2), 163-191 (2013) · Zbl 1261.65034
[24] Meurant, G., Tichý, P.: Erratum to: On computing quadrature-based bounds for the A-norm of the error in conjugate gradients [mr3011386]. Numer. Algorithms 66(3), 679-680 (2014) · Zbl 1298.65062
[25] Oettli, W., Prager, W.: Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides. Numer. Math. 6(1), 405-409 (1964) · Zbl 0133.08603
[26] Paige, C.C., Saunders, M.A.: LSQR: an algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Software 8(1), 43-71 (1982) · Zbl 0478.65016
[27] Parlett, B.N., Dhillon, I.S.: Relatively robust representations of symmetric tridiagonals. In: Proceedings of the International Workshop on Accurate Solution of Eigenvalue Problems (University Park, PA, 1998), vol. 309, pp. 121-151 (2000) · Zbl 0948.65026
[28] Rigal, J.L., Gaches, J.: On the compatibility of a given solution with the data of a linear system. Journal of the ACM (JACM) 14(3), 543-548 (1967) · Zbl 0183.17704
[29] 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) · Zbl 1026.65027
[30] Strakoš, Z., Tichý, P.: Error estimation in preconditioned conjugate gradients. BIT 45(4), 789-817 (2005) · Zbl 1095.65029
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.