    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    }