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.math.analysis.solvers;
018    
019    import org.apache.commons.math.util.FastMath;
020    
021    /**
022     * Implements the <a href="http://mathworld.wolfram.com/Bisection.html">
023     * bisection algorithm</a> for finding zeros of univariate real functions.
024     * <p>
025     * The function should be continuous but not necessarily smooth.</p>
026     *
027     * @version $Id: BisectionSolver.java 1131229 2011-06-03 20:49:25Z luc $
028     */
029    public class BisectionSolver extends AbstractUnivariateRealSolver {
030        /** Default absolute accuracy. */
031        private static final double DEFAULT_ABSOLUTE_ACCURACY = 1e-6;
032    
033        /**
034         * Construct a solver with default accuracy (1e-6).
035         */
036        public BisectionSolver() {
037            this(DEFAULT_ABSOLUTE_ACCURACY);
038        }
039        /**
040         * Construct a solver.
041         *
042         * @param absoluteAccuracy Absolute accuracy.
043         */
044        public BisectionSolver(double absoluteAccuracy) {
045            super(absoluteAccuracy);
046        }
047        /**
048         * Construct a solver.
049         *
050         * @param relativeAccuracy Relative accuracy.
051         * @param absoluteAccuracy Absolute accuracy.
052         */
053        public BisectionSolver(double relativeAccuracy,
054                               double absoluteAccuracy) {
055            super(relativeAccuracy, absoluteAccuracy);
056        }
057    
058        /**
059         * {@inheritDoc}
060         */
061        @Override
062        protected double doSolve() {
063            double min = getMin();
064            double max = getMax();
065            verifyInterval(min, max);
066            final double absoluteAccuracy = getAbsoluteAccuracy();
067            double m;
068            double fm;
069            double fmin;
070    
071            while (true) {
072                m = UnivariateRealSolverUtils.midpoint(min, max);
073                fmin = computeObjectiveValue(min);
074                fm = computeObjectiveValue(m);
075    
076                if (fm * fmin > 0) {
077                    // max and m bracket the root.
078                    min = m;
079                } else {
080                    // min and m bracket the root.
081                    max = m;
082                }
083    
084                if (FastMath.abs(max - min) <= absoluteAccuracy) {
085                    m = UnivariateRealSolverUtils.midpoint(min, max);
086                    return m;
087                }
088            }
089        }
090    }