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    }