1 /*
2 * Copyright (C) 2012 Alberto Irurueta Carro (alberto@irurueta.com)
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 package com.irurueta.numerical.roots;
17
18 import com.irurueta.numerical.EvaluationException;
19 import com.irurueta.numerical.InvalidBracketRangeException;
20 import com.irurueta.numerical.LockedException;
21 import com.irurueta.numerical.NotAvailableException;
22 import com.irurueta.numerical.NotReadyException;
23 import com.irurueta.numerical.SingleDimensionFunctionEvaluatorListener;
24
25 /**
26 * Computes a root for a single dimension function inside a given bracket of
27 * values, in other words, root will only be searched within provided minimum
28 * and maximum evaluation points.
29 */
30 public abstract class BracketedSingleRootEstimator extends SingleRootEstimator {
31
32 /**
33 * Number tries to automatically compute a bracket of values for a given
34 * function.
35 */
36 public static final int NTRY = 50;
37
38 /**
39 * Factor to use to modify initial values when searching for a bracket.
40 */
41 public static final double FACTOR = 1.6;
42
43 /**
44 * Default minimum evaluation point.
45 */
46 public static final double DEFAULT_MIN_EVAL_POINT = -Double.MAX_VALUE;
47
48 /**
49 * Default maximum evaluation point.
50 */
51 public static final double DEFAULT_MAX_EVAL_POINT = Double.MAX_VALUE;
52
53 /**
54 * Constant defining the value by which the largest bracket evaluation value
55 * is increased respect the minimum.
56 */
57 public static final double BRACKET_EPS = 1e-8;
58
59 /**
60 * Minimum evaluation point.
61 */
62 protected double minEvalPoint;
63
64 /**
65 * Maximum evaluation point.
66 */
67 protected double maxEvalPoint;
68
69 /**
70 * Boolean indicating whether a bracket has been computed and is available.
71 */
72 protected boolean bracketAvailable;
73
74 /**
75 * Empty constructor.
76 */
77 protected BracketedSingleRootEstimator() {
78 super();
79 minEvalPoint = DEFAULT_MIN_EVAL_POINT;
80 maxEvalPoint = DEFAULT_MAX_EVAL_POINT;
81 bracketAvailable = true;
82 }
83
84 /**
85 * Constructor.
86 *
87 * @param listener Listener to evaluate a single dimension function f(x)
88 * to find its roots.
89 * @param minEvalPoint Smallest value inside the bracket of values where the
90 * root will be searched.
91 * @param maxEvalPoint Largest value inside the bracket of values where the
92 * root will be searched.
93 * @throws InvalidBracketRangeException Raised if minEvalPoint <
94 * maxEvalPoint.
95 */
96 protected BracketedSingleRootEstimator(
97 final SingleDimensionFunctionEvaluatorListener listener, final double minEvalPoint,
98 final double maxEvalPoint) throws InvalidBracketRangeException {
99 super(listener);
100 internalSetBracket(minEvalPoint, maxEvalPoint);
101 }
102
103 /**
104 * Sets the bracket of values (i.e. range of values) where the root will be
105 * searched.
106 *
107 * @param minEvalPoint Smallest value inside the bracket of values where the
108 * root will be searched.
109 * @param maxEvalPoint Largest value inside the bracket of values where the
110 * root will be searched.
111 * @throws LockedException Raised if this instance is locked while doing
112 * some computations.
113 * @throws InvalidBracketRangeException Raised if minEvalPoint <
114 * maxEvalPoint.
115 */
116 public void setBracket(final double minEvalPoint, final double maxEvalPoint) throws LockedException,
117 InvalidBracketRangeException {
118 if (isLocked()) {
119 throw new LockedException();
120 }
121 internalSetBracket(minEvalPoint, maxEvalPoint);
122 }
123
124 /**
125 * Internal method to set the bracket of values (i.e. range of values) where
126 * the root will be searched.
127 *
128 * @param minEvalPoint Smallest value inside the bracket of values where the
129 * root will be searched.
130 * @param maxEvalPoint Largest value inside the bracket of values where the
131 * root will be searched.
132 * @throws InvalidBracketRangeException Raised if minEvalPoint <
133 * maxEvalPoint.
134 */
135 private void internalSetBracket(final double minEvalPoint, final double maxEvalPoint)
136 throws InvalidBracketRangeException {
137 if (minEvalPoint >= maxEvalPoint) {
138 throw new InvalidBracketRangeException();
139 }
140
141 this.minEvalPoint = minEvalPoint;
142 this.maxEvalPoint = maxEvalPoint;
143 bracketAvailable = true;
144 }
145
146 /**
147 * Returns boolean indicating whether bracket has been set or not.
148 *
149 * @return True if bracket has been set, false otherwise.
150 */
151 public boolean isBracketAvailable() {
152 return bracketAvailable;
153 }
154
155 /**
156 * Returns smallest value inside the bracket of values where the root will
157 * be searched.
158 *
159 * @return Smallest value inside the bracket.
160 * @throws NotAvailableException Raised if bracket has not been set.
161 */
162 public double getMinEvaluationPoint() throws NotAvailableException {
163 if (!isBracketAvailable()) {
164 throw new NotAvailableException();
165 }
166 return minEvalPoint;
167 }
168
169 /**
170 * Returns largest value inside the bracket of values where the root will
171 * be searched.
172 *
173 * @return Largest values inside the bracket.
174 * @throws NotAvailableException Raised if bracket has not been set.
175 */
176 public double getMaxEvaluationPoint() throws NotAvailableException {
177 if (!isBracketAvailable()) {
178 throw new NotAvailableException();
179 }
180 return maxEvalPoint;
181 }
182
183 /**
184 * Starting from provided minimum and maximum values, this method expands
185 * the range (i.e. bracket of values) until a zero crossing is found where
186 * a root is present or until the bracket becomes unacceptably large, where
187 * an exception will be raised.
188 * Notice that this method searches for zero crossings, hence, functions
189 * such as Math.pow(x - root, 2.0), will raise a RootEstimationException
190 * because the only root present in them does not produce a zero crossing.
191 *
192 * @param minEvalPoint Smallest initial value to estimate a new larger
193 * bracket.
194 * @param maxEvalPoint Largest initial value to estimate a new larger
195 * bracket.
196 * @throws LockedException Raised if this instance is locked while doing
197 * some computations.
198 * @throws NotReadyException Raised if this instance is not ready (e.g. a
199 * listener has not yet been provided, etc.)
200 * @throws InvalidBracketRangeException Raised if minEvalPoint <
201 * maxEvalPoint
202 * @throws RootEstimationException Raised if a bracket couldn't be found
203 * inside the provided limits because no zero crossing was present or
204 * convergence was not achieved.
205 */
206 public void computeBracket(final double minEvalPoint, final double maxEvalPoint)
207 throws LockedException, NotReadyException, InvalidBracketRangeException, RootEstimationException {
208
209 if (isLocked()) {
210 throw new LockedException();
211 }
212 if (!isReady()) {
213 throw new NotReadyException();
214 }
215 if (minEvalPoint >= maxEvalPoint) {
216 throw new InvalidBracketRangeException();
217 }
218
219 locked = true;
220
221 // expand initial bracket until function contains a sign change
222 var x1 = minEvalPoint;
223 var x2 = maxEvalPoint;
224 double f1;
225 double f2;
226 try {
227 f1 = listener.evaluate(x1);
228 f2 = listener.evaluate(x2);
229
230 var found = false;
231 for (var j = 0; j < NTRY; j++) {
232 if (f1 * f2 < 0.0) {
233 found = true;
234 break;
235 }
236 if (Math.abs(f1) < Math.abs(f2)) {
237 x1 += FACTOR * (x1 - x2);
238 f1 = listener.evaluate(x1);
239 } else {
240 x2 += FACTOR * (x2 - x1);
241 f2 = listener.evaluate(x2);
242 }
243 }
244
245 if (!found) {
246 throw new RootEstimationException();
247 }
248
249 this.minEvalPoint = x1;
250 this.maxEvalPoint = x2;
251 bracketAvailable = true;
252
253 } catch (final EvaluationException e) {
254 throw new RootEstimationException(e);
255 } finally {
256 locked = false;
257 }
258 }
259
260 /**
261 * Starting from provided point, this method expands the range (i.e.
262 * bracket of values) until a zero crossing is found where a root is present
263 * or until the bracket becomes unacceptably large, where an exception will
264 * be raised.
265 * Notice that this method searches for zero crossings, hence, functions
266 * such as Math.pow(x - root, 2.0), will raise a RootEstimationException
267 * because the only root present in them does not produce a zero crossing.
268 *
269 * @param point Initial value to start the bracket computation. Bracket
270 * range is expanded starting at the point that was provided.
271 * @throws LockedException Raised if this instance is locked while doing
272 * some computations.
273 * @throws NotReadyException Raised if this instance is not ready (e.g. a
274 * listener has not yet been provided, etc.).
275 * @throws InvalidBracketRangeException Raised if point is close to
276 * Double.MAX_VALUE.
277 * @throws RootEstimationException Raised if a bracket couldn't be found
278 * inside the provided limits because no zero crossing was present or
279 * convergence was not achieved.
280 */
281 public void computeBracket(final double point) throws LockedException, NotReadyException,
282 InvalidBracketRangeException, RootEstimationException {
283 computeBracket(point, FACTOR * point + BRACKET_EPS);
284 }
285
286 /**
287 * Starting at zero, this method expands the range (i.e. bracket of values)
288 * until a zero crossing is found where a root is present or until the
289 * bracket becomes unacceptably large, where an exception will be raised.
290 * Notice that this method searches for zero crossings, hence, functions
291 * such as Math.pow(x - root, 2.0), will raise a RootEstimationException
292 * because the only root present in them does not produce a zero crossing.
293 *
294 * @throws LockedException Raised if this instance is locked while doing
295 * some computations.
296 * @throws NotReadyException Raised if this instance is not ready (e.g. a
297 * listener has not yet been provided, etc.).
298 * @throws RootEstimationException Raised if a bracket couldn't be found
299 * inside the provided limits because no zero crossing was present or
300 * convergence was not achieved.
301 */
302 public void computeBracket() throws LockedException, NotReadyException, RootEstimationException {
303 try {
304 computeBracket(0.0, BRACKET_EPS);
305 } catch (final InvalidBracketRangeException ignore) {
306 // never happens
307 }
308 }
309
310 /**
311 * Internal method to swap two values. Value inside a[0] will be swapped
312 * with value provided in b[0].
313 *
314 * @param a Value to be swapped.
315 * @param b Value to be swapped.
316 */
317 protected void swap(final double[] a, final double[] b) {
318 final var tmp = a[0];
319 a[0] = b[0];
320 b[0] = tmp;
321 }
322
323 /**
324 * Internal method to determine whether a and b have the same sign.
325 *
326 * @param a Value to be compared.
327 * @param b Value to be compared.
328 * @return Returns "a" if "a" and "b" have the same sign or "-a" otherwise.
329 */
330 protected double sign(final double a, final double b) {
331 if (b >= 0.0) {
332 return a >= 0.0 ? a : -a;
333 } else {
334 return a >= 0.0 ? -a : a;
335 }
336 }
337 }