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    }