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 java.io.IOException;
20 import org.apache.commons.math.ConvergenceException;
21 import org.apache.commons.math.FunctionEvaluationException;
22
23 /**
24 * Implements <a href="http://mathworld.wolfram.com/NewtonsMethod.html">
25 * Newton's Method</a> for finding zeros of real univariate functions.
26 * <p>
27 * The function should be continuous but not necessarily smooth.
28 *
29 * @version $Revision: 348791 $ $Date: 2005-11-24 12:50:36 -0700 (Thu, 24 Nov 2005) $
30 */
31 public class NewtonSolver extends UnivariateRealSolverImpl {
32
33 /** Serializable version identifier */
34 private static final long serialVersionUID = 2606474895443431607L;
35
36 /** The first derivative of the target function. */
37 private transient UnivariateRealFunction derivative;
38
39 /**
40 * Construct a solver for the given function.
41 * @param f function to solve.
42 */
43 public NewtonSolver(DifferentiableUnivariateRealFunction f) {
44 super(f, 100, 1E-6);
45 derivative = f.derivative();
46 }
47
48 /**
49 * Find a zero near the midpoint of <code>min</code> and <code>max</code>.
50 *
51 * @param min the lower bound for the interval
52 * @param max the upper bound for the interval
53 * @return the value where the function is zero
54 * @throws ConvergenceException if the maximum iteration count is exceeded
55 * @throws FunctionEvaluationException if an error occurs evaluating the
56 * function or derivative
57 * @throws IllegalArgumentException if min is not less than max
58 */
59 public double solve(double min, double max) throws ConvergenceException,
60 FunctionEvaluationException {
61 return solve(min, max, UnivariateRealSolverUtils.midpoint(min, max));
62 }
63
64 /**
65 * Find a zero near the value <code>startValue</code>.
66 *
67 * @param min the lower bound for the interval (ignored).
68 * @param max the upper bound for the interval (ignored).
69 * @param startValue the start value to use.
70 * @return the value where the function is zero
71 * @throws ConvergenceException if the maximum iteration count is exceeded
72 * @throws FunctionEvaluationException if an error occurs evaluating the
73 * function or derivative
74 * @throws IllegalArgumentException if startValue is not between min and max
75 */
76 public double solve(double min, double max, double startValue)
77 throws ConvergenceException, FunctionEvaluationException {
78
79 clearResult();
80 verifySequence(min, startValue, max);
81
82 double x0 = startValue;
83 double x1;
84
85 int i = 0;
86 while (i < maximalIterationCount) {
87 x1 = x0 - (f.value(x0) / derivative.value(x0));
88 if (Math.abs(x1 - x0) <= absoluteAccuracy) {
89
90 setResult(x1, i);
91 return x1;
92 }
93
94 x0 = x1;
95 ++i;
96 }
97
98 throw new ConvergenceException
99 ("Maximum number of iterations exceeded " + i);
100 }
101
102 /**
103 * Custom deserialization to initialize transient deriviate field.
104 *
105 * @param in serialized object input stream
106 * @throws IOException if IO error occurs
107 * @throws ClassNotFoundException if instantiation error occurs
108 */
109 private void readObject(java.io.ObjectInputStream in)
110 throws IOException, ClassNotFoundException {
111 in.defaultReadObject();
112 derivative = ((DifferentiableUnivariateRealFunction) f).derivative();
113 }
114 }