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: 1.18 $ $Date: 2004/07/17 21:19:39 $
    28   */
    29  public class BisectionSolver extends UnivariateRealSolverImpl {
    30
    31      /*** Serializable version identifier */
    32      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                  fmin = fm;
    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 ConvergenceException
    105             ("Maximum number of iterations exceeded: "  + maximalIterationCount);
    106     }
    107 }