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