{
  "id": "1705.08806",
  "version": "v1",
  "published": "2017-05-24T14:56:28.000Z",
  "updated": "2017-05-24T14:56:28.000Z",
  "title": "Significance of error estimation in iterative solution of linear systems : estimation algorithms and analysis for CG, Bi-CG and GMRES",
  "authors": [
    "Puneet Jain",
    "Krishna Manglani",
    "Murugesan Venkatapathi"
  ],
  "categories": [
    "math.NA"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-05-24T14:56:28.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "error estimation",
      "iterative solution",
      "estimation algorithms",
      "non-symmetric linear systems",
      "condition number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}