| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package org.apache.commons.numbers.rootfinder; |
| |
| import java.util.function.DoubleUnaryOperator; |
| |
| import org.junit.jupiter.api.Assertions; |
| import org.junit.jupiter.api.Test; |
| |
| /** |
| * Test cases for the {@link BrentSolver} class. |
| */ |
| public class BrentSolverTest { |
| private static final double DEFAULT_ABSOLUTE_ACCURACY = 1e-6; |
| private static final double DEFAULT_RELATIVE_ACCURACY = 1e-14; |
| private static final double DEFAULT_FUNCTION_ACCURACY = 1e-15; |
| |
| @Test |
| void testSinZero() { |
| // The sinus function is behaved well around the root at pi. The second |
| // order derivative is zero, which means linar approximating methods will |
| // still converge quadratically. |
| final DoubleUnaryOperator func = new Sin(); |
| final BrentSolver solver = new BrentSolver(DEFAULT_ABSOLUTE_ACCURACY, |
| DEFAULT_RELATIVE_ACCURACY, |
| DEFAULT_FUNCTION_ACCURACY); |
| |
| double result; |
| MonitoredFunction f; |
| |
| // Somewhat benign interval. The function is monotonous. |
| f = new MonitoredFunction(func); |
| result = solver.findRoot(f, 3, 4); |
| Assertions.assertEquals(Math.PI, result, DEFAULT_ABSOLUTE_ACCURACY); |
| Assertions.assertTrue(f.getCallsCount() <= 7); |
| |
| // Larger and somewhat less benign interval. The function is grows first. |
| f = new MonitoredFunction(func); |
| result = solver.findRoot(f, 1, 4); |
| Assertions.assertEquals(Math.PI, result, DEFAULT_ABSOLUTE_ACCURACY); |
| Assertions.assertTrue(f.getCallsCount() <= 8); |
| } |
| |
| @Test |
| void testQuinticZero() { |
| // The quintic function has zeros at 0, +-0.5 and +-1. |
| // Around the root of 0 the function is well behaved, with a second derivative |
| // of zero a 0. |
| // The other roots are less well to find, in particular the root at 1, because |
| // the function grows fast for x>1. |
| // The function has extrema (first derivative is zero) at 0.27195613 and 0.82221643, |
| // intervals containing these values are harder for the solvers. |
| final DoubleUnaryOperator func = new QuinticFunction(); |
| final BrentSolver solver = new BrentSolver(DEFAULT_ABSOLUTE_ACCURACY, |
| DEFAULT_RELATIVE_ACCURACY, |
| DEFAULT_FUNCTION_ACCURACY); |
| |
| double result; |
| MonitoredFunction f; |
| |
| // Symmetric bracket around 0. Test whether solvers can handle hitting |
| // the root in the first iteration. |
| f = new MonitoredFunction(func); |
| result = solver.findRoot(f, -0.2, 0.2); |
| Assertions.assertEquals(0, result, DEFAULT_ABSOLUTE_ACCURACY); |
| Assertions.assertTrue(f.getCallsCount() <= 3); |
| |
| // 1 iterations on i586 JDK 1.4.1. |
| // Asymmetric bracket around 0. Contains extremum. |
| f = new MonitoredFunction(func); |
| result = solver.findRoot(f, -0.1, 0.3); |
| Assertions.assertEquals(0, result, DEFAULT_ABSOLUTE_ACCURACY); |
| // 5 iterations on i586 JDK 1.4.1. |
| Assertions.assertTrue(f.getCallsCount() <= 7); |
| |
| // Large bracket around 0. Contains two extrema. |
| f = new MonitoredFunction(func); |
| result = solver.findRoot(f, -0.3, 0.45); |
| Assertions.assertEquals(0, result, DEFAULT_ABSOLUTE_ACCURACY); |
| // 6 iterations on i586 JDK 1.4.1. |
| Assertions.assertTrue(f.getCallsCount() <= 8); |
| |
| // Benign bracket around 0.5, function is monotonous. |
| f = new MonitoredFunction(func); |
| result = solver.findRoot(f, 0.3, 0.7); |
| Assertions.assertEquals(0.5, result, DEFAULT_ABSOLUTE_ACCURACY); |
| // 6 iterations on i586 JDK 1.4.1. |
| Assertions.assertTrue(f.getCallsCount() <= 9); |
| |
| // Less benign bracket around 0.5, contains one extremum. |
| f = new MonitoredFunction(func); |
| result = solver.findRoot(f, 0.2, 0.6); |
| Assertions.assertEquals(0.5, result, DEFAULT_ABSOLUTE_ACCURACY); |
| Assertions.assertTrue(f.getCallsCount() <= 10); |
| |
| // Large, less benign bracket around 0.5, contains both extrema. |
| f = new MonitoredFunction(func); |
| result = solver.findRoot(f, 0.05, 0.95); |
| Assertions.assertEquals(0.5, result, DEFAULT_ABSOLUTE_ACCURACY); |
| Assertions.assertTrue(f.getCallsCount() <= 11); |
| |
| // Relatively benign bracket around 1, function is monotonous. Fast growth for x>1 |
| // is still a problem. |
| f = new MonitoredFunction(func); |
| result = solver.findRoot(f, 0.85, 1.25); |
| Assertions.assertEquals(1.0, result, DEFAULT_ABSOLUTE_ACCURACY); |
| Assertions.assertTrue(f.getCallsCount() <= 11); |
| |
| // Less benign bracket around 1 with extremum. |
| f = new MonitoredFunction(func); |
| result = solver.findRoot(f, 0.8, 1.2); |
| Assertions.assertEquals(1.0, result, DEFAULT_ABSOLUTE_ACCURACY); |
| Assertions.assertTrue(f.getCallsCount() <= 11); |
| |
| // Large bracket around 1. Monotonous. |
| f = new MonitoredFunction(func); |
| result = solver.findRoot(f, 0.85, 1.75); |
| Assertions.assertEquals(1.0, result, DEFAULT_ABSOLUTE_ACCURACY); |
| Assertions.assertTrue(f.getCallsCount() <= 13); |
| |
| // Large bracket around 1. Interval contains extremum. |
| f = new MonitoredFunction(func); |
| result = solver.findRoot(f, 0.55, 1.45); |
| Assertions.assertEquals(1.0, result, DEFAULT_ABSOLUTE_ACCURACY); |
| Assertions.assertTrue(f.getCallsCount() <= 10); |
| } |
| |
| @Test |
| void testTooManyCalls() { |
| final DoubleUnaryOperator func = new QuinticFunction(); |
| final BrentSolver solver = new BrentSolver(DEFAULT_ABSOLUTE_ACCURACY, |
| DEFAULT_RELATIVE_ACCURACY, |
| DEFAULT_FUNCTION_ACCURACY); |
| |
| double result; |
| MonitoredFunction f; |
| |
| // Very large bracket around 1 for testing fast growth behavior. |
| f = new MonitoredFunction(func); |
| result = solver.findRoot(f, 0.85, 5); |
| Assertions.assertEquals(1.0, result, DEFAULT_ABSOLUTE_ACCURACY); |
| Assertions.assertTrue(f.getCallsCount() <= 15); |
| |
| try { |
| f = new MonitoredFunction(func, 10); |
| result = solver.findRoot(f, 0.85, 5); |
| Assertions.fail("Expected too many calls condition"); |
| } catch (IllegalStateException ex) { |
| // Expected. |
| // Ensure expected error condition. |
| Assertions.assertNotEquals(-1, ex.getMessage().indexOf("too many calls")); |
| } |
| } |
| |
| @Test |
| void testRootEndpoints() { |
| final DoubleUnaryOperator f = new Sin(); |
| final BrentSolver solver = new BrentSolver(DEFAULT_ABSOLUTE_ACCURACY, |
| DEFAULT_RELATIVE_ACCURACY, |
| DEFAULT_FUNCTION_ACCURACY); |
| |
| // Endpoint is root. |
| double result = solver.findRoot(f, Math.PI, 4); |
| Assertions.assertEquals(Math.PI, result, DEFAULT_ABSOLUTE_ACCURACY); |
| |
| result = solver.findRoot(f, 3, Math.PI); |
| Assertions.assertEquals(Math.PI, result, DEFAULT_ABSOLUTE_ACCURACY); |
| |
| result = solver.findRoot(f, Math.PI, 3.5, 4); |
| Assertions.assertEquals(Math.PI, result, DEFAULT_ABSOLUTE_ACCURACY); |
| |
| result = solver.findRoot(f, 3, 3.07, Math.PI); |
| Assertions.assertEquals(Math.PI, result, DEFAULT_ABSOLUTE_ACCURACY); |
| } |
| |
| @Test |
| void testBadEndpoints() { |
| final DoubleUnaryOperator f = new Sin(); |
| final BrentSolver solver = new BrentSolver(DEFAULT_ABSOLUTE_ACCURACY, |
| DEFAULT_RELATIVE_ACCURACY, |
| DEFAULT_FUNCTION_ACCURACY); |
| try { // Bad interval. |
| solver.findRoot(f, 1, -1); |
| Assertions.fail("Expecting bad interval condition"); |
| } catch (SolverException ex) { |
| // Ensure expected error condition. |
| Assertions.assertNotEquals(-1, ex.getMessage().indexOf(" > ")); |
| } |
| try { // No bracketing. |
| solver.findRoot(f, 1, 1.5); |
| Assertions.fail("Expecting non-bracketing condition"); |
| } catch (SolverException ex) { |
| // Ensure expected error condition. |
| Assertions.assertNotEquals(-1, ex.getMessage().indexOf("No bracketing")); |
| } |
| try { // No bracketing. |
| solver.findRoot(f, 1, 1.2, 1.5); |
| Assertions.fail("Expecting non-bracketing condition"); |
| } catch (SolverException ex) { |
| // Ensure expected error condition. |
| Assertions.assertNotEquals(-1, ex.getMessage().indexOf("No bracketing")); |
| } |
| } |
| |
| @Test |
| void testBadInitialGuess() { |
| final DoubleUnaryOperator func = new QuinticFunction(); |
| final BrentSolver solver = new BrentSolver(DEFAULT_ABSOLUTE_ACCURACY, |
| DEFAULT_RELATIVE_ACCURACY, |
| DEFAULT_FUNCTION_ACCURACY); |
| |
| try { |
| // Invalid guess (it *is* a root, but outside of the range). |
| double result = solver.findRoot(func, 0.0, 7.0, 0.6); |
| Assertions.fail("an out of range condition was expected"); |
| } catch (SolverException ex) { |
| // Ensure expected error condition. |
| Assertions.assertNotEquals(-1, ex.getMessage().indexOf("out of range")); |
| } |
| } |
| |
| @Test |
| void testInitialGuess() { |
| final DoubleUnaryOperator func = new QuinticFunction(); |
| final BrentSolver solver = new BrentSolver(DEFAULT_ABSOLUTE_ACCURACY, |
| DEFAULT_RELATIVE_ACCURACY, |
| DEFAULT_FUNCTION_ACCURACY); |
| double result; |
| MonitoredFunction f; |
| |
| // No guess. |
| f = new MonitoredFunction(func); |
| result = solver.findRoot(f, 0.6, 7.0); |
| Assertions.assertEquals(1.0, result, DEFAULT_ABSOLUTE_ACCURACY); |
| final int referenceCallsCount = f.getCallsCount(); |
| Assertions.assertTrue(referenceCallsCount >= 13); |
| |
| // Bad guess. |
| f = new MonitoredFunction(func); |
| result = solver.findRoot(f, 0.6, 0.61, 7.0); |
| Assertions.assertEquals(1.0, result, DEFAULT_ABSOLUTE_ACCURACY); |
| Assertions.assertTrue(f.getCallsCount() > referenceCallsCount); |
| |
| // Good guess. |
| f = new MonitoredFunction(func); |
| result = solver.findRoot(f, 0.6, 0.9999990001, 7.0); |
| Assertions.assertEquals(1.0, result, DEFAULT_ABSOLUTE_ACCURACY); |
| Assertions.assertTrue(f.getCallsCount() < referenceCallsCount); |
| |
| // Perfect guess. |
| f = new MonitoredFunction(func); |
| result = solver.findRoot(f, 0.6, 1.0, 7.0); |
| Assertions.assertEquals(1.0, result, DEFAULT_ABSOLUTE_ACCURACY); |
| Assertions.assertEquals(1, f.getCallsCount()); |
| } |
| } |