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 * https://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
18 /*
19 * This is not the original file distributed by the Apache Software Foundation
20 * It has been modified by the Hipparchus project
21 */
22 package org.hipparchus.analysis.solvers;
23
24 import org.hipparchus.exception.MathIllegalStateException;
25 import org.hipparchus.util.FastMath;
26
27 /**
28 * Implements the <a href="http://mathworld.wolfram.com/Bisection.html">
29 * bisection algorithm</a> for finding zeros of univariate real functions.
30 * <p>
31 * The function should be continuous but not necessarily smooth.</p>
32 *
33 */
34 public class BisectionSolver extends AbstractUnivariateSolver {
35 /** Default absolute accuracy. */
36 private static final double DEFAULT_ABSOLUTE_ACCURACY = 1e-6;
37
38 /**
39 * Construct a solver with default accuracy (1e-6).
40 */
41 public BisectionSolver() {
42 this(DEFAULT_ABSOLUTE_ACCURACY);
43 }
44 /**
45 * Construct a solver.
46 *
47 * @param absoluteAccuracy Absolute accuracy.
48 */
49 public BisectionSolver(double absoluteAccuracy) {
50 super(absoluteAccuracy);
51 }
52 /**
53 * Construct a solver.
54 *
55 * @param relativeAccuracy Relative accuracy.
56 * @param absoluteAccuracy Absolute accuracy.
57 */
58 public BisectionSolver(double relativeAccuracy,
59 double absoluteAccuracy) {
60 super(relativeAccuracy, absoluteAccuracy);
61 }
62
63 /**
64 * {@inheritDoc}
65 */
66 @Override
67 protected double doSolve()
68 throws MathIllegalStateException {
69 double min = getMin();
70 double max = getMax();
71 verifyInterval(min, max);
72 verifyBracketing(min, max);
73 final double absoluteAccuracy = getAbsoluteAccuracy();
74 double m;
75 double fm;
76 double fmin;
77
78 while (true) {
79 m = UnivariateSolverUtils.midpoint(min, max);
80 fmin = computeObjectiveValue(min);
81 fm = computeObjectiveValue(m);
82
83 if (fm * fmin > 0) {
84 // max and m bracket the root.
85 min = m;
86 } else {
87 // min and m bracket the root.
88 max = m;
89 }
90
91 if (FastMath.abs(max - min) <= absoluteAccuracy) {
92 m = UnivariateSolverUtils.midpoint(min, max);
93 return m;
94 }
95 }
96 }
97 }