Java- Commons.Math BrentSolver returns NoBracketingException. Is this a bug?

Question

I wrote a test program to review the BrentSolver class through the Apache Commons Math library.

import java.util.TreeSet;
import org.apache.commons.math3.analysis.UnivariateFunction;
import org.apache.commons.math3.analysis.solvers.*;

public class TestBrent {
    public static void main(String[] args) {
        BrentSolver test2 = new BrentSolver(1E-10);       
        UnivariateFunction func = (double x) -> Math.sin(x);

        TreeSet<Double> set = new TreeSet<>();
        for (int i = 1; i <= 500; i++) {
            set.add(test2.solve(1000, func, i, i+1));
        }
        for (Double s : set) {
            if(s > 0)
            System.out.println(s);
        }
    }
}

When running the program, the following error is returned

Exception in thread "main" org.apache.commons.math3.exception.NoBracketingException: function values at endpoints do not have different signs, endpoints: [1, 2], values: [0.841, 0.909]
    at org.apache.commons.math3.analysis.solvers.BrentSolver.doSolve(BrentSolver.java:133)
    at org.apache.commons.math3.analysis.solvers.BaseAbstractUnivariateSolver.solve(BaseAbstractUnivariateSolver.java:199)
    at org.apache.commons.math3.analysis.solvers.BaseAbstractUnivariateSolver.solve(BaseAbstractUnivariateSolver.java:204)
    at TestBrent.main(TestBrent.java:12)
Java Result: 1

Removing the if statement allows the program to find the root.

import java.util.TreeSet;
import org.apache.commons.math3.analysis.UnivariateFunction;
import org.apache.commons.math3.analysis.solvers.*;

public class TestBrent {
    public static void main(String[] args) {
        BrentSolver test2 = new BrentSolver(1E-10);       
        UnivariateFunction func = (double x) -> Math.sin(x);

        System.out.println(test2.solve(1000, func, 1, 4));

    }
}

Is this a bug inside the Apache Commons Math library? All of the root finding algorithms (outside of Newton's method) appear to have the same bug.

Answer 1

No, this is not a bug. The error is telling you that your function (in this case sin(x)) has the same sign evaluated at x==1 as it does for x==2. It is indicating that the interval you passed to it has no root within it. To work reliably, the solver needs to be passed an interval with one root in it. The crude check for that is that the signs of the function for the interval bounds are different (of course that doesn't preclude the interval containing several roots...). See the docs, which say:

A solver may require that the interval brackets a single zero root.

In your first example, the for loop will pass the solver different intervals ([1,2],[2,3] and so on). Some will have roots in, some won't. Unfortunately, the for loop never gets past the first iteration because there is no root between 1 and 2.

In your second example, you pass the solver the interval [1,4]. Of course, sin(x) does have a root between those points at x=PI.

It's the conditioning of your problem that is giving rise to the error, not a bug in the library.

---

If you want to use the first formulation - you could surround the line

set.add(test2.solve(1000, func, i, i+1));

with a try...catch loop like:

try {
    set.add(test2.solve(1000, func, i, i+1));
}
catch (NoBracketingException e) {
    System.err.println("Oops - error.  Likely cause: No root in interval ["+i+","+(i+1)+"]");
    System.err.println(e.message());
}