Re: Stopping criteria for iterative methods


In article <14657053.1161874267456.JavaMail.jakarta@xxxxxxxxxxxxxxxxxxxxxx>,
Blase <sunder_1600@xxxxxxxxx> writes:
I have questions regarding a) residual-based criterion and
b)consecutive approximation criterion for iterative methods: Jacobi,
Gauss Siedel and SOR. The residual-based criterion requires that we
multiply the norm of the vector r_n=b-Ax_n to the tolerance, not for the
consecutive approximation criterion which requires that we stop iterating
if the r_n < tol.


I don't uderstand what you mean here:
(*) stop if norm(r_n)<=tol*norm(r_0)
instead of
(**) stop if norm(r_n) <=tol ?




Looking at both these stopping criteria, I fail to comprehend the
rationale behind the residual stopping criteria. The second criterion
has advantages, that is whenever the algorithm stops, we are
sure that the norm would be less than the tolerance no matter what
our initial guess was, but if we were to use residual error, we cannot
make such claims.

To quote someone, "Also, you don't leave yourself vulnerable to the
vicissitudes of your initial guess. "

(**) implies that norm(x_n-x_true) /norm(x_true)<=cond(A)*tol
and (*) the analogous multiplied with norm(r_0).
this is useful if you know enough about cond(A).
there is possibly some trouble with (**):
if you fix tol and multiply A,b by tol, x does not change but the criterion
will be satisfied immediately (-> scale dependency)
multiplying with norm(r_0) you remove this, but clearly, if x_0 is bad,
then termination may occur too early


by "consecutive error criterion I had assumed something like
norm(x_n-x_{n-1}}/norm(x_n) <=tol
but this is useful only if you know something about the convergence rate
of the process, which, as a rule, depends on cond(A) and you have something like

norm(x_n-x_true)<=tol*norm(x_n)/(1-L) and L=1-const/cond(A)
(in the best case of SOR with omega_opt L=1-const/sqrt(cond(A)) )
again this gives you useful information only if you have enough knowledge about
cond(A)
hth
peter

.