On error estimation in the conjugate gradient method: Normwise backward error
Main Article Content
Abstract
Using an idea of Duff and V{\"o}mel [BIT, 42 (2002), pp.~300--322 ] we suggest a simple algorithm that incrementally estimates the $2$-norm of Jacobi matrices that are available during the conjugate gradient (CG) computations. The estimate can be used, e.g., in stopping criteria based on the normwise backward error. Numerical experiments predict that the estimate approximates the $2$-norm of $A$ with a sufficient accuracy.
Article Details
How to Cite
Tichý, P.
(2016).
On error estimation in the conjugate gradient method: Normwise backward error.
Proceedings Of The Conference Algoritmy, , 323-332.
Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/algoritmy/article/view/421/337
Section
Articles
References
[1] M. Arioli, I. Duff, and D. Ruiz. Stopping criteria for iterative solvers. SIAM J. Matrix Anal. Appl., 13(1):138–144, 1992.
[2] R. Barrett, M. Berry, T. F. Chan, and et al. Templates for the solution of linear systems: building blocks for iterative methods. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994.
[3] C. H. Bischof. Incremental condition estimation. SIAM J. Matrix Anal. Appl., 35(11):312–322, 1990.
[4] I. S. Duff and C. Vomel. Incremental norm estimation for dense and sparse matrices. BIT, 42(2):300–322, 2002.
[5] J. Duintjer Tebbens and M. Tuma. On incremental condition estimators in the 2-norm. SIAM J. Matrix Anal. Appl., 35(1):174–197, 2014.
[6] G. H. Golub and G. Meurant. Matrices, moments and quadrature with applications. Princeton University Press, USA, 2010.
[7] G. H. Golub and C. F. Van Loan. Matrix computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, third edition, 1996.
[8] M. R. Hestenes and E. Stiefel. Methods of conjugate gradients for solving linear systems. J. Research Nat. Bur. Standards, 49:409–436, 1952.
[9] N. J. Higham. Accuracy and stability of numerical algorithms. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996.
[10] G. Meurant. The Lanczos and conjugate gradient algorithms, from theory to finite precision computations, volume 19 of Software, Environments, and Tools. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2006.
[11] G. Meurant. Estimates of the l2 norm of the error in the conjugate gradient algorithm. Numer. Algorithms, 40(2):157–169, 2005.
[12] C. C. Paige and M. A. Saunders. LSQR: an algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Software, 8(1):43–71, 1982.
[13] J.-L. Rigal and J. Gaches. On the compatibility of a given solution with the data of a linear system. J. Assoc. Comput. Mach., 14:543–548, 1967.
[2] R. Barrett, M. Berry, T. F. Chan, and et al. Templates for the solution of linear systems: building blocks for iterative methods. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994.
[3] C. H. Bischof. Incremental condition estimation. SIAM J. Matrix Anal. Appl., 35(11):312–322, 1990.
[4] I. S. Duff and C. Vomel. Incremental norm estimation for dense and sparse matrices. BIT, 42(2):300–322, 2002.
[5] J. Duintjer Tebbens and M. Tuma. On incremental condition estimators in the 2-norm. SIAM J. Matrix Anal. Appl., 35(1):174–197, 2014.
[6] G. H. Golub and G. Meurant. Matrices, moments and quadrature with applications. Princeton University Press, USA, 2010.
[7] G. H. Golub and C. F. Van Loan. Matrix computations. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, third edition, 1996.
[8] M. R. Hestenes and E. Stiefel. Methods of conjugate gradients for solving linear systems. J. Research Nat. Bur. Standards, 49:409–436, 1952.
[9] N. J. Higham. Accuracy and stability of numerical algorithms. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996.
[10] G. Meurant. The Lanczos and conjugate gradient algorithms, from theory to finite precision computations, volume 19 of Software, Environments, and Tools. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2006.
[11] G. Meurant. Estimates of the l2 norm of the error in the conjugate gradient algorithm. Numer. Algorithms, 40(2):157–169, 2005.
[12] C. C. Paige and M. A. Saunders. LSQR: an algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Software, 8(1):43–71, 1982.
[13] J.-L. Rigal and J. Gaches. On the compatibility of a given solution with the data of a linear system. J. Assoc. Comput. Mach., 14:543–548, 1967.