Previous: Complex Systems
Up: Related Issues
Next: Data Structures
Previous Page: Complex Systems
Next Page: More Details about Stopping Criteria
An iterative method produces a sequence 
of vectors
converging to the vector 
satisfying the 
system 
.
To be effective, a method must decide when to stop. A good stopping
criterion should
- identify when the error
is small
enough to stop,
- stop if the error is no longer decreasing or decreasing too slowly, and
- limit the maximum amount of time spent iterating.
For the user wishing to read as little as possible,
the following simple stopping criterion will likely be adequate.
The user must supply the quantities
, 
, stop_tol, and preferably also 
:
- The integer is the maximum number of iterations the algorithm
will be permitted to perform.
- The real number is a norm of
. Any reasonable
(order of magnitude) approximation of the absolute value of
the largest entry of the matrix will do.
- The real number is a norm of
. Again, any
reasonable approximation of the
absolute value of the largest entry of will do.
- The real number stop_tol measures how small the user wants
the residual
of the ultimate solution
to be. One way to choose stop_tol is as the
approximate uncertainty in the entries of and relative to
and , respectively. For example, choosing stop_tol
means that the user considers the entries of and
to have errors in the range 
and 
, respectively. The algorithm will compute no more
accurately than its inherent uncertainty warrants. The user should
choose stop_tol less than one and greater than the machine
precision 
.
Here is the algorithm:
Note that if 
does not change much from step to step, which occurs
near convergence, then 
need not be recomputed.
If is not available, the stopping criterion may be replaced with
the generally stricter criterion
In either case, the final error bound is
.
If an estimate of 
is available, one may also use the stopping
criterion
which guarantees that the relative error 
in the computed solution is bounded by stop_tol.
Previous: Complex Systems
Up: Related Issues
Next: Data Structures
Previous Page: Complex Systems
Next Page: More Details about Stopping Criteria