View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      https://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  
18  /*
19   * This is not the original file distributed by the Apache Software Foundation
20   * It has been modified by the Hipparchus project
21   */
22  
23  package org.hipparchus.analysis.solvers;
24  
25  import org.hipparchus.analysis.differentiation.DerivativeStructure;
26  import org.hipparchus.analysis.differentiation.UnivariateDifferentiableFunction;
27  import org.hipparchus.exception.MathIllegalStateException;
28  import org.hipparchus.util.FastMath;
29  
30  /**
31   * Implements <a href="http://mathworld.wolfram.com/NewtonsMethod.html">
32   * Newton's Method</a> for finding zeros of real univariate differentiable
33   * functions.
34   *
35   */
36  public class NewtonRaphsonSolver extends AbstractUnivariateDifferentiableSolver {
37      /** Default absolute accuracy. */
38      private static final double DEFAULT_ABSOLUTE_ACCURACY = 1e-6;
39  
40      /**
41       * Construct a solver.
42       */
43      public NewtonRaphsonSolver() {
44          this(DEFAULT_ABSOLUTE_ACCURACY);
45      }
46      /**
47       * Construct a solver.
48       *
49       * @param absoluteAccuracy Absolute accuracy.
50       */
51      public NewtonRaphsonSolver(double absoluteAccuracy) {
52          super(absoluteAccuracy);
53      }
54  
55      /**
56       * Find a zero near the midpoint of {@code min} and {@code max}.
57       *
58       * @param f Function to solve.
59       * @param min Lower bound for the interval.
60       * @param max Upper bound for the interval.
61       * @param maxEval Maximum number of evaluations.
62       * @return the value where the function is zero.
63       * @throws org.hipparchus.exception.MathIllegalStateException
64       * if the maximum evaluation count is exceeded.
65       * @throws org.hipparchus.exception.MathIllegalArgumentException
66       * if {@code min >= max}.
67       */
68      @Override
69      public double solve(int maxEval, final UnivariateDifferentiableFunction f,
70                          final double min, final double max)
71          throws MathIllegalStateException {
72          return super.solve(maxEval, f, UnivariateSolverUtils.midpoint(min, max));
73      }
74  
75      /**
76       * {@inheritDoc}
77       */
78      @Override
79      protected double doSolve()
80          throws MathIllegalStateException {
81          final double startValue = getStartValue();
82          final double absoluteAccuracy = getAbsoluteAccuracy();
83  
84          double x0 = startValue;
85          double x1;
86          while (true) {
87              final DerivativeStructure y0 = computeObjectiveValueAndDerivative(x0);
88              x1 = x0 - (y0.getValue() / y0.getPartialDerivative(1));
89              if (FastMath.abs(x1 - x0) <= absoluteAccuracy) {
90                  return x1;
91              }
92  
93              x0 = x1;
94          }
95      }
96  }