1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 package org.apache.commons.math4.legacy.analysis.solvers;
19
20 import org.apache.commons.math4.legacy.analysis.QuinticFunction;
21 import org.apache.commons.math4.legacy.analysis.UnivariateFunction;
22 import org.apache.commons.math4.legacy.analysis.differentiation.DerivativeStructure;
23 import org.apache.commons.math4.legacy.analysis.differentiation.UnivariateDifferentiableFunction;
24 import org.apache.commons.math4.legacy.exception.NumberIsTooSmallException;
25 import org.apache.commons.math4.legacy.exception.TooManyEvaluationsException;
26 import org.junit.Assert;
27 import org.junit.Test;
28
29
30
31
32
33 public final class BracketingNthOrderBrentSolverTest extends BaseSecantSolverAbstractTest {
34
35 @Override
36 protected UnivariateSolver getSolver() {
37 return new BracketingNthOrderBrentSolver();
38 }
39
40
41 @Override
42 protected int[] getQuinticEvalCounts() {
43 return new int[] {1, 3, 8, 1, 9, 4, 8, 1, 12, 1, 16};
44 }
45
46 @Test(expected=NumberIsTooSmallException.class)
47 public void testInsufficientOrder1() {
48 new BracketingNthOrderBrentSolver(1.0e-10, 1);
49 }
50
51 @Test(expected=NumberIsTooSmallException.class)
52 public void testInsufficientOrder2() {
53 new BracketingNthOrderBrentSolver(1.0e-10, 1.0e-10, 1);
54 }
55
56 @Test(expected=NumberIsTooSmallException.class)
57 public void testInsufficientOrder3() {
58 new BracketingNthOrderBrentSolver(1.0e-10, 1.0e-10, 1.0e-10, 1);
59 }
60
61 @Test
62 public void testConstructorsOK() {
63 Assert.assertEquals(2, new BracketingNthOrderBrentSolver(1.0e-10, 2).getMaximalOrder());
64 Assert.assertEquals(2, new BracketingNthOrderBrentSolver(1.0e-10, 1.0e-10, 2).getMaximalOrder());
65 Assert.assertEquals(2, new BracketingNthOrderBrentSolver(1.0e-10, 1.0e-10, 1.0e-10, 2).getMaximalOrder());
66 }
67
68 @Test
69 public void testConvergenceOnFunctionAccuracy() {
70 BracketingNthOrderBrentSolver solver =
71 new BracketingNthOrderBrentSolver(1.0e-12, 1.0e-10, 0.001, 3);
72 QuinticFunction f = new QuinticFunction();
73 double result = solver.solve(20, f, 0.2, 0.9, 0.4, AllowedSolution.BELOW_SIDE);
74 Assert.assertEquals(0, f.value(result), solver.getFunctionValueAccuracy());
75 Assert.assertTrue(f.value(result) <= 0);
76 Assert.assertTrue(result - 0.5 > solver.getAbsoluteAccuracy());
77 result = solver.solve(20, f, -0.9, -0.2, -0.4, AllowedSolution.ABOVE_SIDE);
78 Assert.assertEquals(0, f.value(result), solver.getFunctionValueAccuracy());
79 Assert.assertTrue(f.value(result) >= 0);
80 Assert.assertTrue(result + 0.5 < -solver.getAbsoluteAccuracy());
81 }
82
83 @Test
84 public void testIssue716() {
85 BracketingNthOrderBrentSolver solver =
86 new BracketingNthOrderBrentSolver(1.0e-12, 1.0e-10, 1.0e-22, 5);
87 UnivariateFunction sharpTurn = new UnivariateFunction() {
88 @Override
89 public double value(double x) {
90 return (2 * x + 1) / (1.0e9 * (x + 1));
91 }
92 };
93 double result = solver.solve(100, sharpTurn, -0.9999999, 30, 15, AllowedSolution.RIGHT_SIDE);
94 Assert.assertEquals(0, sharpTurn.value(result), solver.getFunctionValueAccuracy());
95 Assert.assertTrue(sharpTurn.value(result) >= 0);
96 Assert.assertEquals(-0.5, result, 1.0e-10);
97 }
98
99 @Test
100 public void testFasterThanNewton() {
101
102
103
104
105
106
107 compare(new TestFunction(0.0, -2, 2) {
108 @Override
109 public DerivativeStructure value(DerivativeStructure x) {
110 return x.sin().subtract(x.multiply(0.5));
111 }
112 });
113 compare(new TestFunction(6.3087771299726890947, -5, 10) {
114 @Override
115 public DerivativeStructure value(DerivativeStructure x) {
116 return x.pow(5).add(x).subtract(10000);
117 }
118 });
119 compare(new TestFunction(9.6335955628326951924, 0.001, 10) {
120 @Override
121 public DerivativeStructure value(DerivativeStructure x) {
122 return x.sqrt().subtract(x.reciprocal()).subtract(3);
123 }
124 });
125 compare(new TestFunction(2.8424389537844470678, -5, 5) {
126 @Override
127 public DerivativeStructure value(DerivativeStructure x) {
128 return x.exp().add(x).subtract(20);
129 }
130 });
131 compare(new TestFunction(8.3094326942315717953, 0.001, 10) {
132 @Override
133 public DerivativeStructure value(DerivativeStructure x) {
134 return x.log().add(x.sqrt()).subtract(5);
135 }
136 });
137 compare(new TestFunction(1.4655712318767680266, -0.5, 1.5) {
138 @Override
139 public DerivativeStructure value(DerivativeStructure x) {
140 return x.subtract(1).multiply(x).multiply(x).subtract(1);
141 }
142 });
143 }
144
145 private void compare(TestFunction f) {
146 compare(f, f.getRoot(), f.getMin(), f.getMax());
147 }
148
149 private void compare(final UnivariateDifferentiableFunction f,
150 double root, double min, double max) {
151 NewtonRaphsonSolver newton = new NewtonRaphsonSolver(1.0e-12);
152 BracketingNthOrderBrentSolver bracketing =
153 new BracketingNthOrderBrentSolver(1.0e-12, 1.0e-12, 1.0e-18, 5);
154 double resultN;
155 try {
156 resultN = newton.solve(100, f, min, max);
157 } catch (TooManyEvaluationsException tmee) {
158 resultN = Double.NaN;
159 }
160 double resultB;
161 try {
162 resultB = bracketing.solve(100, f, min, max);
163 } catch (TooManyEvaluationsException tmee) {
164 resultB = Double.NaN;
165 }
166 Assert.assertEquals(root, resultN, newton.getAbsoluteAccuracy());
167 Assert.assertEquals(root, resultB, bracketing.getAbsoluteAccuracy());
168
169
170 final int weightedBracketingEvaluations = bracketing.getEvaluations();
171
172
173 final int weightedNewtonEvaluations = 2 * newton.getEvaluations();
174
175 Assert.assertTrue(weightedBracketingEvaluations < weightedNewtonEvaluations);
176 }
177
178 private abstract static class TestFunction implements UnivariateDifferentiableFunction {
179
180 private final double root;
181 private final double min;
182 private final double max;
183
184 protected TestFunction(final double root, final double min, final double max) {
185 this.root = root;
186 this.min = min;
187 this.max = max;
188 }
189
190 public double getRoot() {
191 return root;
192 }
193
194 public double getMin() {
195 return min;
196 }
197
198 public double getMax() {
199 return max;
200 }
201
202 @Override
203 public double value(final double x) {
204 return value(new DerivativeStructure(0, 0, x)).getValue();
205 }
206
207 @Override
208 public abstract DerivativeStructure value(DerivativeStructure t);
209 }
210 }