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