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    
023    /**
024     * Implements the <a href="http://mathworld.wolfram.com/Bisection.html">
025     * bisection algorithm</a> for finding zeros of univariate real functions. 
026     * <p>
027     * The function should be continuous but not necessarily smooth.</p>
028     * 
029     * @version $Revision: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $
030     */
031    public class BisectionSolver extends UnivariateRealSolverImpl {
032        
033        /**
034         * Construct a solver for the given function.
035         * 
036         * @param f function to solve.
037         * @deprecated as of 2.0 the function to solve is passed as an argument
038         * to the {@link #solve(UnivariateRealFunction, double, double)} or
039         * {@link UnivariateRealSolverImpl#solve(UnivariateRealFunction, double, double, double)}
040         * method.
041         */
042        @Deprecated
043        public BisectionSolver(UnivariateRealFunction f) {
044            super(f, 100, 1E-6);
045        }
046    
047        /**
048         * Construct a solver.
049         * 
050         */
051        public BisectionSolver() {
052            super(100, 1E-6);
053        }
054    
055        /** {@inheritDoc} */
056        @Deprecated
057        public double solve(double min, double max, double initial)
058            throws MaxIterationsExceededException, FunctionEvaluationException {
059            return solve(f, min, max);
060        }
061        
062        /** {@inheritDoc} */
063        @Deprecated
064        public double solve(double min, double max)
065            throws MaxIterationsExceededException, FunctionEvaluationException {
066            return solve(f, min, max);
067        }
068    
069        /** {@inheritDoc} */
070        public double solve(final UnivariateRealFunction f, double min, double max, double initial)
071            throws MaxIterationsExceededException, FunctionEvaluationException {
072            return solve(min, max);
073        }
074    
075        /** {@inheritDoc} */
076        public double solve(final UnivariateRealFunction f, double min, double max)
077            throws MaxIterationsExceededException, FunctionEvaluationException {
078                
079            clearResult();
080            verifyInterval(min,max);
081            double m;
082            double fm;
083            double fmin;
084            
085            int i = 0;
086            while (i < maximalIterationCount) {
087                m = UnivariateRealSolverUtils.midpoint(min, max);
088               fmin = f.value(min);
089               fm = f.value(m);
090    
091                if (fm * fmin > 0.0) {
092                    // max and m bracket the root.
093                    min = m;
094                } else {
095                    // min and m bracket the root.
096                    max = m;
097                }
098    
099                if (Math.abs(max - min) <= absoluteAccuracy) {
100                    m = UnivariateRealSolverUtils.midpoint(min, max);
101                    setResult(m, i);
102                    return m;
103                }
104                ++i;
105            }
106            
107            throw new MaxIterationsExceededException(maximalIterationCount);
108        }
109    }