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.math3.analysis.solvers;
18  
19  import org.apache.commons.math3.util.FastMath;
20  import org.apache.commons.math3.exception.TooManyEvaluationsException;
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 $Id: BisectionSolver.java 1391927 2012-09-30 00:03:30Z erans $
29   */
30  public class BisectionSolver extends AbstractUnivariateSolver {
31      /** Default absolute accuracy. */
32      private static final double DEFAULT_ABSOLUTE_ACCURACY = 1e-6;
33  
34      /**
35       * Construct a solver with default accuracy (1e-6).
36       */
37      public BisectionSolver() {
38          this(DEFAULT_ABSOLUTE_ACCURACY);
39      }
40      /**
41       * Construct a solver.
42       *
43       * @param absoluteAccuracy Absolute accuracy.
44       */
45      public BisectionSolver(double absoluteAccuracy) {
46          super(absoluteAccuracy);
47      }
48      /**
49       * Construct a solver.
50       *
51       * @param relativeAccuracy Relative accuracy.
52       * @param absoluteAccuracy Absolute accuracy.
53       */
54      public BisectionSolver(double relativeAccuracy,
55                             double absoluteAccuracy) {
56          super(relativeAccuracy, absoluteAccuracy);
57      }
58  
59      /**
60       * {@inheritDoc}
61       */
62      @Override
63      protected double doSolve()
64          throws TooManyEvaluationsException {
65          double min = getMin();
66          double max = getMax();
67          verifyInterval(min, max);
68          final double absoluteAccuracy = getAbsoluteAccuracy();
69          double m;
70          double fm;
71          double fmin;
72  
73          while (true) {
74              m = UnivariateSolverUtils.midpoint(min, max);
75              fmin = computeObjectiveValue(min);
76              fm = computeObjectiveValue(m);
77  
78              if (fm * fmin > 0) {
79                  // max and m bracket the root.
80                  min = m;
81              } else {
82                  // min and m bracket the root.
83                  max = m;
84              }
85  
86              if (FastMath.abs(max - min) <= absoluteAccuracy) {
87                  m = UnivariateSolverUtils.midpoint(min, max);
88                  return m;
89              }
90          }
91      }
92  }