Publication database of NCMM , project MORE and MathMAC center.
Dear guest, welcome to this publication database. As an anonymous user, you will probably not have edit rights. Also, the collapse status of the topic tree will not be persistent. If you like to have these and other options enabled, you might ask Jaroslav Hron for a login account.
This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit https://github.com/aigaion.
 [BibTeX] [RIS] [Request]
Approximating the extreme Ritz values and upper bounds for the A-norm of the error in CG
Type of publication: Article
Citation:
Publication status: Accepted
Journal: Numerical Algorithms
Volume: online first
Year: 2018
DOI: 10.1007/s11075-018-0634-8
Abstract: 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 µ 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 µ is not exactly a lower bound for the smallest eigenvalue of A. In this case, µ 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.
Preprint project: NCMM
Preprint year: 2018
Preprint number: 12
Preprint ID: NCMM/2018/12
Keywords:
Authors Meurant, Gérard
Tichý, Petr
Added by: [MB]
Total mark: 0
Attachments
    Notes
      Topics