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 * http://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 package org.apache.commons.math4.legacy.analysis.solvers;
19
20 import org.apache.commons.math4.legacy.analysis.differentiation.DerivativeStructure;
21 import org.apache.commons.math4.legacy.analysis.differentiation.UnivariateDifferentiableFunction;
22 import org.apache.commons.math4.legacy.exception.TooManyEvaluationsException;
23 import org.apache.commons.math4.core.jdkmath.JdkMath;
24
25 /**
26 * Implements <a href="http://mathworld.wolfram.com/NewtonsMethod.html">
27 * Newton's Method</a> for finding zeros of real univariate differentiable
28 * functions.
29 *
30 * @since 3.1
31 */
32 public class NewtonRaphsonSolver extends AbstractUnivariateDifferentiableSolver {
33 /** Default absolute accuracy. */
34 private static final double DEFAULT_ABSOLUTE_ACCURACY = 1e-6;
35
36 /**
37 * Construct a solver.
38 */
39 public NewtonRaphsonSolver() {
40 this(DEFAULT_ABSOLUTE_ACCURACY);
41 }
42 /**
43 * Construct a solver.
44 *
45 * @param absoluteAccuracy Absolute accuracy.
46 */
47 public NewtonRaphsonSolver(double absoluteAccuracy) {
48 super(absoluteAccuracy);
49 }
50
51 /**
52 * Find a zero near the midpoint of {@code min} and {@code max}.
53 *
54 * @param f Function to solve.
55 * @param min Lower bound for the interval.
56 * @param max Upper bound for the interval.
57 * @param maxEval Maximum number of evaluations.
58 * @return the value where the function is zero.
59 * @throws org.apache.commons.math4.legacy.exception.TooManyEvaluationsException
60 * if the maximum evaluation count is exceeded.
61 * @throws org.apache.commons.math4.legacy.exception.NumberIsTooLargeException
62 * if {@code min >= max}.
63 */
64 @Override
65 public double solve(int maxEval, final UnivariateDifferentiableFunction f,
66 final double min, final double max)
67 throws TooManyEvaluationsException {
68 return super.solve(maxEval, f, UnivariateSolverUtils.midpoint(min, max));
69 }
70
71 /**
72 * {@inheritDoc}
73 */
74 @Override
75 protected double doSolve()
76 throws TooManyEvaluationsException {
77 final double startValue = getStartValue();
78 final double absoluteAccuracy = getAbsoluteAccuracy();
79
80 double x0 = startValue;
81 double x1;
82 while (true) {
83 final DerivativeStructure y0 = computeObjectiveValueAndDerivative(x0);
84 x1 = x0 - (y0.getValue() / y0.getPartialDerivative(1));
85 if (JdkMath.abs(x1 - x0) <= absoluteAccuracy) {
86 return x1;
87 }
88
89 x0 = x1;
90 }
91 }
92 }