1
$\begingroup$

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^*$?

$\endgroup$
  • 5
    $\begingroup$ 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$. $\endgroup$ – Nick Alger Dec 1 at 2:49
  • $\begingroup$ It's also common to compare $r_{k}$ with $\| b \|$ rather than $r_{0}$. $\endgroup$ – Brian Borchers Dec 1 at 3:34
  • $\begingroup$ @BrianBorchers . Why compare $r_k$ with $b$ instead of $r_0=b-Ax_0$? i.e., why using zero vector guess, usually? $\endgroup$ – sunshine Dec 1 at 4:53
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.