View Javadoc

1   /*
2    * Copyright 2003-2004 The Apache Software Foundation.
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    *      http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
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                  // max and m bracket the root.
89                  min = m;
90              } else {
91                  // min and m bracket the root.
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 }