1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.math4.legacy.analysis.solvers;
18
19 import org.apache.commons.math4.legacy.exception.TooManyEvaluationsException;
20 import org.apache.commons.math4.core.jdkmath.JdkMath;
21
22 /**
23 * Implements the <a href="http://mathworld.wolfram.com/Bisection.html">
24 * bisection algorithm</a> for finding zeros of univariate real functions.
25 * <p>
26 * The function should be continuous but not necessarily smooth.</p>
27 *
28 */
29 public class BisectionSolver extends AbstractUnivariateSolver {
30 /** Default absolute accuracy. */
31 private static final double DEFAULT_ABSOLUTE_ACCURACY = 1e-6;
32
33 /**
34 * Construct a solver with default accuracy (1e-6).
35 */
36 public BisectionSolver() {
37 this(DEFAULT_ABSOLUTE_ACCURACY);
38 }
39 /**
40 * Construct a solver.
41 *
42 * @param absoluteAccuracy Absolute accuracy.
43 */
44 public BisectionSolver(double absoluteAccuracy) {
45 super(absoluteAccuracy);
46 }
47 /**
48 * Construct a solver.
49 *
50 * @param relativeAccuracy Relative accuracy.
51 * @param absoluteAccuracy Absolute accuracy.
52 */
53 public BisectionSolver(double relativeAccuracy,
54 double absoluteAccuracy) {
55 super(relativeAccuracy, absoluteAccuracy);
56 }
57
58 /**
59 * {@inheritDoc}
60 */
61 @Override
62 protected double doSolve()
63 throws TooManyEvaluationsException {
64 double min = getMin();
65 double max = getMax();
66 verifyInterval(min, max);
67 final double absoluteAccuracy = getAbsoluteAccuracy();
68 double m;
69 double fm;
70 double fmin;
71
72 while (true) {
73 m = UnivariateSolverUtils.midpoint(min, max);
74 fmin = computeObjectiveValue(min);
75 fm = computeObjectiveValue(m);
76
77 if (fm * fmin > 0) {
78 // max and m bracket the root.
79 min = m;
80 } else {
81 // min and m bracket the root.
82 max = m;
83 }
84
85 if (JdkMath.abs(max - min) <= absoluteAccuracy) {
86 m = UnivariateSolverUtils.midpoint(min, max);
87 return m;
88 }
89 }
90 }
91 }