The behavior of the Gauss-Radau upper bound of the error norm in CG

DOI10.1007/S11075-023-01522-ZMaRDI QIDQ6093978zbMATH OpenOpenAlexFDO

Authors G. Meurant, Petr Tichý

Publication date 12 September 2023

Published in Numerical Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

conjugate gradientserror boundsGauss-Radau quadrature

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Numerical computation of eigenvalues and eigenvectors of matrices (65F15)

Abstract: Consider the problem of solving systems of linear algebraic equations $Ax=b$ with a real symmetric positive definite matrix $A$ using the conjugate gradient (CG) method. To stop the algorithm at the appropriate moment, it is important to monitor the quality of the approximate solution. One of the most relevant quantities for measuring the quality of the approximate solution is the $A$-norm of the error. This quantity cannot be easily computed, however, it can be estimated. In this paper we discuss and analyze the behaviour of the Gauss-Radau upper bound on the $A$-norm of the error, based on viewing CG as a procedure for approximating a certain Riemann-Stieltjes integral. This upper bound depends on a prescribed underestimate $mu$ to the smallest eigenvalue of $A$. We concentrate on explaining a phenomenon observed during computations showing that, in later CG iterations, the upper bound loses its accuracy, and is almost independent of $mu$. We construct a model problem that is used to demonstrate and study the behaviour of the upper bound in dependence of $mu$, and developed formulas that are helpful in understanding this behavior. We show that the above mentioned phenomenon is closely related to the convergence of the smallest Ritz value to the smallest eigenvalue of $A$. It occurs when the smallest Ritz value is a better approximation to the smallest eigenvalue than the prescribed underestimate $mu$. We also suggest an adaptive strategy for improving the accuracy of the upper bounds in the previous iterations.

Recommendations

• Approximating the extreme Ritz values and upper bounds for the \(A\)-norm of the error in CG
• Accurate error estimation in CG
• Computable error bounds and estimates for the conjugate gradient method
• On error estimation in the conjugate gradient method and why it works in finite precision computations
• Euclidean-norm error bounds for SYMMLQ and CG

Cites work

• Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem
• Accurate error estimation in CG
• 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
• Bounds for the error of linear systems of equations using the theory of moments
• Erratum to: ``On computing quadrature-based bounds for the A-norm of the error in conjugate gradients
• Error estimation in preconditioned conjugate gradients
• Estimates in quadratic formulas
• How to Make the Lanczos Algorithm Converge Slowly
• scientific article; zbMATH DE number 3649907 (Why is no real title available?)
• scientific article; zbMATH DE number 554737 (Why is no real title available?)
• scientific article; zbMATH DE number 1049347 (Why is no real title available?)
• scientific article; zbMATH DE number 1049353 (Why is no real title available?)
• scientific article; zbMATH DE number 2107939 (Why is no real title available?)
• Matrices, moments and quadrature with applications
• 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 error estimation in the conjugate gradient method and why it works in finite precision computations
• On prescribing the convergence behavior of the conjugate gradient algorithm
• On sensitivity of Gauss-Christoffel quadrature
• On the real convergence rate of the conjugate gradient method
• Predicting the Behavior of Finite Precision Lanczos and Conjugate Gradient Computations
• Some Modified Matrix Eigenvalue Problems
• The computation of bounds for the norm of the error in the conjugate gradient algorithm
• The Lanczos and conjugate gradient algorithms in finite precision arithmetic
• The numerically stable reconstruction of Jacobi matrices from spectral data

Cited in

(8)

• Accurate error estimation in CG
• 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
• Euclidean-norm error bounds for SYMMLQ and CG
• Block conjugate gradient methods with error norm estimates for least squares problems
• Error norm estimates for the block conjugate gradient algorithms
• Monotonicity, bounds and acceleration of block Gauss and Gauss-Radau quadrature for computing B^T (A)B
• A posteriori error estimates based on multilevel decompositions with an iterative solver on the coarsest level

This page was built for publication: The behavior of the Gauss-Radau upper bound of the error norm in CG

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