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.solvers;
18  
19  import org.apache.commons.math.FunctionEvaluationException;
20  import org.apache.commons.math.MaxIterationsExceededException;
21  import org.apache.commons.math.analysis.UnivariateRealFunction;
22  
23  /**
24   * Implements the <a href="http://mathworld.wolfram.com/Bisection.html">
25   * bisection algorithm</a> for finding zeros of univariate real functions. 
26   * <p>
27   * The function should be continuous but not necessarily smooth.</p>
28   * 
29   * @version $Revision: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $
30   */
31  public class BisectionSolver extends UnivariateRealSolverImpl {
32      
33      /**
34       * Construct a solver for the given function.
35       * 
36       * @param f function to solve.
37       * @deprecated as of 2.0 the function to solve is passed as an argument
38       * to the {@link #solve(UnivariateRealFunction, double, double)} or
39       * {@link UnivariateRealSolverImpl#solve(UnivariateRealFunction, double, double, double)}
40       * method.
41       */
42      @Deprecated
43      public BisectionSolver(UnivariateRealFunction f) {
44          super(f, 100, 1E-6);
45      }
46  
47      /**
48       * Construct a solver.
49       * 
50       */
51      public BisectionSolver() {
52          super(100, 1E-6);
53      }
54  
55      /** {@inheritDoc} */
56      @Deprecated
57      public double solve(double min, double max, double initial)
58          throws MaxIterationsExceededException, FunctionEvaluationException {
59          return solve(f, min, max);
60      }
61      
62      /** {@inheritDoc} */
63      @Deprecated
64      public double solve(double min, double max)
65          throws MaxIterationsExceededException, FunctionEvaluationException {
66          return solve(f, min, max);
67      }
68  
69      /** {@inheritDoc} */
70      public double solve(final UnivariateRealFunction f, double min, double max, double initial)
71          throws MaxIterationsExceededException, FunctionEvaluationException {
72          return solve(min, max);
73      }
74  
75      /** {@inheritDoc} */
76      public double solve(final UnivariateRealFunction f, double min, double max)
77          throws MaxIterationsExceededException, FunctionEvaluationException {
78              
79          clearResult();
80          verifyInterval(min,max);
81          double m;
82          double fm;
83          double fmin;
84          
85          int i = 0;
86          while (i < maximalIterationCount) {
87              m = UnivariateRealSolverUtils.midpoint(min, max);
88             fmin = f.value(min);
89             fm = f.value(m);
90  
91              if (fm * fmin > 0.0) {
92                  // max and m bracket the root.
93                  min = m;
94              } else {
95                  // min and m bracket the root.
96                  max = m;
97              }
98  
99              if (Math.abs(max - min) <= absoluteAccuracy) {
100                 m = UnivariateRealSolverUtils.midpoint(min, max);
101                 setResult(m, i);
102                 return m;
103             }
104             ++i;
105         }
106         
107         throw new MaxIterationsExceededException(maximalIterationCount);
108     }
109 }