Previous: Stopping Criteria
Up: Stopping Criteria
Next: When or
is not readily available
Previous Page: Stopping Criteria
Next Page: When or
is not readily available
Ideally we would like to stop when the magnitudes of entries of the error
fall below a user-supplied threshold.
But
is hard to estimate directly, so
we use the residual
instead, which is
more readily computed. The rest of this section describes how to measure
the sizes of vectors
and
, and how to bound
in terms of
.
We will measure errors using vector and matrix norms. The most common vector norms are:
For some algorithms we may also use the norm
, where
is a fixed nonsingular
matrix and
is one of
, 1, or 2.
Corresponding to these vector norms are three matrix norms:
as well as .
We may also use the matrix norm
, where
denotes the largest eigenvalue.
Henceforth
and
will refer to any mutually
consistent pair of the above.
(
and
, as well as
and
, both form
mutually consistent pairs.)
All these norms satisfy the triangle inequality
and
, as well as
for mutually consistent pairs.
(For more details on the properties of norms, see Golub and
Van Loan [108].)
One difference between these norms is their dependence on dimension.
A vector of length n with entries uniformly distributed between
0 and 1 will satisfy
, but
will grow
like
and
will grow like n. Therefore a stopping
criterion based on
(or
) may have to be permitted to
grow proportional to n (or
) in order that it does not become
much harder to satisfy for large n.
There are two approaches to bounding the
inaccuracy of the computed solution to .
Since
,
which we will call the forward error,
is hard to estimate directly,
we introduce
the backward error, which allows us to bound the forward error.
The normwise backward error is defined as
the smallest possible value of
where
is the exact solution of
(here
denotes a general matrix, not
times
; the
same goes for
).
The backward error may be easily computed from the residual
; we show how below.
Provided one has
some bound on the inverse of
,
one can bound the forward error in terms of the backward error via
the simple equality
which implies
.
Therefore, a stopping criterion of the form ``stop when
'' also yields an upper bound on the forward error
. (Sometimes we may prefer to
use the stricter but harder to estimate bound
; see §
. Here
is the matrix or vector of absolute values of components of
.)
The backward error also has a direct interpretation as a stopping
criterion, in addition to supplying a bound on the forward error.
Recall that the backward error is the smallest change
to the problem
that makes
an exact solution of
. If the original data
and
have
errors from previous computations or measurements,
then it is usually not worth iterating until
and
are even
smaller than these errors.
For example, if the machine precision is
, it is not
worth making
and
, because just rounding the entries
of
and
to fit in the machine creates errors this large.
Based on this discussion, we discuss some stopping criteria and their properties. The first one we discussed above is
The second stopping criterion we discussed, which does not require ,
may be much more stringent than Criterion 1:
If an estimate of is available, one can also just stop
when the upper bound on the error
falls below
a threshold. This yields the third stopping criterion:
One drawback to Criteria 1 and 2 is that they usually treat backward errors in
each component of and
equally, since most
norms
and
measure each entry of
and
equally.
For example, if
is sparse and
is dense, this loss of
possibly important structure will not be reflected in
.
In contrast, the following stopping criterion gives one the option of scaling
each component
and
differently,
including the possibility of insisting that some entries be zero.
The cost is an extra matrix-vector multiply:
Finally, we mention one more criterion, not because we recommend it, but because it is widely used. We mention it in order to explain its potential drawbacks: