Brent's Method

When searching for a real simple root of a real valued function, it is possible to take advantage of the special geometry of the problem, where the function crosses the axis from negative to positive or vice versa. Brent's method [Br02] is effectively a safeguarded secant method that always keeps a point where the function is positive and one where it is negative so that the root is always bracketed. At any given step, a choice is made between an interpolated (secant) step and a bisection in such a way that eventual convergence is guaranteed.

If (RefLink[FindRoot, paclet:ref/FindRoot]) is given two real starting conditions that bracket a root of a real function, then Brent's method will be used. Thus, if you are working in one dimension and can determine initial conditions that will bracket a root, it is often a good idea to do so since Brent's method is the most robust algorithm available for (RefLink[FindRoot, paclet:ref/FindRoot]).

Even though essentially all the theory for solving nonlinear equations and local minimization is based on smooth functions, Brent's method is sufficiently robust that you can even get a good estimate for a zero crossing for discontinuous functions.

This loads a package that contains some utility functions:

<<Optimization`UnconstrainedProblems`

This shows the steps and function evaluations used in an attempt to find the root of a discontinuous function:

FindRootPlot[2 UnitStep[Sin[x]]-1,{x,3,4}]

The method gives up and issues a message when the root is bracketed very closely, but it is not able to find a value of the function, which is zero. This robustness carries over very well to continuous functions that are very steep.

This shows the steps and function evaluations used to find the root of a function that varies rapidly near its root:

FindRootPlot[ArcTan[10000 Sin[x] ],{x,3,4}, PlotRange->All]