001: /*
002: * Copyright 2003-2004 The Apache Software Foundation.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.commons.math.analysis;
017:
018: import org.apache.commons.math.FunctionEvaluationException;
019: import org.apache.commons.math.ConvergenceException;
020:
021: /**
022: * Implements the <a href="http://mathworld.wolfram.com/Bisection.html">
023: * bisection algorithm</a> for finding zeros of univariate real functions.
024: * <p>
025: * The function should be continuous but not necessarily smooth.
026: *
027: * @version $Revision: 348519 $ $Date: 2005-11-23 12:12:18 -0700 (Wed, 23 Nov 2005) $
028: */
029: public class BisectionSolver extends UnivariateRealSolverImpl {
030:
031: /** Serializable version identifier */
032: private static final long serialVersionUID = 7137520585963699578L;
033:
034: /**
035: * Construct a solver for the given function.
036: *
037: * @param f function to solve.
038: */
039: public BisectionSolver(UnivariateRealFunction f) {
040: super (f, 100, 1E-6);
041: }
042:
043: /**
044: * Find a zero in the given interval.
045: *
046: * @param min the lower bound for the interval.
047: * @param max the upper bound for the interval.
048: * @param initial the start value to use (ignored).
049: * @return the value where the function is zero
050: * @throws ConvergenceException the maximum iteration count is exceeded
051: * @throws FunctionEvaluationException if an error occurs evaluating
052: * the function
053: * @throws IllegalArgumentException if min is not less than max
054: */
055: public double solve(double min, double max, double initial)
056: throws ConvergenceException, FunctionEvaluationException {
057:
058: return solve(min, max);
059: }
060:
061: /**
062: * Find a zero root in the given interval.
063: *
064: * @param min the lower bound for the interval
065: * @param max the upper bound for the interval
066: * @return the value where the function is zero
067: * @throws ConvergenceException if the maximum iteration count is exceeded.
068: * @throws FunctionEvaluationException if an error occurs evaluating the
069: * function
070: * @throws IllegalArgumentException if min is not less than max
071: */
072: public double solve(double min, double max)
073: throws ConvergenceException, FunctionEvaluationException {
074:
075: clearResult();
076: verifyInterval(min, max);
077: double m;
078: double fm;
079: double fmin;
080:
081: int i = 0;
082: while (i < maximalIterationCount) {
083: m = UnivariateRealSolverUtils.midpoint(min, max);
084: fmin = f.value(min);
085: fm = f.value(m);
086:
087: if (fm * fmin > 0.0) {
088: // max and m bracket the root.
089: min = m;
090: } else {
091: // min and m bracket the root.
092: max = m;
093: }
094:
095: if (Math.abs(max - min) <= absoluteAccuracy) {
096: m = UnivariateRealSolverUtils.midpoint(min, max);
097: setResult(m, i);
098: return m;
099: }
100: ++i;
101: }
102:
103: throw new ConvergenceException(
104: "Maximum number of iterations exceeded: "
105: + maximalIterationCount);
106: }
107: }
|