Stopping Rules for Jacobi/Gauss-Seidel Iteration Suppose that $A\mathbf{x}=\mathbf{b}$ is a diagonally dominant linear system. We can use iterative methods that produce a sequence of approximations $\mathbf{x}^1,\mathbf{x}^2,\dots$ that converge to $\mathbf{x}$.
Doing this for a small system it seems intuitive to stop when the components $x^i_j$ and $x^{i+1}_j$ differ by a tolerance $\varepsilon$ giving solutions correct to $\varepsilon$.
While playing around with larger systems it was clear that this could stop well before convergence and is a very poor stopping rule (and doesn't give accurate answers as claimed).
Researching a little further I see some slightly more sophisticated stopping rules (in the below the norms might be max norms or 2-norms):


*

*When $\|\mathbf{x}^{i+1}-\mathbf{x}^i\|< \varepsilon.$

*When $\|\mathbf{x}^{i+1}-\mathbf{x}^i\|< \varepsilon\|\mathbf{b}\|.$

*When $\displaystyle \max_j\left|\frac{x_j^{i+1}-x_j^i}{x_j^{i+1}}\right|<\varepsilon$.

*When the residual $\|\mathbf{r}\|=\|\mathbf{b}-A\mathbf{x}^i\|<\varepsilon$.

*When the residual $\|\mathbf{r}\|=\|\mathbf{b}-A\mathbf{x}^i\|<\varepsilon\|\mathbf{b}\|$.


I am interested in hearing the pros and cons of each. I am hoping to use one that is relatively easy to implement on VBA with perhaps 20 unknowns.
 A: Let's look at forward error bounds.
From normwise analysis we have
$$\frac{\|x-x^i\|}{\|x\|} \leq \frac{2\kappa(A)\epsilon_n}{1-\kappa(A)\epsilon_n},\ \  \epsilon_n = \frac{\|b - Ax^i\|}{\|A\|\|x^i\| + \|b\|} \tag{1}$$
where $\|\cdot\|$ is any vector norm and the corresponding subordinate matrix norm, and $\kappa(A) = \|A\|\|A^{-1}\|$ is the matrix condition number with respect to the norm  $\|\cdot\|$. Number $\epsilon_n$ is the normwise backward error obtained at $i$-th iteration. This is the only number, that can be controlled in this inequality.
From componentwise analysis we have:
$$\frac{\|x-x^i\|_\infty}{\|x\|_\infty} \leq \frac{2\eta(A)\epsilon_c}{1-\eta(A)\epsilon_c},\ \  \epsilon_c = \max_j\frac{|b - Ax^i|_j}{(|A||x^i| + |b|)_j} \tag{2}$$
where $\eta(A) = \||A^{-1}||A|\|_\infty$ is the Skeel condition number and $\epsilon_c$ is the componentwise backward error obtained at $i$-th iteration.
From (1) and (2) we can see, that none of provided stopping rules are particullary good. The best one is the last one since
$$\epsilon_n = \frac{\|b - Ax^i\|}{\|A\|\|x^i\| + \|b\|} \leq \frac{\|b - Ax^i\|}{\|b\|} \tag{3}$$
However condition (3) is too conservative, and as consequence the algorithm will perform too many iterations than required to obtain reasonably accurate solution.
Notice, that you can build a good stopping rule directly from (1) as
$$\|b - Ax^i\|_\infty \leq (\|A\|_\infty\|x^i\|_\infty + \|b\|_\infty)\times\epsilon \tag{4}$$
since $\|A\|_\infty$ can be easily estimated. Then the tolerance $\epsilon$ is just the normwise backward error.
Since generally componentwise error bounds are much better, than normwise bounds, a stopping rule based on (2) would be better than (4). Unfortunately this would require calculating $|A||x^i|$, which is not always possible.
