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 }