1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 package org.apache.commons.math.analysis;
17
18 import org.apache.commons.math.FunctionEvaluationException;
19 import org.apache.commons.math.ConvergenceException;
20
21 /**
22 * Implements the <a href="http://mathworld.wolfram.com/Bisection.html">
23 * bisection algorithm</a> for finding zeros of univariate real functions.
24 * <p>
25 * The function should be continuous but not necessarily smooth.
26 *
27 * @version $Revision: 348519 $ $Date: 2005-11-23 12:12:18 -0700 (Wed, 23 Nov 2005) $
28 */
29 public class BisectionSolver extends UnivariateRealSolverImpl {
30
31 /** Serializable version identifier */
32 private static final long serialVersionUID = 7137520585963699578L;
33
34 /**
35 * Construct a solver for the given function.
36 *
37 * @param f function to solve.
38 */
39 public BisectionSolver(UnivariateRealFunction f) {
40 super(f, 100, 1E-6);
41 }
42
43 /**
44 * Find a zero in the given interval.
45 *
46 * @param min the lower bound for the interval.
47 * @param max the upper bound for the interval.
48 * @param initial the start value to use (ignored).
49 * @return the value where the function is zero
50 * @throws ConvergenceException the maximum iteration count is exceeded
51 * @throws FunctionEvaluationException if an error occurs evaluating
52 * the function
53 * @throws IllegalArgumentException if min is not less than max
54 */
55 public double solve(double min, double max, double initial)
56 throws ConvergenceException, FunctionEvaluationException {
57
58 return solve(min, max);
59 }
60
61 /**
62 * Find a zero root in the given interval.
63 *
64 * @param min the lower bound for the interval
65 * @param max the upper bound for the interval
66 * @return the value where the function is zero
67 * @throws ConvergenceException if the maximum iteration count is exceeded.
68 * @throws FunctionEvaluationException if an error occurs evaluating the
69 * function
70 * @throws IllegalArgumentException if min is not less than max
71 */
72 public double solve(double min, double max) throws ConvergenceException,
73 FunctionEvaluationException {
74
75 clearResult();
76 verifyInterval(min,max);
77 double m;
78 double fm;
79 double fmin;
80
81 int i = 0;
82 while (i < maximalIterationCount) {
83 m = UnivariateRealSolverUtils.midpoint(min, max);
84 fmin = f.value(min);
85 fm = f.value(m);
86
87 if (fm * fmin > 0.0) {
88
89 min = m;
90 } else {
91
92 max = m;
93 }
94
95 if (Math.abs(max - min) <= absoluteAccuracy) {
96 m = UnivariateRealSolverUtils.midpoint(min, max);
97 setResult(m, i);
98 return m;
99 }
100 ++i;
101 }
102
103 throw new ConvergenceException
104 ("Maximum number of iterations exceeded: " + maximalIterationCount);
105 }
106 }