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

error estimationconjugate gradients methods

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

• scientific article; zbMATH DE number 554737 (Why is no real title available?)
• 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
• 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

(14)

• Approximating the extreme Ritz values and upper bounds for the \(A\)-norm of the error in CG
• The behavior of the Gauss-Radau upper bound of the error norm in CG
• Error Bounds for Lanczos-Based Matrix Function Approximation
• Error estimation in preconditioned conjugate gradients
• On soft errors in the conjugate gradient method: sensitivity and robust numerical detection
• 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 flexible short recurrence Krylov subspace method for matrices arising in the time integration of port-Hamiltonian systems and ODEs/DAEs with a dissipative Hamiltonian
• Computable error bounds and estimates for the conjugate gradient method
• Towards understanding CG and GMRES through examples
• Solving \(A\underline x=\underline b\) using a modified conjugate gradient method based on roots of \(A\)
• A posteriori error bounds for the block-Lanczos method for matrix function approximation
• New error estimates for the conjugate gradient method
• Calculation of Cam-Form Errors

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)