Euclidean-Norm Error Bounds for SYMMLQ and CG
Ron Estrin, Dominique Orban, Michael A. Saunders · SIAM Journal on Matrix Analysis and Applications · 2019
For positive definite and semidefinite consistent $Ax_\star=b$, we use the Gauss--Radau approach of Golub and Meurant (1997) to obtain an upper bound on the error $\|x_\star-x_k^L\|_2$ for SYMMLQ iterates, assuming exact arithmetic. Such a bound, computable in constant time per iteration, was not previously available. We show that the CG error $\|x_\star-x_k^C\|_2$ is always smaller and can also be bounded in constant time per iteration. Our approach is computationally cheaper than other bounds or estimates of the CG error in the literature. As with other approaches using Gauss--Radau quadrature, we require a positive lower bound on the smallest nonzero eigenvalue of $A$. For indefinite $A$, we obtain an estimate of $\|x_\star-x_k^L\|_2$. Numerical experiments demonstrate that our bounds are remarkably tight for SYMMLQ on positive definite systems and therefore provide reliable bounds for CG.