    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.FunctionEvaluationException;
    020    import org.apache.commons.math.MaxIterationsExceededException;
    021    import org.apache.commons.math.analysis.UnivariateRealFunction;
    022    import org.apache.commons.math.util.FastMath;
    023
    024    /**
    025     * Implements the <a href="http://mathworld.wolfram.com/Bisection.html">
    026     * bisection algorithm</a> for finding zeros of univariate real functions.
    027     * <p>
    028     * The function should be continuous but not necessarily smooth.</p>
    029     *
    030     * @version $Revision: 1070725 $ $Date: 2011-02-15 02:31:12 +0100 (mar. 15 f??vr. 2011) $
    031     */
    032    public class BisectionSolver extends UnivariateRealSolverImpl {
    033
    034        /**
    035         * Construct a solver for the given function.
    036         *
    037         * @param f function to solve.
    038         * @deprecated as of 2.0 the function to solve is passed as an argument
    039         * to the {@link #solve(UnivariateRealFunction, double, double)} or
    040         * {@link UnivariateRealSolverImpl#solve(UnivariateRealFunction, double, double, double)}
    041         * method.
    042         */
    043        @Deprecated
    044        public BisectionSolver(UnivariateRealFunction f) {
    045            super(f, 100, 1E-6);
    046        }
    047
    048        /**
    049         * Construct a solver.
    050         *
    051         */
    052        public BisectionSolver() {
    053            super(100, 1E-6);
    054        }
    055
    056        /** {@inheritDoc} */
    057        @Deprecated
    058        public double solve(double min, double max, double initial)
    059            throws MaxIterationsExceededException, FunctionEvaluationException {
    060            return solve(f, min, max);
    061        }
    062
    063        /** {@inheritDoc} */
    064        @Deprecated
    065        public double solve(double min, double max)
    066            throws MaxIterationsExceededException, FunctionEvaluationException {
    067            return solve(f, min, max);
    068        }
    069
    070        /**
    071         * {@inheritDoc}
    072         * @deprecated in 2.2 (to be removed in 3.0).
    073         */
    074        @Deprecated
    075        public double solve(final UnivariateRealFunction f, double min, double max, double initial)
    076            throws MaxIterationsExceededException, FunctionEvaluationException {
    077            return solve(f, min, max);
    078        }
    079
    080        /** {@inheritDoc} */
    081        @Override
    082        public double solve(int maxEval, final UnivariateRealFunction f, double min, double max, double initial)
    083            throws MaxIterationsExceededException, FunctionEvaluationException {
    084            return solve(maxEval, f, min, max);
    085        }
    086
    087        /** {@inheritDoc} */
    088        @Override
    089        public double solve(int maxEval, final UnivariateRealFunction f, double min, double max)
    090            throws MaxIterationsExceededException, FunctionEvaluationException {
    091            setMaximalIterationCount(maxEval);
    092            return solve(f, min, max);
    093        }
    094
    095        /**
    096         * {@inheritDoc}
    097         * @deprecated in 2.2 (to be removed in 3.0).
    098         */
    099        @Deprecated
    100        public double solve(final UnivariateRealFunction f, double min, double max)
    101            throws MaxIterationsExceededException, FunctionEvaluationException {
    102
    103            clearResult();
    104            verifyInterval(min,max);
    105            double m;
    106            double fm;
    107            double fmin;
    108
    109            int i = 0;
    110            while (i < maximalIterationCount) {
    111                m = UnivariateRealSolverUtils.midpoint(min, max);
    112               fmin = f.value(min);
    113               fm = f.value(m);
    114
    115                if (fm * fmin > 0.0) {
    116                    // max and m bracket the root.
    117                    min = m;
    118                } else {
    119                    // min and m bracket the root.
    120                    max = m;
    121                }
    122
    123                if (FastMath.abs(max - min) <= absoluteAccuracy) {
    124                    m = UnivariateRealSolverUtils.midpoint(min, max);
    125                    setResult(m, i);
    126                    return m;
    127                }
    128                ++i;
    129            }
    130
    131            throw new MaxIterationsExceededException(maximalIterationCount);
    132        }
    133    }