commons-numbers-rootfinder/src/test/java/org/apache/commons/numbers/rootfinder/BrentSolverTest.java - commons-numbers - Git at Google

 /*
  * 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);

         // Very large bracket around 1 for testing fast growth behavior.
         final MonitoredFunction f = new MonitoredFunction(func);
         final double result = solver.findRoot(f, 0.85, 5);
         Assertions.assertEquals(1.0, result, DEFAULT_ABSOLUTE_ACCURACY);
         Assertions.assertTrue(f.getCallsCount() <= 15);

         final MonitoredFunction f2 = new MonitoredFunction(func, 10);
         final IllegalArgumentException ex = Assertions.assertThrows(IllegalArgumentException.class,
             () -> solver.findRoot(f2, 0.85, 5), "Expected too many calls condition");
         // 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());
     }
 }
	/*
	* 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);

	// Very large bracket around 1 for testing fast growth behavior.
	final MonitoredFunction f = new MonitoredFunction(func);
	final double result = solver.findRoot(f, 0.85, 5);
	Assertions.assertEquals(1.0, result, DEFAULT_ABSOLUTE_ACCURACY);
	Assertions.assertTrue(f.getCallsCount() <= 15);

	final MonitoredFunction f2 = new MonitoredFunction(func, 10);
	final IllegalArgumentException ex = Assertions.assertThrows(IllegalArgumentException.class,
	() -> solver.findRoot(f2, 0.85, 5), "Expected too many calls condition");
	// 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());
	}
	}