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.MathException;
020 import org.apache.commons.math.analysis.MonitoredFunction;
021 import org.apache.commons.math.analysis.QuinticFunction;
022 import org.apache.commons.math.analysis.SinFunction;
023 import org.apache.commons.math.analysis.UnivariateRealFunction;
024
025 import junit.framework.Test;
026 import junit.framework.TestCase;
027 import junit.framework.TestSuite;
028
029 /**
030 * Testcase for UnivariateRealSolver.
031 * Because Brent-Dekker is guaranteed to converge in less than the default
032 * maximum iteration count due to bisection fallback, it is quite hard to
033 * debug. I include measured iteration counts plus one in order to detect
034 * regressions. On average Brent-Dekker should use 4..5 iterations for the
035 * default absolute accuracy of 10E-8 for sinus and the quintic function around
036 * zero, and 5..10 iterations for the other zeros.
037 *
038 * @version $Revision:670469 $ $Date:2008-06-23 10:01:38 +0200 (lun., 23 juin 2008) $
039 */
040 public final class BrentSolverTest extends TestCase {
041
042 public BrentSolverTest(String name) {
043 super(name);
044 }
045
046 public static Test suite() {
047 TestSuite suite = new TestSuite(BrentSolverTest.class);
048 suite.setName("UnivariateRealSolver Tests");
049 return suite;
050 }
051
052 @Deprecated
053 public void testDeprecated() throws MathException {
054 // The sinus function is behaved well around the root at #pi. The second
055 // order derivative is zero, which means linar approximating methods will
056 // still converge quadratically.
057 UnivariateRealFunction f = new SinFunction();
058 double result;
059 UnivariateRealSolver solver = new BrentSolver(f);
060 // Somewhat benign interval. The function is monotone.
061 result = solver.solve(3, 4);
062 //System.out.println(
063 // "Root: " + result + " Iterations: " + solver.getIterationCount());
064 assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
065 // 4 iterations on i586 JDK 1.4.1.
066 assertTrue(solver.getIterationCount() <= 5);
067 // Larger and somewhat less benign interval. The function is grows first.
068 result = solver.solve(1, 4);
069 //System.out.println(
070 // "Root: " + result + " Iterations: " + solver.getIterationCount());
071 assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
072 // 5 iterations on i586 JDK 1.4.1.
073 assertTrue(solver.getIterationCount() <= 6);
074 solver = new SecantSolver(f);
075 result = solver.solve(3, 4);
076 //System.out.println(
077 // "Root: " + result + " Iterations: " + solver.getIterationCount());
078 assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
079 // 4 iterations on i586 JDK 1.4.1.
080 assertTrue(solver.getIterationCount() <= 5);
081 result = solver.solve(1, 4);
082 //System.out.println(
083 // "Root: " + result + " Iterations: " + solver.getIterationCount());
084 assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
085 // 5 iterations on i586 JDK 1.4.1.
086 assertTrue(solver.getIterationCount() <= 6);
087 assertEquals(result, solver.getResult(), 0);
088 }
089
090 public void testSinZero() throws MathException {
091 // The sinus function is behaved well around the root at #pi. The second
092 // order derivative is zero, which means linar approximating methods will
093 // still converge quadratically.
094 UnivariateRealFunction f = new SinFunction();
095 double result;
096 UnivariateRealSolver solver = new BrentSolver();
097 // Somewhat benign interval. The function is monotone.
098 result = solver.solve(f, 3, 4);
099 //System.out.println(
100 // "Root: " + result + " Iterations: " + solver.getIterationCount());
101 assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
102 // 4 iterations on i586 JDK 1.4.1.
103 assertTrue(solver.getIterationCount() <= 5);
104 // Larger and somewhat less benign interval. The function is grows first.
105 result = solver.solve(f, 1, 4);
106 //System.out.println(
107 // "Root: " + result + " Iterations: " + solver.getIterationCount());
108 assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
109 // 5 iterations on i586 JDK 1.4.1.
110 assertTrue(solver.getIterationCount() <= 6);
111 solver = new SecantSolver();
112 result = solver.solve(f, 3, 4);
113 //System.out.println(
114 // "Root: " + result + " Iterations: " + solver.getIterationCount());
115 assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
116 // 4 iterations on i586 JDK 1.4.1.
117 assertTrue(solver.getIterationCount() <= 5);
118 result = solver.solve(f, 1, 4);
119 //System.out.println(
120 // "Root: " + result + " Iterations: " + solver.getIterationCount());
121 assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
122 // 5 iterations on i586 JDK 1.4.1.
123 assertTrue(solver.getIterationCount() <= 6);
124 assertEquals(result, solver.getResult(), 0);
125 }
126
127 public void testQuinticZero() throws MathException {
128 // The quintic function has zeros at 0, +-0.5 and +-1.
129 // Around the root of 0 the function is well behaved, with a second derivative
130 // of zero a 0.
131 // The other roots are less well to find, in particular the root at 1, because
132 // the function grows fast for x>1.
133 // The function has extrema (first derivative is zero) at 0.27195613 and 0.82221643,
134 // intervals containing these values are harder for the solvers.
135 UnivariateRealFunction f = new QuinticFunction();
136 double result;
137 // Brent-Dekker solver.
138 UnivariateRealSolver solver = new BrentSolver();
139 // Symmetric bracket around 0. Test whether solvers can handle hitting
140 // the root in the first iteration.
141 result = solver.solve(f, -0.2, 0.2);
142 //System.out.println(
143 // "Root: " + result + " Iterations: " + solver.getIterationCount());
144 assertEquals(result, 0, solver.getAbsoluteAccuracy());
145 assertTrue(solver.getIterationCount() <= 2);
146 // 1 iterations on i586 JDK 1.4.1.
147 // Asymmetric bracket around 0, just for fun. Contains extremum.
148 result = solver.solve(f, -0.1, 0.3);
149 //System.out.println(
150 // "Root: " + result + " Iterations: " + solver.getIterationCount());
151 assertEquals(result, 0, solver.getAbsoluteAccuracy());
152 // 5 iterations on i586 JDK 1.4.1.
153 assertTrue(solver.getIterationCount() <= 6);
154 // Large bracket around 0. Contains two extrema.
155 result = solver.solve(f, -0.3, 0.45);
156 //System.out.println(
157 // "Root: " + result + " Iterations: " + solver.getIterationCount());
158 assertEquals(result, 0, solver.getAbsoluteAccuracy());
159 // 6 iterations on i586 JDK 1.4.1.
160 assertTrue(solver.getIterationCount() <= 7);
161 // Benign bracket around 0.5, function is monotonous.
162 result = solver.solve(f, 0.3, 0.7);
163 //System.out.println(
164 // "Root: " + result + " Iterations: " + solver.getIterationCount());
165 assertEquals(result, 0.5, solver.getAbsoluteAccuracy());
166 // 6 iterations on i586 JDK 1.4.1.
167 assertTrue(solver.getIterationCount() <= 7);
168 // Less benign bracket around 0.5, contains one extremum.
169 result = solver.solve(f, 0.2, 0.6);
170 //System.out.println(
171 // "Root: " + result + " Iterations: " + solver.getIterationCount());
172 assertEquals(result, 0.5, solver.getAbsoluteAccuracy());
173 // 6 iterations on i586 JDK 1.4.1.
174 assertTrue(solver.getIterationCount() <= 7);
175 // Large, less benign bracket around 0.5, contains both extrema.
176 result = solver.solve(f, 0.05, 0.95);
177 //System.out.println(
178 // "Root: " + result + " Iterations: " + solver.getIterationCount());
179 assertEquals(result, 0.5, solver.getAbsoluteAccuracy());
180 // 8 iterations on i586 JDK 1.4.1.
181 assertTrue(solver.getIterationCount() <= 9);
182 // Relatively benign bracket around 1, function is monotonous. Fast growth for x>1
183 // is still a problem.
184 result = solver.solve(f, 0.85, 1.25);
185 //System.out.println(
186 // "Root: " + result + " Iterations: " + solver.getIterationCount());
187 assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
188 // 8 iterations on i586 JDK 1.4.1.
189 assertTrue(solver.getIterationCount() <= 9);
190 // Less benign bracket around 1 with extremum.
191 result = solver.solve(f, 0.8, 1.2);
192 //System.out.println(
193 // "Root: " + result + " Iterations: " + solver.getIterationCount());
194 assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
195 // 8 iterations on i586 JDK 1.4.1.
196 assertTrue(solver.getIterationCount() <= 9);
197 // Large bracket around 1. Monotonous.
198 result = solver.solve(f, 0.85, 1.75);
199 //System.out.println(
200 // "Root: " + result + " Iterations: " + solver.getIterationCount());
201 assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
202 // 10 iterations on i586 JDK 1.4.1.
203 assertTrue(solver.getIterationCount() <= 11);
204 // Large bracket around 1. Interval contains extremum.
205 result = solver.solve(f, 0.55, 1.45);
206 //System.out.println(
207 // "Root: " + result + " Iterations: " + solver.getIterationCount());
208 assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
209 // 7 iterations on i586 JDK 1.4.1.
210 assertTrue(solver.getIterationCount() <= 8);
211 // Very large bracket around 1 for testing fast growth behaviour.
212 result = solver.solve(f, 0.85, 5);
213 //System.out.println(
214 // "Root: " + result + " Iterations: " + solver.getIterationCount());
215 assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
216 // 12 iterations on i586 JDK 1.4.1.
217 assertTrue(solver.getIterationCount() <= 13);
218 // Secant solver.
219 solver = new SecantSolver();
220 result = solver.solve(f, -0.2, 0.2);
221 //System.out.println(
222 // "Root: " + result + " Iterations: " + solver.getIterationCount());
223 assertEquals(result, 0, solver.getAbsoluteAccuracy());
224 // 1 iterations on i586 JDK 1.4.1.
225 assertTrue(solver.getIterationCount() <= 2);
226 result = solver.solve(f, -0.1, 0.3);
227 //System.out.println(
228 // "Root: " + result + " Iterations: " + solver.getIterationCount());
229 assertEquals(result, 0, solver.getAbsoluteAccuracy());
230 // 5 iterations on i586 JDK 1.4.1.
231 assertTrue(solver.getIterationCount() <= 6);
232 result = solver.solve(f, -0.3, 0.45);
233 //System.out.println(
234 // "Root: " + result + " Iterations: " + solver.getIterationCount());
235 assertEquals(result, 0, solver.getAbsoluteAccuracy());
236 // 6 iterations on i586 JDK 1.4.1.
237 assertTrue(solver.getIterationCount() <= 7);
238 result = solver.solve(f, 0.3, 0.7);
239 //System.out.println(
240 // "Root: " + result + " Iterations: " + solver.getIterationCount());
241 assertEquals(result, 0.5, solver.getAbsoluteAccuracy());
242 // 7 iterations on i586 JDK 1.4.1.
243 assertTrue(solver.getIterationCount() <= 8);
244 result = solver.solve(f, 0.2, 0.6);
245 //System.out.println(
246 // "Root: " + result + " Iterations: " + solver.getIterationCount());
247 assertEquals(result, 0.5, solver.getAbsoluteAccuracy());
248 // 6 iterations on i586 JDK 1.4.1.
249 assertTrue(solver.getIterationCount() <= 7);
250 result = solver.solve(f, 0.05, 0.95);
251 //System.out.println(
252 // "Root: " + result + " Iterations: " + solver.getIterationCount());
253 assertEquals(result, 0.5, solver.getAbsoluteAccuracy());
254 // 8 iterations on i586 JDK 1.4.1.
255 assertTrue(solver.getIterationCount() <= 9);
256 result = solver.solve(f, 0.85, 1.25);
257 //System.out.println(
258 // "Root: " + result + " Iterations: " + solver.getIterationCount());
259 assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
260 // 10 iterations on i586 JDK 1.4.1.
261 assertTrue(solver.getIterationCount() <= 11);
262 result = solver.solve(f, 0.8, 1.2);
263 //System.out.println(
264 // "Root: " + result + " Iterations: " + solver.getIterationCount());
265 assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
266 // 8 iterations on i586 JDK 1.4.1.
267 assertTrue(solver.getIterationCount() <= 9);
268 result = solver.solve(f, 0.85, 1.75);
269 //System.out.println(
270 // "Root: " + result + " Iterations: " + solver.getIterationCount());
271 assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
272 // 14 iterations on i586 JDK 1.4.1.
273 assertTrue(solver.getIterationCount() <= 15);
274 // The followig is especially slow because the solver first has to reduce
275 // the bracket to exclude the extremum. After that, convergence is rapide.
276 result = solver.solve(f, 0.55, 1.45);
277 //System.out.println(
278 // "Root: " + result + " Iterations: " + solver.getIterationCount());
279 assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
280 // 7 iterations on i586 JDK 1.4.1.
281 assertTrue(solver.getIterationCount() <= 8);
282 result = solver.solve(f, 0.85, 5);
283 //System.out.println(
284 // "Root: " + result + " Iterations: " + solver.getIterationCount());
285 assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
286 // 14 iterations on i586 JDK 1.4.1.
287 assertTrue(solver.getIterationCount() <= 15);
288 // Static solve method
289 result = UnivariateRealSolverUtils.solve(f, -0.2, 0.2);
290 assertEquals(result, 0, solver.getAbsoluteAccuracy());
291 result = UnivariateRealSolverUtils.solve(f, -0.1, 0.3);
292 assertEquals(result, 0, 1E-8);
293 result = UnivariateRealSolverUtils.solve(f, -0.3, 0.45);
294 assertEquals(result, 0, 1E-6);
295 result = UnivariateRealSolverUtils.solve(f, 0.3, 0.7);
296 assertEquals(result, 0.5, 1E-6);
297 result = UnivariateRealSolverUtils.solve(f, 0.2, 0.6);
298 assertEquals(result, 0.5, 1E-6);
299 result = UnivariateRealSolverUtils.solve(f, 0.05, 0.95);
300 assertEquals(result, 0.5, 1E-6);
301 result = UnivariateRealSolverUtils.solve(f, 0.85, 1.25);
302 assertEquals(result, 1.0, 1E-6);
303 result = UnivariateRealSolverUtils.solve(f, 0.8, 1.2);
304 assertEquals(result, 1.0, 1E-6);
305 result = UnivariateRealSolverUtils.solve(f, 0.85, 1.75);
306 assertEquals(result, 1.0, 1E-6);
307 result = UnivariateRealSolverUtils.solve(f, 0.55, 1.45);
308 assertEquals(result, 1.0, 1E-6);
309 result = UnivariateRealSolverUtils.solve(f, 0.85, 5);
310 assertEquals(result, 1.0, 1E-6);
311 }
312
313 public void testRootEndpoints() throws Exception {
314 UnivariateRealFunction f = new SinFunction();
315 UnivariateRealSolver solver = new BrentSolver();
316
317 // endpoint is root
318 double result = solver.solve(f, Math.PI, 4);
319 assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
320
321 result = solver.solve(f, 3, Math.PI);
322 assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
323 }
324
325 public void testBadEndpoints() throws Exception {
326 UnivariateRealFunction f = new SinFunction();
327 UnivariateRealSolver solver = new BrentSolver();
328 try { // bad interval
329 solver.solve(f, 1, -1);
330 fail("Expecting IllegalArgumentException - bad interval");
331 } catch (IllegalArgumentException ex) {
332 // expected
333 }
334 try { // no bracket
335 solver.solve(f, 1, 1.5);
336 fail("Expecting IllegalArgumentException - non-bracketing");
337 } catch (IllegalArgumentException ex) {
338 // expected
339 }
340 }
341
342 public void testInitialGuess() throws MathException {
343
344 MonitoredFunction f = new MonitoredFunction(new QuinticFunction());
345 UnivariateRealSolver solver = new BrentSolver();
346 double result;
347
348 // no guess
349 result = solver.solve(f, 0.6, 7.0);
350 assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
351 int referenceCallsCount = f.getCallsCount();
352 assertTrue(referenceCallsCount >= 13);
353
354 // invalid guess (it *is* a root, but outside of the range)
355 try {
356 result = solver.solve(f, 0.6, 7.0, 0.0);
357 fail("an IllegalArgumentException was expected");
358 } catch (IllegalArgumentException iae) {
359 // expected behaviour
360 } catch (Exception e) {
361 fail("wrong exception caught: " + e.getMessage());
362 }
363
364 // bad guess
365 f.setCallsCount(0);
366 result = solver.solve(f, 0.6, 7.0, 0.61);
367 assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
368 assertTrue(f.getCallsCount() > referenceCallsCount);
369
370 // good guess
371 f.setCallsCount(0);
372 result = solver.solve(f, 0.6, 7.0, 0.999999);
373 assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
374 assertTrue(f.getCallsCount() < referenceCallsCount);
375
376 // perfect guess
377 f.setCallsCount(0);
378 result = solver.solve(f, 0.6, 7.0, 1.0);
379 assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
380 assertEquals(0, solver.getIterationCount());
381 assertEquals(1, f.getCallsCount());
382
383 }
384
385 }