-
Notifications
You must be signed in to change notification settings - Fork 1
Rationale: tolerances
-
Relative tolerance is specified with respect to the expected value (not the received value, or the maximum of the two (how would you do that with a vector?), or any other combination).
-
You don't need to divide by the expected value to apply the relative tolerance, thereby avoiding the risk of division by zero. Instead of doing
abs((got - expected) / expected) < rtolyou can also compare
abs(got - expected) < rtol * abs(expected)In case the expected value is zero, this reduces to
abs(got) < 0which is the correct interpretation, but impossible to satisfy. However, this need not be a problem if an absolute tolerance is also supplied, and if the absolute and relative stopping criterion are ORed (rather than ANDed).
-
One could argue that the only meaningful tolerance is a relative one ("the result should not deviate more than 1% from the specified value"), and that an absolute tolerance is really a relative tolerance for numbers that happen to have an order of magnitude around unity. It doesn't really make sense to expect that values spanning many orders of magnitude all satisfy the expected values within an absolute tolerance of, say, 1e-6. That value would be meaningless for expected values of, say, 1e-10, and impossible for expected values of, say, 1e+8.
The case where an absolute tolerance is very useful, is when the expected value is very close or equal to zero. One particular example: a Jacobian entry of 1e-10 is more of a qualitative statement ("very small") than a quantitative statement. In other words, it is more or less OK if a Jacobian entry of 3.78e-10 passes an approximate equality test with an expected value of 1e-10 (in a Jacobian where the elements are otherwise of the order of magnitude 1), even though the relative error is almost 400%!
-
Passing the test if either the relative tolerance or the absolute tolerance is met has the following advantages:
1. Backward compatibilty with existing software: what used to pass will continue to pass. 2. What used to fail but now passes are tests against expected values of high order of magnitude. -
TOLERANCE could be made a synonym of ATOL for backwards compatibility.
-
Sanity checking and backwards compatibility:
If an absolute and relative tolerance are both specified, and the test passes if either tolerance is met, and fails if none are met, then:
* what used to pass and should pass will continue to pass: * any value below absolute tolerance - since conditions are ORed, anything that used to pass will continue to pass * what used to pass but shouldn't pass: * (value below absolute tolerance but above relative tolerance) * nothing? anything that passed used to be very small, below the absolute tolerance, and one could argue that relative error doesn't matter for very small values as discussed in the Jacobian entry example * what used to fail: * value exceeding absolute tolerance but meeting relative tolerance (large value) - should pass and will pass due to ORing of conditions * value exceeding absolute tolerance and not meeting relative tolerance (small value) - should fail and will fail due to either condition not being met
-
"Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods" does not seem to have an absolute tolerance. (http://www.netlib.org/templates/templates.pdf)
-
A question on StackExchange: (https://math.stackexchange.com/questions/909855/why-does-quadpack-only-enforce-the-least-strict-error-boundary)
"The idea is that generally, the relative error boundary is the one that one would like to fulfill. However, when approaching very small [integral] values, the error boundary imposed by the relative tolerance becomes extremely small. It is in this case that the absolute error boundary is used as a more practical restriction."which itself is a reference to the following question on MathWorks (https://www.mathworks.com/matlabcentral/answers/26743-absolute-and-relative-tolerance-definitions)
-
QUADPACK uses the following criterion: (http://linux.math.tifr.res.in/manuals/html/gsl-ref-html/gsl-ref_16.html#SEC244)
|RESULT - I| <= max(epsabs, epsrel |I|) -
Another useful discussion at StackOverflow: (https://stackoverflow.com/questions/8961844/relative-and-absolute-tolerance-definitions-in-matlab-solver)
"When you perform an optimization, you need to decide when to stop. One way to check for whether your solution is good enough is to check whether the solution is still changing significantly. There are two ways to measure how much a solution changes: relative change (i.e. % change), or absolute change. It makes a lot of sense to check for relative change, since a change of 5 means something very different when the solution is around 1 than when it is around 100000. Thus, the optimization routine checks, at every iteration i whether abs(1-x(i)/x(i-1))<relTol, i.e. by what fraction the new solution has changed since the last iteration. Note that x can be an array of solutions if you're optimizing multiple parameters at the same time (the solution thus has "multiple components"). Of course, you want the condition to be fulfilled for all "solution components" before you stop optimizing further. The relative tolerance, however, becomes problematic when the solution is around zero, since x/0 is undefined. Thus, it makes sense to also look at the absolute change in value, and quit optimizing when abs(x(i)-x(i-1))<absTol. If you choose absTol small enough, it will only be relTol that counts for large solutions, while absTol only becomes relevant if the solution comes to lie around 0. Since the solver stops when either of the two criterion is fulfilled, how close you get to a (locally) optimal solution is determined by absTol or relTol. For example, if relTol is 10%, you will never get much closer than 10% to the optimal solution, unless your solution is around zero, in which case the absTol criterion (of, say, 0.0001) is satisfied before the relTol criterion."Note the sentence "[...] the solver stops when either of the two criteri[a] is fulfilled [...]".
-
In the examples to Matlab unit tests, relative and absolute tolerance are also combined by ORing: (https://nl.mathworks.com/help/matlab/ref/matlab.unittest.constraints.relativetolerance-class.html)
In the example "Combine Absolute and Relative Tolerances to Test Small and Large Values":
Combine tolerances so when you test the equality of values, an absolute (floor) tolerance dominates when the values are near zero, and a relative tolerance dominates for larger values. Define two structures containing electromagnetic properties of a vacuum. One structure, approxVacuumProps, contains approximate values for the permeability and speed of light in a vacuum. Test that the relative difference between the approximate and baseline values is within eps*1e11. The test fails because the relative difference in the permeabilities is not within the tolerance. The difference between the two values is small, but the numbers are close to zero, so the difference relative to their size is not small enough to satisfy the tolerance. Construct a tolerance object to test that the absolute difference between the approximate and baseline values is within 1e-4. The test fails because the absolute difference in the speed of light is not within the tolerance. The difference between the two values is small relative to their size, but too large to satisfy the tolerance. Construct a logical disjunction of tolerance objects to test that the absolute difference between the approximate and baseline values is within 1e-4 or the relative difference is within eps*1e11. The test uses this tolerance so permeability values that are close to zero satisfy the absolute (floor) tolerance, and speed of light values that are large, satisfy the relative tolerance. -
There is a discussion in the Knitro documentation that argues
minshould be used instead ofmax: (https://www.artelys.com/tools/knitro_doc/2_userGuide/termination.html)Knitro stops and declares locally optimal solution found if the following stopping conditions are satisfied: FeasErr <= min( tau_1 * feastol, feastol_abs ) OptErr <= min( tau_2 * opttol, opttol_abs ) where feastol, opttol, feastol_abs, and opttol_abs are constants defined by user options. Note: Please be aware that the min function in (stop1)-(stop2) was a max function in versions of Knitro previous to Knitro 9.0, and the default values for the user option tolerances were also changed. The changes were made to prevent cases where Knitro might declare optimality with very large absolute errors (but small relative errors), or incorrectly declare optimality on unbounded models. This stopping test is designed to give the user much flexibility in deciding when the solution returned by Knitro is accurate enough. By default, Knitro uses a scaled stopping test, while also enforcing that some minimum absolute tolerances for feasibility and optimality are satisfied. One can use a purely absolute stopping test by setting feastol_abs <= feastol and opttol_abs <= opttol.However, I fail to see the point for my application: if the relative error is small, does it matter if the absolute error is large?
-
Scilab seems to use a combination of relative and absolute tolerance: (https://help.scilab.org/doc/5.5.2/en_US/optimbase_terminate.html)
norm(currentxopt - previousxopt) < tolxrelative * norm(currentxopt) + tolxabsolute -
DNSQE: TOL is a relative tolerance. (http://rsusu1.rnd.runnet.ru/develop/fortran/slatec/DNSQE.html)
-
ODEPACK: DLSODE has both relative and absolute tolerances: (https://people.sc.fsu.edu/~jburkardt/f77_src/odepack/odepack.f)
RTOL :IN Relative tolerance parameter (scalar). ATOL :IN Absolute tolerance parameter (scalar or array). If ITOL = 1, ATOL need not be dimensioned. If ITOL = 2, ATOL must be dimensioned at least NEQ. The estimated local error in Y(i) will be controlled so as to be roughly less (in magnitude) than EWT(i) = RTOL*ABS(Y(i)) + ATOL if ITOL = 1, or EWT(i) = RTOL*ABS(Y(i)) + ATOL(i) if ITOL = 2. Thus the local error test passes if, in each component, either the absolute error is less than ATOL (or ATOL(i)), or the relative error is less than RTOL. Use RTOL = 0.0 for pure absolute error control, and use ATOL = 0.0 (or ATOL(i) = 0.0) for pure relative error control. Caution: Actual (global) errors may exceed these local tolerances, so choose them conservatively.And further:
RTOL A relative error tolerance parameter, either a scalar or an array of length NEQ. See description below under ATOL. Input only. ATOL An absolute error tolerance parameter, either a scalar or an array of length NEQ. Input only. The input parameters ITOL, RTOL, and ATOL determine the error control performed by the solver. The solver will control the vector e = (e(i)) of estimated local errors in Y, according to an inequality of the form rms-norm of ( e(i)/EWT(i) ) <= 1, where EWT(i) = RTOL(i)*ABS(Y(i)) + ATOL(i), and the rms-norm (root-mean-square norm) here is rms-norm(v) = SQRT(sum v(i)**2 / NEQ). Here EWT = (EWT(i)) is a vector of weights which must always be positive, and the values of RTOL and ATOL should all be nonnegative. The following table gives the types (scalar/array) of RTOL and ATOL, and the corresponding form of EWT(i). ITOL RTOL ATOL EWT(i) ---- ------ ------ ----------------------------- 1 scalar scalar RTOL*ABS(Y(i)) + ATOL 2 scalar array RTOL*ABS(Y(i)) + ATOL(i) 3 array scalar RTOL(i)*ABS(Y(i)) + ATOL 4 array array RTOL(i)*ABS(Y(i)) + ATOL(i) When either of these parameters is a scalar, it need not be dimensioned in the user's calling program. If none of the above choices (with ITOL, RTOL, and ATOL fixed throughout the problem) is suitable, more general error controls can be obtained by substituting user-supplied routines for the setting of EWT and/or for the norm calculation. See Part 4 below. If global errors are to be estimated by making a repeated run on the same problem with smaller tolerances, then all components of RTOL and ATOL (i.e., of EWT) should be scaled down uniformly.