# Why do not we choose the error solution norm as an iterative method's criterion?

For solving linear system $$Ax=b,$$ using iterative mehods, we often use the terminate criterion as follows: $$\frac{\|r_k\|}{\|r_0\|}=\frac{\|b-Ax_k\|}{\|b-Ax_0\|}where $$x_0$$ is the initial guess and $$x_k$$ is the $$k$$-th step iterate.

My question is why do not we use the real terminate criterion instead as follows: because $$\frac{\|x_k-x^*\|}{\|x_0-x^*\|}\leq k(A)\frac{\|r_k\|}{\|r_0\|}$$ where k(A) is the condition number. I want to ask that: Is there a case when the residual criterion satisfied but the condition number is so large that the k-th step iterate is still far from the real solution $$x^*$$?

• Evaluating the error typically requires knowing the solution, $x^*$. But this quantity is unknown (it is what we are trying to find). In contrast, evaluating the residual simply requires knowing the iterate $x_k$. Commented Dec 1, 2019 at 2:49
• It's also common to compare $r_{k}$ with $\| b \|$ rather than $r_{0}$. Commented Dec 1, 2019 at 3:34
• @BrianBorchers . Why compare $r_k$ with $b$ instead of $r_0=b-Ax_0$? i.e., why using zero vector guess, usually? Commented Dec 1, 2019 at 4:53

We can't use the criterion you show last in practice because it requires us to know what $$\kappa(A)$$ is. But computing the condition number is, in general, more expensive than solving a linear system. As a consequence, the criterion you show is not practical.
That only leaves us with variants of the criterion $$\frac{\|r_k\|}{\|r_0\|}=\frac{\|b-Ax_k\|}{\|b-Ax_0\|}\le eps.$$ I'll argue that that is not a good criterion because the accuracy of the final iterate now depends on your choice of initial guess $$x_0$$. In particular, if you happened to have a really good initial guess already, you'd still have to do many many iterations to get that ratio below your tolerance. Rather, what one typically does is to require $$\frac{\|r_k\|}{\|b\|}=\frac{\|b-Ax_k\|}{\|b\|}\le eps.$$ This way, you normalize everything to the ratio you would get if you were to start with $$x_0=0$$ -- but if you happen to have a better starting guess, that's fine and you just have to do fewer iterations.