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 */
017package org.apache.commons.math3.analysis.solvers;
018
019import org.apache.commons.math3.util.FastMath;
020import 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 */
029public class BisectionSolver extends AbstractUnivariateSolver {
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        throws TooManyEvaluationsException {
064        double min = getMin();
065        double max = getMax();
066        verifyInterval(min, max);
067        final double absoluteAccuracy = getAbsoluteAccuracy();
068        double m;
069        double fm;
070        double fmin;
071
072        while (true) {
073            m = UnivariateSolverUtils.midpoint(min, max);
074            fmin = computeObjectiveValue(min);
075            fm = computeObjectiveValue(m);
076
077            if (fm * fmin > 0) {
078                // max and m bracket the root.
079                min = m;
080            } else {
081                // min and m bracket the root.
082                max = m;
083            }
084
085            if (FastMath.abs(max - min) <= absoluteAccuracy) {
086                m = UnivariateSolverUtils.midpoint(min, max);
087                return m;
088            }
089        }
090    }
091}