8
$\begingroup$

Most numerical algorithms require an epsilon to be chosen in order to be robust and provide meaningful results. Choosing machine epsilon is usually too aggressive. Barring any special knowledge about your problem, one rule of thumb I remember is to use $\sqrt{\epsilon_{\text{machine}}}$. Eg: it's mentioned in this wikipedia article. Which basically is the same as assuming that half of the digits in your floating point number are bogus.

But I can't figure out where I got that rule of thumb. I just see it crop up, unreferenced, in various texts. Is there a source for it I could point someone to if they were uninformed about practical issues of numerical algorithms and naively trying to use machine epsilon?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
9
$\begingroup$

The Wikipedia article cite Numerical Recipes, 3rd edition, Section 5.7, which is pages 229-230 (a limited number of page views is available at http://www.nrbook.com/empanel/). Sure enough, they provide a derivation to demonstrate that using a one-sided difference quotient, $\sqrt{\varepsilon}$ is a good choice of step-size for finite difference approximations of derivatives. I don't know that $\sqrt{\varepsilon}$ would be great for other choices of algorithm in the absence of problem-specific information. For specific algorithms, you're probably better off trying to get information about your problem, using some reasonable strategies for trial-and-error with different choices of tolerance, and maybe looking up more detailed references for the specific algorithms you're using. A good catch-all reference I like to recommend is Accuracy and Stability of Numerical Algorithms by Nicholas Higham.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I love Numerical Recipes. The obsolete versions are free (start from that link on nr.com) and you can read the whole book. Basically finding a minimum gets the square root of epsilon while finding a root gets epsilon. You need to consider your specific problem. $\endgroup$
    – Ross Millikan
    Aug 12, 2014 at 3:13
  • $\begingroup$ Yes, it must have been from Numerical Recipes that I'd seen it. I think I also saw the 1e-6/1e-12 epsilon for floats/doubles for singular value clamping in the section on SVDs, misremembered that as 1e-5/1e-10, thought that they were the square roots of the machine epsilon, and got all mixed up. $\endgroup$
    – Jay Lemmon
    Aug 12, 2014 at 17:08
4
$\begingroup$

In the context of the forward difference method of numerical differentiation, the choice of a stepsize that is about $h=\sqrt{\epsilon_{\mbox{machine}}}$ can be justified by an analysis of the truncation and roundoff errors that occur- this particular choice minimizes the sum of the two errors. However, if you switch to a centered difference formula it turns out that $h=\epsilon_{\mbox{machine}}^{1/3}$ is optimal.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.