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.math.analysis.solvers;
19
20 import org.apache.commons.math.FunctionEvaluationException;
21 import org.apache.commons.math.MathRuntimeException;
22 import org.apache.commons.math.MaxIterationsExceededException;
23 import org.apache.commons.math.analysis.DifferentiableUnivariateRealFunction;
24 import org.apache.commons.math.analysis.UnivariateRealFunction;
25
26 /**
27 * Implements <a href="http://mathworld.wolfram.com/NewtonsMethod.html">
28 * Newton's Method</a> for finding zeros of real univariate functions.
29 * <p>
30 * The function should be continuous but not necessarily smooth.</p>
31 *
32 * @version $Revision: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $
33 */
34 public class NewtonSolver extends UnivariateRealSolverImpl {
35
36 /**
37 * Construct a solver for the given function.
38 * @param f function to solve.
39 * @deprecated as of 2.0 the function to solve is passed as an argument
40 * to the {@link #solve(UnivariateRealFunction, double, double)} or
41 * {@link UnivariateRealSolverImpl#solve(UnivariateRealFunction, double, double, double)}
42 * method.
43 */
44 @Deprecated
45 public NewtonSolver(DifferentiableUnivariateRealFunction f) {
46 super(f, 100, 1E-6);
47 }
48
49 /**
50 * Construct a solver.
51 */
52 public NewtonSolver() {
53 super(100, 1E-6);
54 }
55
56 /** {@inheritDoc} */
57 @Deprecated
58 public double solve(final double min, final double max)
59 throws MaxIterationsExceededException,
60 FunctionEvaluationException {
61 return solve(f, min, max);
62 }
63
64 /** {@inheritDoc} */
65 @Deprecated
66 public double solve(final double min, final double max, final double startValue)
67 throws MaxIterationsExceededException, FunctionEvaluationException {
68 return solve(f, min, max, startValue);
69 }
70
71 /**
72 * Find a zero near the midpoint of <code>min</code> and <code>max</code>.
73 *
74 * @param f the function to solve
75 * @param min the lower bound for the interval
76 * @param max the upper bound for the interval
77 * @return the value where the function is zero
78 * @throws MaxIterationsExceededException if the maximum iteration count is exceeded
79 * @throws FunctionEvaluationException if an error occurs evaluating the
80 * function or derivative
81 * @throws IllegalArgumentException if min is not less than max
82 */
83 public double solve(final UnivariateRealFunction f,
84 final double min, final double max)
85 throws MaxIterationsExceededException, FunctionEvaluationException {
86 return solve(f, min, max, UnivariateRealSolverUtils.midpoint(min, max));
87 }
88
89 /**
90 * Find a zero near the value <code>startValue</code>.
91 *
92 * @param f the function to solve
93 * @param min the lower bound for the interval (ignored).
94 * @param max the upper bound for the interval (ignored).
95 * @param startValue the start value to use.
96 * @return the value where the function is zero
97 * @throws MaxIterationsExceededException if the maximum iteration count is exceeded
98 * @throws FunctionEvaluationException if an error occurs evaluating the
99 * function or derivative
100 * @throws IllegalArgumentException if startValue is not between min and max or
101 * if function is not a {@link DifferentiableUnivariateRealFunction} instance
102 */
103 public double solve(final UnivariateRealFunction f,
104 final double min, final double max, final double startValue)
105 throws MaxIterationsExceededException, FunctionEvaluationException {
106
107 try {
108
109 final UnivariateRealFunction derivative =
110 ((DifferentiableUnivariateRealFunction) f).derivative();
111 clearResult();
112 verifySequence(min, startValue, max);
113
114 double x0 = startValue;
115 double x1;
116
117 int i = 0;
118 while (i < maximalIterationCount) {
119
120 x1 = x0 - (f.value(x0) / derivative.value(x0));
121 if (Math.abs(x1 - x0) <= absoluteAccuracy) {
122 setResult(x1, i);
123 return x1;
124 }
125
126 x0 = x1;
127 ++i;
128 }
129
130 throw new MaxIterationsExceededException(maximalIterationCount);
131 } catch (ClassCastException cce) {
132 throw MathRuntimeException.createIllegalArgumentException("function is not differentiable");
133 }
134 }
135
136 }