Accurate error estimation in CG

DOI10.1007/S11075-021-01078-WMaRDI QIDQ2234486zbMATH OpenOpenAlexFDO

Authors Jan Papež, Petr Tichý, G. Meurant

Publication date 19 October 2021

Published in Numerical Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2101.03931

zbMATH Keywords

conjugate gradients methodserror estimation

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10)

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 $x_k$ so that the process could be stopped whenever $x_k$ is accurate enough. One of the most relevant quantities for monitoring the quality of $x_k$ is the squared $A$-norm of the error vector $x-x_k$. 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.

Recommendations

• Error estimation in preconditioned conjugate gradients
• Approximating the extreme Ritz values and upper bounds for the \(A\)-norm of the error in CG
• On Estimation of theA-norm of the Error in CG and PCG
• Computable error bounds and estimates for the conjugate gradient method
• The behavior of the Gauss-Radau upper bound of the error norm in CG

Cites work

• A posteriori error estimates including algebraic error and stopping criteria for iterative solvers
• A stopping criterion for the conjugate gradient algorithm in a finite element method framework
• Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem
• Approximating the extreme Ritz values and upper bounds for the \(A\)-norm of the error in CG
• Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences
• Block Preconditioning of Stochastic Galerkin Problems: New Two-sided Guaranteed Spectral Bounds
• Error estimation in preconditioned conjugate gradients
• Estimates in quadratic formulas
• Generalized spectrum of second order differential operators
• scientific article; zbMATH DE number 554737 (Why is no real title available?)
• Laplacian preconditioning of elliptic PDEs: localization of the eigenvalues of the discretized operator
• Matrices, moments and quadrature. II: How to compute the norm of the error iterative methods
• Methods of conjugate gradients for solving linear systems
• Numerical experiments in computing bounds for the norm of the error in the preconditioned conjugate gradient algorithm
• On computing quadrature-based bounds for the A-norm of the error in conjugate gradients
• On efficient numerical solution of linear algebraic systems arising in goal-oriented error estimates
• On error estimation in the conjugate gradient method and why it works in finite precision computations
• Predicting the Behavior of Finite Precision Lanczos and Conjugate Gradient Computations
• Stopping criteria for adaptive finite element solvers
• The Lanczos and Conjugate Gradient Algorithms
• The Lanczos and conjugate gradient algorithms in finite precision arithmetic

Cited in

(17)

• Approximating the extreme Ritz values and upper bounds for the \(A\)-norm of the error in CG
• Error estimation in preconditioned conjugate gradients
• Calculation of Cam-Form Errors
• On soft errors in the conjugate gradient method: sensitivity and robust numerical detection
• Error Bounds for Lanczos-Based Matrix Function Approximation
• Computable error bounds and estimates for the conjugate gradient method
• Solving A x= b using a modified conjugate gradient method based on roots of A
• The behavior of the Gauss-Radau upper bound of the error norm in CG
• A flexible short recurrence Krylov subspace method for matrices arising in the time integration of port-Hamiltonian systems and ODEs/DAEs with a dissipative Hamiltonian
• Towards understanding CG and GMRES through examples
• The effect of approximate coarsest-level solves on the convergence of multigrid V-cycle methods
• Estimating error norms in CG-like algorithms for least-squares and least-norm problems
• A posteriori error bounds for the block-Lanczos method for matrix function approximation
• New error estimates for the conjugate gradient method
• Block conjugate gradient methods with error norm estimates for least squares problems
• Stopping criteria for the conjugate gradient algorithm in high-order finite element methods
• A posteriori error estimates based on multilevel decompositions with an iterative solver on the coarsest level

This page was built for publication: Accurate error estimation in CG

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2234486)