Methods that do not use the derivative
When the derivative of the function is not available, much less information is available to guess the location of the zero. Most methods that don't require a derivative do need to have an interval where a zero is known to exist. Such an interval is called a bracket, and such algorithms are collectively known as root bracketing solvers.
Root bracketing solvers work by bracketing the zero in an interval. The target function must be positive on one end of the interval, and negative on the other end. If the target function is continuous, this guarantees that the function has a zero in the interval.
The algorithm then proceeds by choosing a point within the interval that divides it into two subintervals. One of these intervals must still contain a zero of the function. This interval is taken as the starting point for the next iteration. Different algorithms use different methods to choose the next dividing point of an interval.
The RootBracketingSolver class
The RootBracketingSolver class is the abstract base class for all classes that implement root bracketing algorithms. It derives from EquationSolver, so all its properties and methods are available.
In addition, it defines two properties, LowerBound and UpperBound, that specifiy the lower and upper bounds of the initial bracketing interval.
All root bracketing solver classes have exactly the same methods and properties. Throughout this section, we will solve the equation
cos x = 0
in the interval [1,2]. The exact solution is, of course, Pi/2 = 1.5707963267948966...
The Bisection method
The bisection method is the simplest of the root bracketing algorithms. It works by dividing the bracketing interval into two equal parts in each iteration. It is implemented by the BisectionSolver class. Not taking into account round-off error, the number of iterations needed to achieve a certain accuracy can be estimated easily as the base 2 logarithm of the relative accuracy. It takes about 10 iterations to gain three digits in accuracy.
var solver = new BisectionSolver();
solver.LowerBound = 1;
solver.UpperBound = 2;
// The target function is a RealFunction.
// See above.
solver.TargetFunction = Math.Cos;
double result = solver.Solve();
// The Status property indicates the result of
// running the algorithm.
Console.WriteLine(" Result: {0}", solver.Status);
// The result is also available through the Result property.
Console.WriteLine(" Solution: {0}", solver.Result);
// You can find out the estimated error of the result
// through the EstimatedError property:
Console.WriteLine(" Estimated error: {0}", solver.EstimatedError);
Console.WriteLine(" # iterations: {0}", solver.IterationsNeeded);The Regula Falsi method
The regula falsi method, also called the method of false position, works by approximating the target function by a line. The bracketing interval is divided at the point where this line crosses the axis. The regula falsi method is superior to the bisection method in that it will, in most cases, converge faster.
Unfortunately, the algorithm can get 'stuck' in certain situations, and convergence may actually be slower than the bisection method. Our example of solving cos x = 0 in [1,2] happens to be such a situation. Solving sin x = 0 over [-0.5,1] does not have this problem.
The regula falsi method is implemented by the RegulaFalsiSolver class. A code sample follows:
var solver = new RegulaFalsiSolver();
solver.LowerBound = 1;
solver.UpperBound = 2;
solver.TargetFunction = Math.Cos;
double result = solver.Solve();
Console.WriteLine(" Result: {0}", solver.Status);
Console.WriteLine(" Solution: {0}", solver.Result);
Console.WriteLine(" Estimated error: {0}", solver.EstimatedError);
Console.WriteLine(" # iterations: {0}", solver.IterationsNeeded);The Dekker-Brent method
The Dekker-Brent method combines the robustness of the bisection method with the increased speed of the regula falsi method. At each iteration, either a bisection or a regula falsi step is taken, depending on the behavior of the algorithm up to that point. As a result, the Dekker-Brent method will converge as fast as the best case regula falsi method at its best, and as slow as the bisection method at its worst. The Dekker-Brent method is implemented by the DekkerBrentSolver class.
The Dekker-Brent method is an excellent root finding algorithm. It is suitable for functions whose derivative is not known and for badly behaved functions.
var solver = new DekkerBrentSolver();
solver.LowerBound = 1;
solver.UpperBound = 2;
solver.TargetFunction = Math.Cos;
double result = solver.Solve();
Console.WriteLine(" Result: {0}", solver.Status);
Console.WriteLine(" Solution: {0}", solver.Result);
Console.WriteLine(" Estimated error: {0}", solver.EstimatedError);
Console.WriteLine(" # iterations: {0}", solver.IterationsNeeded);The Robust Solver
In 1995, Alefeld, Potra, and Shi published an algorithm that is a refinement of the Dekker-Brent method that is more robust. The method is implemented by the RobustSolver class.
The robust solver is the most reliable of the root finding algorithms. It is recommended for functions whose derivative is not known and badly behaved functions.
var solver = new RobustSolver();
solver.LowerBound = 1;
solver.UpperBound = 2;
solver.TargetFunction = Math.Cos;
double result = solver.Solve();
Console.WriteLine(" Result: {0}", solver.Status);
Console.WriteLine(" Solution: {0}", solver.Result);
Console.WriteLine(" Estimated error: {0}", solver.EstimatedError);
Console.WriteLine(" # iterations: {0}", solver.IterationsNeeded);References
R. P. Brent, "An algorithm with guaranteed convergence for finding a zero of a function", Computer Journal, 14 (1971) 422-425
J. C. P. Bus and T. J. Dekker, "Two Efficient Algorithms with Guaranteed Convergence for Finding a Zero of a Function", ACM Transactions of Mathematical Software, Vol. 1 No. 4 (1975) 330-345