1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.math.analysis;
18
19 import org.apache.commons.math.ConvergenceException;
20 import org.apache.commons.math.FunctionEvaluationException;
21
22 /***
23 * Implements <a href="http://mathworld.wolfram.com/NewtonsMethod.html">
24 * Newton's Method</a> for finding zeros of real univariate functions.
25 * <p>
26 * The function should be continuous but not necessarily smooth.
27 *
28 * @version $Revision: 1.6 $ $Date: 2004/07/17 21:19:39 $
29 */
30 public class NewtonSolver extends UnivariateRealSolverImpl {
31
32 /*** Serializable version identifier */
33 static final long serialVersionUID = 2606474895443431607L;
34
35 /*** The first derivative of the target function. */
36 private UnivariateRealFunction derivative;
37
38 /***
39 * Construct a solver for the given function.
40 * @param f function to solve.
41 */
42 public NewtonSolver(DifferentiableUnivariateRealFunction f) {
43 super(f, 100, 1E-6);
44 derivative = f.derivative();
45 }
46
47 /***
48 * Find a zero near the midpoint of <code>min</code> and <code>max</code>.
49 *
50 * @param min the lower bound for the interval
51 * @param max the upper bound for the interval
52 * @return the value where the function is zero
53 * @throws ConvergenceException if the maximum iteration count is exceeded
54 * @throws FunctionEvaluationException if an error occurs evaluating the
55 * function or derivative
56 * @throws IllegalArgumentException if min is not less than max
57 */
58 public double solve(double min, double max) throws ConvergenceException,
59 FunctionEvaluationException {
60 return solve(min, max, UnivariateRealSolverUtils.midpoint(min, max));
61 }
62
63 /***
64 * Find a zero near the value <code>startValue</code>.
65 *
66 * @param min the lower bound for the interval (ignored).
67 * @param max the upper bound for the interval (ignored).
68 * @param startValue the start value to use.
69 * @return the value where the function is zero
70 * @throws ConvergenceException if the maximum iteration count is exceeded
71 * @throws FunctionEvaluationException if an error occurs evaluating the
72 * function or derivative
73 * @throws IllegalArgumentException if startValue is not between min and max
74 */
75 public double solve(double min, double max, double startValue)
76 throws ConvergenceException, FunctionEvaluationException {
77
78 clearResult();
79 verifySequence(min, startValue, max);
80
81 double x0 = startValue;
82 double x1;
83
84 int i = 0;
85 while (i < maximalIterationCount) {
86 x1 = x0 - (f.value(x0) / derivative.value(x0));
87 if (Math.abs(x1 - x0) <= absoluteAccuracy) {
88
89 setResult(x1, i);
90 return x1;
91 }
92
93 x0 = x1;
94 ++i;
95 }
96
97 throw new ConvergenceException
98 ("Maximum number of iterations exceeded " + i);
99 }
100
101 }