1   /*
2    * Copyright 2003-2004 The Apache Software Foundation.
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 org.apache.commons.math.analysis;
17  
18  import org.apache.commons.math.MathException;
19  
20  import junit.framework.Test;
21  import junit.framework.TestCase;
22  import junit.framework.TestSuite;
23  
24  /**
25   * Testcase for UnivariateRealSolver.
26   * Because Brent-Dekker is guaranteed to converge in less than the default
27   * maximum iteration count due to bisection fallback, it is quite hard to
28   * debug. I include measured iteration counts plus one in order to detect
29   * regressions. On average Brent-Dekker should use 4..5 iterations for the
30   * default absolute accuracy of 10E-8 for sinus and the quintic function around
31   * zero, and 5..10 iterations for the other zeros.
32   * 
33   * @version $Revision: 179958 $ $Date: 2005-06-03 22:36:42 -0700 (Fri, 03 Jun 2005) $ 
34   */
35  public final class BrentSolverTest extends TestCase {
36  
37      public BrentSolverTest(String name) {
38          super(name);
39      }
40  
41      public static Test suite() {
42          TestSuite suite = new TestSuite(BrentSolverTest.class);
43          suite.setName("UnivariateRealSolver Tests");
44          return suite;
45      }
46  
47      public void testSinZero() throws MathException {
48          // The sinus function is behaved well around the root at #pi. The second
49          // order derivative is zero, which means linar approximating methods will
50          // still converge quadratically. 
51          UnivariateRealFunction f = new SinFunction();
52          double result;
53          UnivariateRealSolver solver = new BrentSolver(f);
54          // Somewhat benign interval. The function is monotone.
55          result = solver.solve(3, 4);
56          //System.out.println(
57          //    "Root: " + result + " Iterations: " + solver.getIterationCount());
58          assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
59          // 4 iterations on i586 JDK 1.4.1.
60          assertTrue(solver.getIterationCount() <= 5);
61          // Larger and somewhat less benign interval. The function is grows first.
62          result = solver.solve(1, 4);
63          //System.out.println(
64          //    "Root: " + result + " Iterations: " + solver.getIterationCount());
65          assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
66          // 5 iterations on i586 JDK 1.4.1.
67          assertTrue(solver.getIterationCount() <= 6);
68          solver = new SecantSolver(f);
69          result = solver.solve(3, 4);
70          //System.out.println(
71          //    "Root: " + result + " Iterations: " + solver.getIterationCount());
72          assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
73          // 4 iterations on i586 JDK 1.4.1.
74          assertTrue(solver.getIterationCount() <= 5);
75          result = solver.solve(1, 4);
76          //System.out.println(
77          //    "Root: " + result + " Iterations: " + solver.getIterationCount());
78          assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
79          // 5 iterations on i586 JDK 1.4.1.
80          assertTrue(solver.getIterationCount() <= 6);
81          assertEquals(result, solver.getResult(), 0);
82      }
83  
84      public void testQuinticZero() throws MathException {
85          // The quintic function has zeros at 0, +-0.5 and +-1.
86          // Around the root of 0 the function is well behaved, with a second derivative
87          // of zero a 0.
88          // The other roots are less well to find, in particular the root at 1, because
89          // the function grows fast for x>1.
90          // The function has extrema (first derivative is zero) at 0.27195613 and 0.82221643,
91          // intervals containing these values are harder for the solvers.
92          UnivariateRealFunction f = new QuinticFunction();
93          double result;
94          // Brent-Dekker solver.
95          UnivariateRealSolver solver = new BrentSolver(f);
96          // Symmetric bracket around 0. Test whether solvers can handle hitting
97          // the root in the first iteration.
98          result = solver.solve(-0.2, 0.2);
99          //System.out.println(
100         //    "Root: " + result + " Iterations: " + solver.getIterationCount());
101         assertEquals(result, 0, solver.getAbsoluteAccuracy());
102         assertTrue(solver.getIterationCount() <= 2);
103         // 1 iterations on i586 JDK 1.4.1.
104         // Asymmetric bracket around 0, just for fun. Contains extremum.
105         result = solver.solve(-0.1, 0.3);
106         //System.out.println(
107         //    "Root: " + result + " Iterations: " + solver.getIterationCount());
108         assertEquals(result, 0, solver.getAbsoluteAccuracy());
109         // 5 iterations on i586 JDK 1.4.1.
110         assertTrue(solver.getIterationCount() <= 6);
111         // Large bracket around 0. Contains two extrema.
112         result = solver.solve(-0.3, 0.45);
113         //System.out.println(
114         //    "Root: " + result + " Iterations: " + solver.getIterationCount());
115         assertEquals(result, 0, solver.getAbsoluteAccuracy());
116         // 6 iterations on i586 JDK 1.4.1.
117         assertTrue(solver.getIterationCount() <= 7);
118         // Benign bracket around 0.5, function is monotonous.
119         result = solver.solve(0.3, 0.7);
120         //System.out.println(
121         //    "Root: " + result + " Iterations: " + solver.getIterationCount());
122         assertEquals(result, 0.5, solver.getAbsoluteAccuracy());
123         // 6 iterations on i586 JDK 1.4.1.
124         assertTrue(solver.getIterationCount() <= 7);
125         // Less benign bracket around 0.5, contains one extremum.
126         result = solver.solve(0.2, 0.6);
127         //System.out.println(
128         //    "Root: " + result + " Iterations: " + solver.getIterationCount());
129         assertEquals(result, 0.5, solver.getAbsoluteAccuracy());
130         // 6 iterations on i586 JDK 1.4.1.
131         assertTrue(solver.getIterationCount() <= 7);
132         // Large, less benign bracket around 0.5, contains both extrema.
133         result = solver.solve(0.05, 0.95);
134         //System.out.println(
135         //    "Root: " + result + " Iterations: " + solver.getIterationCount());
136         assertEquals(result, 0.5, solver.getAbsoluteAccuracy());
137         // 8 iterations on i586 JDK 1.4.1.
138         assertTrue(solver.getIterationCount() <= 9);
139         // Relatively benign bracket around 1, function is monotonous. Fast growth for x>1
140         // is still a problem.
141         result = solver.solve(0.85, 1.25);
142         //System.out.println(
143         //    "Root: " + result + " Iterations: " + solver.getIterationCount());
144         assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
145         // 8 iterations on i586 JDK 1.4.1.
146         assertTrue(solver.getIterationCount() <= 9);
147         // Less benign bracket around 1 with extremum.
148         result = solver.solve(0.8, 1.2);
149         //System.out.println(
150         //    "Root: " + result + " Iterations: " + solver.getIterationCount());
151         assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
152         // 8 iterations on i586 JDK 1.4.1.
153         assertTrue(solver.getIterationCount() <= 9);
154         // Large bracket around 1. Monotonous.
155         result = solver.solve(0.85, 1.75);
156         //System.out.println(
157         //    "Root: " + result + " Iterations: " + solver.getIterationCount());
158         assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
159         // 10 iterations on i586 JDK 1.4.1.
160         assertTrue(solver.getIterationCount() <= 11);
161         // Large bracket around 1. Interval contains extremum.
162         result = solver.solve(0.55, 1.45);
163         //System.out.println(
164         //    "Root: " + result + " Iterations: " + solver.getIterationCount());
165         assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
166         // 7 iterations on i586 JDK 1.4.1.
167         assertTrue(solver.getIterationCount() <= 8);
168         // Very large bracket around 1 for testing fast growth behaviour.
169         result = solver.solve(0.85, 5);
170         //System.out.println(
171        //     "Root: " + result + " Iterations: " + solver.getIterationCount());
172         assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
173         // 12 iterations on i586 JDK 1.4.1.
174         assertTrue(solver.getIterationCount() <= 13);
175         // Secant solver.
176         solver = new SecantSolver(f);
177         result = solver.solve(-0.2, 0.2);
178         //System.out.println(
179         //    "Root: " + result + " Iterations: " + solver.getIterationCount());
180         assertEquals(result, 0, solver.getAbsoluteAccuracy());
181         // 1 iterations on i586 JDK 1.4.1.
182         assertTrue(solver.getIterationCount() <= 2);
183         result = solver.solve(-0.1, 0.3);
184         //System.out.println(
185         //    "Root: " + result + " Iterations: " + solver.getIterationCount());
186         assertEquals(result, 0, solver.getAbsoluteAccuracy());
187         // 5 iterations on i586 JDK 1.4.1.
188         assertTrue(solver.getIterationCount() <= 6);
189         result = solver.solve(-0.3, 0.45);
190         //System.out.println(
191         //    "Root: " + result + " Iterations: " + solver.getIterationCount());
192         assertEquals(result, 0, solver.getAbsoluteAccuracy());
193         // 6 iterations on i586 JDK 1.4.1.
194         assertTrue(solver.getIterationCount() <= 7);
195         result = solver.solve(0.3, 0.7);
196         //System.out.println(
197         //    "Root: " + result + " Iterations: " + solver.getIterationCount());
198         assertEquals(result, 0.5, solver.getAbsoluteAccuracy());
199         // 7 iterations on i586 JDK 1.4.1.
200         assertTrue(solver.getIterationCount() <= 8);
201         result = solver.solve(0.2, 0.6);
202         //System.out.println(
203         //    "Root: " + result + " Iterations: " + solver.getIterationCount());
204         assertEquals(result, 0.5, solver.getAbsoluteAccuracy());
205         // 6 iterations on i586 JDK 1.4.1.
206         assertTrue(solver.getIterationCount() <= 7);
207         result = solver.solve(0.05, 0.95);
208         //System.out.println(
209         //    "Root: " + result + " Iterations: " + solver.getIterationCount());
210         assertEquals(result, 0.5, solver.getAbsoluteAccuracy());
211         // 8 iterations on i586 JDK 1.4.1.
212         assertTrue(solver.getIterationCount() <= 9);
213         result = solver.solve(0.85, 1.25);
214         //System.out.println(
215         //    "Root: " + result + " Iterations: " + solver.getIterationCount());
216         assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
217         // 10 iterations on i586 JDK 1.4.1.
218         assertTrue(solver.getIterationCount() <= 11);
219         result = solver.solve(0.8, 1.2);
220         //System.out.println(
221         //    "Root: " + result + " Iterations: " + solver.getIterationCount());
222         assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
223         // 8 iterations on i586 JDK 1.4.1.
224         assertTrue(solver.getIterationCount() <= 9);
225         result = solver.solve(0.85, 1.75);
226         //System.out.println(
227         //    "Root: " + result + " Iterations: " + solver.getIterationCount());
228         assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
229         // 14 iterations on i586 JDK 1.4.1.
230         assertTrue(solver.getIterationCount() <= 15);
231         // The followig is especially slow because the solver first has to reduce
232         // the bracket to exclude the extremum. After that, convergence is rapide.
233         result = solver.solve(0.55, 1.45);
234         //System.out.println(
235         //    "Root: " + result + " Iterations: " + solver.getIterationCount());
236         assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
237         // 7 iterations on i586 JDK 1.4.1.
238         assertTrue(solver.getIterationCount() <= 8);
239         result = solver.solve(0.85, 5);
240         //System.out.println(
241         //    "Root: " + result + " Iterations: " + solver.getIterationCount());
242         assertEquals(result, 1.0, solver.getAbsoluteAccuracy());
243         // 14 iterations on i586 JDK 1.4.1.
244         assertTrue(solver.getIterationCount() <= 15);
245         // Static solve method
246         result = UnivariateRealSolverUtils.solve(f, -0.2, 0.2);
247         assertEquals(result, 0, solver.getAbsoluteAccuracy());
248         result = UnivariateRealSolverUtils.solve(f, -0.1, 0.3);
249         assertEquals(result, 0, 1E-8);
250         result = UnivariateRealSolverUtils.solve(f, -0.3, 0.45);
251         assertEquals(result, 0, 1E-6);
252         result = UnivariateRealSolverUtils.solve(f, 0.3, 0.7);
253         assertEquals(result, 0.5, 1E-6);
254         result = UnivariateRealSolverUtils.solve(f, 0.2, 0.6);
255         assertEquals(result, 0.5, 1E-6);
256         result = UnivariateRealSolverUtils.solve(f, 0.05, 0.95);
257         assertEquals(result, 0.5, 1E-6);
258         result = UnivariateRealSolverUtils.solve(f, 0.85, 1.25);
259         assertEquals(result, 1.0, 1E-6);
260         result = UnivariateRealSolverUtils.solve(f, 0.8, 1.2);
261         assertEquals(result, 1.0, 1E-6);
262         result = UnivariateRealSolverUtils.solve(f, 0.85, 1.75);
263         assertEquals(result, 1.0, 1E-6);
264         result = UnivariateRealSolverUtils.solve(f, 0.55, 1.45);
265         assertEquals(result, 1.0, 1E-6);
266         result = UnivariateRealSolverUtils.solve(f, 0.85, 5);
267         assertEquals(result, 1.0, 1E-6);
268     }
269     
270     public void testBadEndpoints() throws Exception {
271         UnivariateRealFunction f = new SinFunction();
272         UnivariateRealSolver solver = new BrentSolver(f);
273         try {  // bad interval
274             solver.solve(1, -1);
275             fail("Expecting IllegalArgumentException - bad interval");
276         } catch (IllegalArgumentException ex) {
277             // expected
278         }
279         try {  // no bracket
280             solver.solve(1, 1.5);
281             fail("Expecting IllegalArgumentException - non-bracketing");
282         } catch (IllegalArgumentException ex) {
283             // expected
284         }
285     }
286 }