mathnet/mathnet-numerics — pull request #259 by hsidky (2014-10-25 21:46:50+00:00)
Title: Changed tolerance check and added bracket check.

This pull request fixes #255. After looking at the Brent's method source, I noticed the following:

There is no check to ensure that there is a sign change in the interval provided by the user. Brent's method is contingent on fact, otherwise, it will return, in all likelihood, a local minimum (assuming no root is exists within the bounds).

The convergence test is inconsistent. It does not make sense to check a relative tolerance against `xMid`, but an absolute tolerance against `froot`. Brent's method gives a `6*eps*|x| + tol` guarantee on the root, not the function residual. Doing this can lead to situations, like that reported by @colinfang, where the relative tolerance on `xmid` is met - so it can no longer change, but not the absolute tolerance on `froot` is not yet met. However, it is not possible to improve the accuracy, so the method returns a false negative.

It appears that this was indented behavior since someone added a check for this explicitly, but I don't think it is the best practice since the relationship between the relative error in `x`, and the absolute residual of `f(x)` is function dependent. I hope I was clear in this explanation.

Now, as for the consequences of my changes with respect to the unit tests:

In general, the tolerances specified on the tests will have to be higher (I have adjusted them), since Brent's method checks convergence on a relative tolerance. I don't think this is "inferior" to the previous implementation for the reasons stated above. It behaves as intended, and prevent situations where false negatives can be reported.

I also noticed that in one of the unit tests, the upper and lower bounds had the same sign. It used to pass because of lack of a check, but they don't any longer, so I just adjusted my selection.

Finally, I noticed some test cases from polymath did not converge with the previous convergence check. These are examples of functions with asymptotic behavior where it would not be possible to meet an absolute tolerance on `f(x)` with a relative tolerance on `x` (aka. false negative). Clearly, the roots are bracketed, and the whole point of Brent's method is that in such a scenario, a root is *guaranteed*.