001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017
018 package org.apache.commons.math.analysis.solvers;
019
020 import org.apache.commons.math.FunctionEvaluationException;
021 import org.apache.commons.math.MathRuntimeException;
022 import org.apache.commons.math.MaxIterationsExceededException;
023 import org.apache.commons.math.analysis.DifferentiableUnivariateRealFunction;
024 import org.apache.commons.math.analysis.UnivariateRealFunction;
025 import org.apache.commons.math.exception.util.LocalizedFormats;
026 import org.apache.commons.math.util.FastMath;
027
028 /**
029 * Implements <a href="http://mathworld.wolfram.com/NewtonsMethod.html">
030 * Newton's Method</a> for finding zeros of real univariate functions.
031 * <p>
032 * The function should be continuous but not necessarily smooth.</p>
033 *
034 * @version $Revision: 1070725 $ $Date: 2011-02-15 02:31:12 +0100 (mar. 15 f??vr. 2011) $
035 */
036 public class NewtonSolver extends UnivariateRealSolverImpl {
037
038 /**
039 * Construct a solver for the given function.
040 * @param f function to solve.
041 * @deprecated as of 2.0 the function to solve is passed as an argument
042 * to the {@link #solve(UnivariateRealFunction, double, double)} or
043 * {@link UnivariateRealSolverImpl#solve(UnivariateRealFunction, double, double, double)}
044 * method.
045 */
046 @Deprecated
047 public NewtonSolver(DifferentiableUnivariateRealFunction f) {
048 super(f, 100, 1E-6);
049 }
050
051 /**
052 * Construct a solver.
053 * @deprecated in 2.2 (to be removed in 3.0).
054 */
055 @Deprecated
056 public NewtonSolver() {
057 super(100, 1E-6);
058 }
059
060 /** {@inheritDoc} */
061 @Deprecated
062 public double solve(final double min, final double max)
063 throws MaxIterationsExceededException, FunctionEvaluationException {
064 return solve(f, min, max);
065 }
066
067 /** {@inheritDoc} */
068 @Deprecated
069 public double solve(final double min, final double max, final double startValue)
070 throws MaxIterationsExceededException, FunctionEvaluationException {
071 return solve(f, min, max, startValue);
072 }
073
074 /**
075 * Find a zero near the midpoint of <code>min</code> and <code>max</code>.
076 *
077 * @param f the function to solve
078 * @param min the lower bound for the interval
079 * @param max the upper bound for the interval
080 * @param maxEval Maximum number of evaluations.
081 * @return the value where the function is zero
082 * @throws MaxIterationsExceededException if the maximum iteration count is exceeded
083 * @throws FunctionEvaluationException if an error occurs evaluating the function or derivative
084 * @throws IllegalArgumentException if min is not less than max
085 */
086 @Override
087 public double solve(int maxEval, final UnivariateRealFunction f,
088 final double min, final double max)
089 throws MaxIterationsExceededException, FunctionEvaluationException {
090 setMaximalIterationCount(maxEval);
091 return solve(f, min, max);
092 }
093
094 /**
095 * Find a zero near the midpoint of <code>min</code> and <code>max</code>.
096 *
097 * @param f the function to solve
098 * @param min the lower bound for the interval
099 * @param max the upper bound for the interval
100 * @return the value where the function is zero
101 * @throws MaxIterationsExceededException if the maximum iteration count is exceeded
102 * @throws FunctionEvaluationException if an error occurs evaluating the function or derivative
103 * @throws IllegalArgumentException if min is not less than max
104 * @deprecated in 2.2 (to be removed in 3.0).
105 */
106 @Deprecated
107 public double solve(final UnivariateRealFunction f,
108 final double min, final double max)
109 throws MaxIterationsExceededException, FunctionEvaluationException {
110 return solve(f, min, max, UnivariateRealSolverUtils.midpoint(min, max));
111 }
112
113 /**
114 * Find a zero near the value <code>startValue</code>.
115 *
116 * @param f the function to solve
117 * @param min the lower bound for the interval (ignored).
118 * @param max the upper bound for the interval (ignored).
119 * @param startValue the start value to use.
120 * @param maxEval Maximum number of evaluations.
121 * @return the value where the function is zero
122 * @throws MaxIterationsExceededException if the maximum iteration count is exceeded
123 * @throws FunctionEvaluationException if an error occurs evaluating the function or derivative
124 * @throws IllegalArgumentException if startValue is not between min and max or
125 * if function is not a {@link DifferentiableUnivariateRealFunction} instance
126 */
127 @Override
128 public double solve(int maxEval, final UnivariateRealFunction f,
129 final double min, final double max, final double startValue)
130 throws MaxIterationsExceededException, FunctionEvaluationException {
131 setMaximalIterationCount(maxEval);
132 return solve(f, min, max, startValue);
133 }
134
135 /**
136 * Find a zero near the value <code>startValue</code>.
137 *
138 * @param f the function to solve
139 * @param min the lower bound for the interval (ignored).
140 * @param max the upper bound for the interval (ignored).
141 * @param startValue the start value to use.
142 * @return the value where the function is zero
143 * @throws MaxIterationsExceededException if the maximum iteration count is exceeded
144 * @throws FunctionEvaluationException if an error occurs evaluating the function or derivative
145 * @throws IllegalArgumentException if startValue is not between min and max or
146 * if function is not a {@link DifferentiableUnivariateRealFunction} instance
147 * @deprecated in 2.2 (to be removed in 3.0).
148 */
149 @Deprecated
150 public double solve(final UnivariateRealFunction f,
151 final double min, final double max, final double startValue)
152 throws MaxIterationsExceededException, FunctionEvaluationException {
153
154 try {
155
156 final UnivariateRealFunction derivative =
157 ((DifferentiableUnivariateRealFunction) f).derivative();
158 clearResult();
159 verifySequence(min, startValue, max);
160
161 double x0 = startValue;
162 double x1;
163
164 int i = 0;
165 while (i < maximalIterationCount) {
166
167 x1 = x0 - (f.value(x0) / derivative.value(x0));
168 if (FastMath.abs(x1 - x0) <= absoluteAccuracy) {
169 setResult(x1, i);
170 return x1;
171 }
172
173 x0 = x1;
174 ++i;
175 }
176
177 throw new MaxIterationsExceededException(maximalIterationCount);
178 } catch (ClassCastException cce) {
179 throw MathRuntimeException.createIllegalArgumentException(LocalizedFormats.FUNCTION_NOT_DIFFERENTIABLE);
180 }
181 }
182
183 }