0
$\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.

I heard that a saying goes that

This criterion often depends on the initial iterate $x_0$, and may result in unnecessary work when $x_0$ is good and may result in a poor result when the $x_0$ is far from the solution. For this reason, we prefer to terminate the iteration as follows: $$ \frac{\|r_k\|}{\|r_0\|}=\frac{\|b-Ax_k\|}{\|b\|}<eps $$

It means that the usual choice for $x_0$ is that zero vector. But I do not understand why we will get unnecessary work and poor result said above if $x_0$ is chosen inappropriately? What's more, why when we choose zero vector as initial guess, the problem about unnecessary work and poor result can be overcome? Because using zero vector may also result in the above problem about unnecessary work and poor result. any hints are welcom.

Another question 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$
  • $\begingroup$ There are two very different questions inside of one. It is strongly suggested to have one question per post. $\endgroup$ – Anton Menshov Nov 30 '19 at 14:04
  • 1
    $\begingroup$ This question probably should answer the first part of the initial guess. This answer of mine is also slightly related despite the question being a bit more on the software side. $\endgroup$ – Anton Menshov Nov 30 '19 at 14:05

Your Answer

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

Browse other questions tagged or ask your own question.