Non-stationary extremal eigenvalue approximations in iterative solutions of linear systems and estimators for relative error

arXiv1302.4824MaRDI QIDQ6239765FDOQ6239765

Authors: Divya Anand Subba, Murugesan Venkatapathi 

Publication date: 20 February 2013

Abstract: Non-stationary approximations of the final value of a converging sequence are discussed, and we show that extremal eigenvalues can be reasonably estimated from the CG iterates without much computation at all. We introduce estimators of relative error for conjugate gradient (CG)methods that adopt past work on computationally efficient bounds of the absolute errors using quadrature formulas. The evaluation of the Gauss quadrature based estimates though, depends on a priori knowledge of extremal eigenvalues; and the upper bounds in particular that are useful as a stopping criterion fail in the absence of a reasonable underestimate of smallest eigenvalue. Estimators for relative errors in A-norm and their extension to errors in l2 norm are presented with numerical results. Estimating the relative error from the residue in an iterative solution is required for efficient solution of a large problem with even a moderately high condition. Specifically, in a problem of solving for vector x in Ax=b, the uncertainty between the strict upper bound in relative error [{kappa}*||r(i)||/||b||] and its strict lower bound [||r(i)||/({kappa}*||b||)] is a factor of {kappa}^2 (given residue r(i)= b-Ax(i) is the residual vector at ith iteration and {kappa} the condition number of the square matrix A).

This page was built for publication: Non-stationary extremal eigenvalue approximations in iterative solutions of linear systems and estimators for relative error

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