001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.math3.analysis.solvers;
018
019 import org.apache.commons.math3.util.FastMath;
020 import org.apache.commons.math3.exception.TooManyEvaluationsException;
021
022 /**
023 * Implements the <a href="http://mathworld.wolfram.com/Bisection.html">
024 * bisection algorithm</a> for finding zeros of univariate real functions.
025 * <p>
026 * The function should be continuous but not necessarily smooth.</p>
027 *
028 * @version $Id: BisectionSolver.java 1391927 2012-09-30 00:03:30Z erans $
029 */
030 public class BisectionSolver extends AbstractUnivariateSolver {
031 /** Default absolute accuracy. */
032 private static final double DEFAULT_ABSOLUTE_ACCURACY = 1e-6;
033
034 /**
035 * Construct a solver with default accuracy (1e-6).
036 */
037 public BisectionSolver() {
038 this(DEFAULT_ABSOLUTE_ACCURACY);
039 }
040 /**
041 * Construct a solver.
042 *
043 * @param absoluteAccuracy Absolute accuracy.
044 */
045 public BisectionSolver(double absoluteAccuracy) {
046 super(absoluteAccuracy);
047 }
048 /**
049 * Construct a solver.
050 *
051 * @param relativeAccuracy Relative accuracy.
052 * @param absoluteAccuracy Absolute accuracy.
053 */
054 public BisectionSolver(double relativeAccuracy,
055 double absoluteAccuracy) {
056 super(relativeAccuracy, absoluteAccuracy);
057 }
058
059 /**
060 * {@inheritDoc}
061 */
062 @Override
063 protected double doSolve()
064 throws TooManyEvaluationsException {
065 double min = getMin();
066 double max = getMax();
067 verifyInterval(min, max);
068 final double absoluteAccuracy = getAbsoluteAccuracy();
069 double m;
070 double fm;
071 double fmin;
072
073 while (true) {
074 m = UnivariateSolverUtils.midpoint(min, max);
075 fmin = computeObjectiveValue(min);
076 fm = computeObjectiveValue(m);
077
078 if (fm * fmin > 0) {
079 // max and m bracket the root.
080 min = m;
081 } else {
082 // min and m bracket the root.
083 max = m;
084 }
085
086 if (FastMath.abs(max - min) <= absoluteAccuracy) {
087 m = UnivariateSolverUtils.midpoint(min, max);
088 return m;
089 }
090 }
091 }
092 }