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

Question

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\|}<eps. $$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^*$?

Answer 1

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.