Significance of error estimation in iterative solution of linear systems : estimation algorithms and analysis for CG, Bi-CG and GMRES

Puneet Jain, Krishna Manglani, Murugesan Venkatapathi

Published 2017-05-24Version 1

We show that estimation of error in the iterative solution can reduce uncertainty in convergence by a factor $\sim \kappa(A,x)$ compared to the case of using the relative residue as a stopping criterion. Here $\kappa(A,x)$ is the condition number of the forward problem of computing $Ax$ given $x$, $A$, and $1 \leq \kappa(A,x) \leq\kappa(A)$ where $\kappa(A)$ is the condition number of matrix $A$. This makes error estimation as important as preconditioning for efficient and accurate solution of moderate to high condition problems ($\kappa(A)>10$). An $\mathcal{O}(1)$ estimator (at every iteration) was proposed more than a decade ago, for efficient solving of symmetric positive definite linear systems by the CG algorithm. Later, an $\mathcal{O}(k^2)$ estimator was described for the GMRES algorithm which allows for non-symmetric linear systems as well, and here $k$ is the iteration number. We suggest a minor modification in this GMRES estimation for increased stability. Note that computational cost of the estimator is expected to be significantly less than the $\mathcal{O}(n^2)$ evaluation at every iteration of these methods in solving problems of dimension $n$. In this work, we first propose an $\mathcal{O}(n)$ error estimator for A-norm and $l_{2}$ norm of the error vector in Bi-CG algorithms that can as well solve non-symmetric linear systems. Secondly, we present an analysis of performance of these error estimates proposed for CG, Bi-CG and GMRES methods. The robust performance of these estimates as a stopping criterion results in increased savings and accuracy in computation, as condition number and size of problems increase.