    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 }