001: /*
002: * Copyright 2003-2004 The Apache Software Foundation.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.commons.math.analysis;
017:
018: import org.apache.commons.math.MathException;
019:
020: import junit.framework.Test;
021: import junit.framework.TestCase;
022: import junit.framework.TestSuite;
023:
024: /**
025: * Testcase for UnivariateRealSolver.
026: * Because Brent-Dekker is guaranteed to converge in less than the default
027: * maximum iteration count due to bisection fallback, it is quite hard to
028: * debug. I include measured iteration counts plus one in order to detect
029: * regressions. On average Brent-Dekker should use 4..5 iterations for the
030: * default absolute accuracy of 10E-8 for sinus and the quintic function around
031: * zero, and 5..10 iterations for the other zeros.
032: *
033: * @version $Revision: 179958 $ $Date: 2005-06-03 22:36:42 -0700 (Fri, 03 Jun 2005) $
034: */
035: public final class BrentSolverTest extends TestCase {
036:
037: public BrentSolverTest(String name) {
038: super (name);
039: }
040:
041: public static Test suite() {
042: TestSuite suite = new TestSuite(BrentSolverTest.class);
043: suite.setName("UnivariateRealSolver Tests");
044: return suite;
045: }
046:
047: public void testSinZero() throws MathException {
048: // The sinus function is behaved well around the root at #pi. The second
049: // order derivative is zero, which means linar approximating methods will
050: // still converge quadratically.
051: UnivariateRealFunction f = new SinFunction();
052: double result;
053: UnivariateRealSolver solver = new BrentSolver(f);
054: // Somewhat benign interval. The function is monotone.
055: result = solver.solve(3, 4);
056: //System.out.println(
057: // "Root: " + result + " Iterations: " + solver.getIterationCount());
058: assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
059: // 4 iterations on i586 JDK 1.4.1.
060: assertTrue(solver.getIterationCount() <= 5);
061: // Larger and somewhat less benign interval. The function is grows first.
062: result = solver.solve(1, 4);
063: //System.out.println(
064: // "Root: " + result + " Iterations: " + solver.getIterationCount());
065: assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
066: // 5 iterations on i586 JDK 1.4.1.
067: assertTrue(solver.getIterationCount() <= 6);
068: solver = new SecantSolver(f);
069: result = solver.solve(3, 4);
070: //System.out.println(
071: // "Root: " + result + " Iterations: " + solver.getIterationCount());
072: assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
073: // 4 iterations on i586 JDK 1.4.1.
074: assertTrue(solver.getIterationCount() <= 5);
075: result = solver.solve(1, 4);
076: //System.out.println(
077: // "Root: " + result + " Iterations: " + solver.getIterationCount());
078: assertEquals(result, Math.PI, solver.getAbsoluteAccuracy());
079: // 5 iterations on i586 JDK 1.4.1.
080: assertTrue(solver.getIterationCount() <= 6);
081: assertEquals(result, solver.getResult(), 0);
082: }
083:
084: public void testQuinticZero() throws MathException {
085: // The quintic function has zeros at 0, +-0.5 and +-1.
086: // Around the root of 0 the function is well behaved, with a second derivative
087: // of zero a 0.
088: // The other roots are less well to find, in particular the root at 1, because
089: // the function grows fast for x>1.
090: // The function has extrema (first derivative is zero) at 0.27195613 and 0.82221643,
091: // intervals containing these values are harder for the solvers.
092: UnivariateRealFunction f = new QuinticFunction();
093: double result;
094: // Brent-Dekker solver.
095: UnivariateRealSolver solver = new BrentSolver(f);
096: // Symmetric bracket around 0. Test whether solvers can handle hitting
097: // the root in the first iteration.
098: result = solver.solve(-0.2, 0.2);
099: //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: }
|