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: 1.1 $ $Date: 2004/07/17 19:49:02 $
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 }