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.math.analysis.solvers;
18  
19  import org.apache.commons.math.MathException;
20  import org.apache.commons.math.analysis.MonitoredFunction;
21  import org.apache.commons.math.analysis.QuinticFunction;
22  import org.apache.commons.math.analysis.SinFunction;
23  import org.apache.commons.math.analysis.UnivariateRealFunction;
24  
25  import junit.framework.Test;
26  import junit.framework.TestCase;
27  import junit.framework.TestSuite;
28  
29  /**
30   * Testcase for UnivariateRealSolver.
31   * Because Brent-Dekker is guaranteed to converge in less than the default
32   * maximum iteration count due to bisection fallback, it is quite hard to
33   * debug. I include measured iteration counts plus one in order to detect
34   * regressions. On average Brent-Dekker should use 4..5 iterations for the
35   * default absolute accuracy of 10E-8 for sinus and the quintic function around
36   * zero, and 5..10 iterations for the other zeros.
37   * 
38   * @version $Revision:670469 $ $Date:2008-06-23 10:01:38 +0200 (lun., 23 juin 2008) $ 
39   */
40  public final class BrentSolverTest extends TestCase {
41  
42      public BrentSolverTest(String name) {
43          super(name);
44      }
45  
46      public static Test suite() {
47          TestSuite suite = new TestSuite(BrentSolverTest.class);
48          suite.setName("UnivariateRealSolver Tests");
49          return suite;
50      }
51  
52      @Deprecated
53      public void testDeprecated() throws MathException {
54          // The sinus function is behaved well around the root at #pi. The second
55          // order derivative is zero, which means linar approximating methods will
56          // still converge quadratically. 
57          UnivariateRealFunction f = new SinFunction();
58          double result;
59          UnivariateRealSolver solver = new BrentSolver(f);
60          // Somewhat benign interval. The function is monotone.
61          result = solver.solve(3, 4);
62          //System.out.println(
63          //    "Root: " + result + " Iterations: " + solver.getIterationCount());
64          assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
65          // 4 iterations on i586 JDK 1.4.1.
66          assertTrue(solver.getIterationCount() <= 5);
67          // Larger and somewhat less benign interval. The function is grows first.
68          result = solver.solve(1, 4);
69          //System.out.println(
70          //    "Root: " + result + " Iterations: " + solver.getIterationCount());
71          assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
72          // 5 iterations on i586 JDK 1.4.1.
73          assertTrue(solver.getIterationCount() <= 6);
74          solver = new SecantSolver(f);
75          result = solver.solve(3, 4);
76          //System.out.println(
77          //    "Root: " + result + " Iterations: " + solver.getIterationCount());
78          assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
79          // 4 iterations on i586 JDK 1.4.1.
80          assertTrue(solver.getIterationCount() <= 5);
81          result = solver.solve(1, 4);
82          //System.out.println(
83          //    "Root: " + result + " Iterations: " + solver.getIterationCount());
84          assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
85          // 5 iterations on i586 JDK 1.4.1.
86          assertTrue(solver.getIterationCount() <= 6);
87          assertEquals(result, solver.getResult(), 0);
88      }
89  
90      public void testSinZero() throws MathException {
91          // The sinus function is behaved well around the root at #pi. The second
92          // order derivative is zero, which means linar approximating methods will
93          // still converge quadratically. 
94          UnivariateRealFunction f = new SinFunction();
95          double result;
96          UnivariateRealSolver solver = new BrentSolver();
97          // Somewhat benign interval. The function is monotone.
98          result = solver.solve(f, 3, 4);
99          //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 }