Consider $Ax=b$ with $A$ nearly singular which means there is an eigenvalue $\lambda_0$ of $A$ that is very small. The usual stop criterion of an iterative method is based on the residual $r_n:=b-Ax_n$ and regards the iterations can stop when $\|r_n\|/\|r_0\|<tol$ with $n$ the iteration number. But in the case we are considering, there could be large error $v$ living in the eigenspace associated with the small eigenvalue $\lambda_0$ which gives small residual $Av=\lambda_0v$.  Suppose the initial residual $r_0$ is large, then it might happen we stop at $\|r_n\|/\|r_0\|<tol$ but the error $x_n-x$ is still big.  What is a better error indicator in this case?  Is $\|x_{n}-x_{n-1}\|$ a good candidate? 
Stopping criteria for iterative linear solvers applied to nearly singular systems
numerics;linear algebra
Please never use the difference between successive iterates to define a stopping criteria. This misdiagnoses stagnation for convergence. Most nonsymmetric matrix iterations are not monotone, and even GMRES in exact arithmetic with no restarts may stagnate for an arbitrary number of iterations (up to the dimension of the matrix) before converging suddenly. See examples in Nachtigal, Reddy, and Trefethen (1993).A better way to define convergenceWe are usually interested in the accuracy of our solution more than the size of the residual. Specifically, we might like to guarantee that the difference between an approximate solution $x_n$ and the exact solution $x$ satisfies $$|x_n - x| < c$$ for some user-specified $c$. It turns out that can achieve this by finding an $x_n$ such that $$|A x_n - b| < c\epsilon$$ where $\epsilon$ is the smallest singular value of $A$, due to$$\begin{align}|x_n - x| &= |A^{-1} A (x_n - x)| \\& \le \frac 1 \epsilon |A x_n - A x| \\& = \frac 1 \epsilon |A x_n - b| \\& < \frac 1 \epsilon \cdot c \epsilon = c\end{align}$$where we have used that $1/\epsilon$ is the largest singular value of $A^{-1}$ (second line) and that $x$ exactly solves $A x = b$ (third line).Estimating the smallest singular value $\epsilon$An accurate estimate of the smallest singular value is usually not directly available from the problem, but it can be estimated as a byproduct of a conjugate gradient or GMRES iteration. Note that although estimates of the largest eigenvalues and singular values is usually quite good after only a few iterations, an accurate estimate of the smallest eigen/singular value $\epsilon$ is usually only obtained once convergence is reached. Before convergence, the estimate will generally be significantly larger than the true value. This suggests that you must actually solve the equations before you can define the correct tolerance $c\epsilon$. An automatic convergence tolerance that takes a user-provided accuracy $c$ for the solution and estimates the smallest singular value $\epsilon$ with the current state of the Krylov method might converge too early because the estimate of $\epsilon$ was much larger than the true value.NotesThe above discussion also works with $A$ replaced by the left-preconditioned operator $P^{-1}A$ and the preconditioned residual $P^{-1} (A x^n - b)$ or with the right-preconditioned operator $A P^{-1}$ and the error $P (x_n - x)$. If $P^{-1}$ is a good preconditioner, the preconditioned operator will be well-conditioned. For left-preconditioning, this means the preconditioned residual can be made small, but the true residual may not be. For right preconditioning, $|P(x_n - x)|$ is easily made small, but the true error $|x_n-x|$ may not be. This explains why left-preconditioning is better for making error small while right-preconditioning is better for making the residual small (and for debugging unstable preconditioners).See this answer for more discussion of norms minimized by GMRES and CG.The estimates of extremal singular values can be monitored using -ksp_monitor_singular_value with any PETSc program. See KSPComputeExtremeSingularValues() to compute singular values from code.When using GMRES to estimate singular values, it is crucial that restarts not be used (e.g. -ksp_gmres_restart 1000 in PETSc).