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    }