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: 811685 $ $Date: 2009-09-05 13:36:48 -0400 (Sat, 05 Sep 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 }