Stopping Criteria



next up previous contents index
Next: More Details about Up: Related Issues Previous: Complex Systems

Stopping Criteria

   

Stopping criterion: Since an iterative method computes successive approximations to the solution of a linear system, a practical test is needed to determine when to stop the iteration. Ideally this test would measure the distance of the last iterate to the true solution, but this is not possible. Instead, various other metrics are used, typically involving the residual. Forward error: The difference between a computed iterate and the true solution of a linear system, measured in some vector norm. Backward error: The size of perturbations of the coefficient matrix and of the right hand side of a linear system, such that the computed iterate is the solution of .

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

  1. identify when the error is small enough to stop,
  2. stop if the error is no longer decreasing or decreasing too slowly, and
  3. 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 :

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.





next up previous contents index
Next: More Details about Up: Related Issues Previous: Complex Systems



Jack Dongarra
Mon Nov 20 08:52:54 EST 1995