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