**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*.

- More Details about Stopping Criteria
- When or is not readily available
- Estimating
- Stopping when progress is no longer being made
- Accounting for floating point errors