View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  package org.apache.commons.math.analysis;
18  
19  import org.apache.commons.math.FunctionEvaluationException;
20  import org.apache.commons.math.MaxIterationsExceededException;
21  
22  /**
23   * Implements the <a href="http://mathworld.wolfram.com/Bisection.html">
24   * bisection algorithm</a> for finding zeros of univariate real functions. 
25   * <p>
26   * The function should be continuous but not necessarily smooth.</p>
27   * 
28   * @version $Revision: 615734 $ $Date: 2008-01-27 23:10:03 -0700 (Sun, 27 Jan 2008) $
29   */
30  public class BisectionSolver extends UnivariateRealSolverImpl {
31      
32      /** Serializable version identifier */
33      private static final long serialVersionUID = 4963578633786538912L;
34  
35      /**
36       * Construct a solver for the given function.
37       * 
38       * @param f function to solve.
39       */
40      public BisectionSolver(UnivariateRealFunction f) {
41          super(f, 100, 1E-6);
42      }
43  
44      /**
45       * Find a zero in the given interval.
46       * 
47       * @param min the lower bound for the interval.
48       * @param max the upper bound for the interval.
49       * @param initial the start value to use (ignored).
50       * @return the value where the function is zero
51       * @throws MaxIterationsExceededException the maximum iteration count is exceeded 
52       * @throws FunctionEvaluationException if an error occurs evaluating
53       *  the function
54       * @throws IllegalArgumentException if min is not less than max
55       */
56      public double solve(double min, double max, double initial)
57          throws MaxIterationsExceededException, FunctionEvaluationException {
58            
59          return solve(min, max);
60      }
61      
62      /**
63       * Find a zero root in the given interval.
64       * 
65       * @param min the lower bound for the interval
66       * @param max the upper bound for the interval
67       * @return the value where the function is zero
68       * @throws MaxIterationsExceededException if the maximum iteration count is exceeded.
69       * @throws FunctionEvaluationException if an error occurs evaluating the
70       * function
71       * @throws IllegalArgumentException if min is not less than max
72       */
73      public double solve(double min, double max) throws MaxIterationsExceededException,
74          FunctionEvaluationException {
75          
76          clearResult();
77          verifyInterval(min,max);
78          double m;
79          double fm;
80          double fmin;
81          
82          int i = 0;
83          while (i < maximalIterationCount) {
84              m = UnivariateRealSolverUtils.midpoint(min, max);
85             fmin = f.value(min);
86             fm = f.value(m);
87  
88              if (fm * fmin > 0.0) {
89                  // max and m bracket the root.
90                  min = m;
91              } else {
92                  // min and m bracket the root.
93                  max = m;
94              }
95  
96              if (Math.abs(max - min) <= absoluteAccuracy) {
97                  m = UnivariateRealSolverUtils.midpoint(min, max);
98                  setResult(m, i);
99                  return m;
100             }
101             ++i;
102         }
103         
104         throw new MaxIterationsExceededException(maximalIterationCount);
105     }
106 }