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
18package org.apache.commons.math.analysis.solvers;
19
20import org.apache.commons.math.FunctionEvaluationException;
21import org.apache.commons.math.MathRuntimeException;
22import org.apache.commons.math.MaxIterationsExceededException;
23import org.apache.commons.math.analysis.DifferentiableUnivariateRealFunction;
24import org.apache.commons.math.analysis.UnivariateRealFunction;
25import org.apache.commons.math.exception.util.LocalizedFormats;
26import org.apache.commons.math.util.FastMath;
27
28/**
29 * Implements <a href="http://mathworld.wolfram.com/NewtonsMethod.html">
30 * Newton's Method</a> for finding zeros of real univariate functions.
31 * <p>
32 * The function should be continuous but not necessarily smooth.</p>
33 *
34 * @version $Revision: 1070725 $ $Date: 2011-02-15 02:31:12 +0100 (mar. 15 févr. 2011) $
35 */
36public class NewtonSolver extends UnivariateRealSolverImpl {
37
38    /**
39     * Construct a solver for the given function.
40     * @param f function to solve.
41     * @deprecated as of 2.0 the function to solve is passed as an argument
42     * to the {@link #solve(UnivariateRealFunction, double, double)} or
43     * {@link UnivariateRealSolverImpl#solve(UnivariateRealFunction, double, double, double)}
44     * method.
45     */
46    @Deprecated
47    public NewtonSolver(DifferentiableUnivariateRealFunction f) {
48        super(f, 100, 1E-6);
49    }
50
51    /**
52     * Construct a solver.
53     * @deprecated in 2.2 (to be removed in 3.0).
54     */
55    @Deprecated
56    public NewtonSolver() {
57        super(100, 1E-6);
58    }
59
60    /** {@inheritDoc} */
61    @Deprecated
62    public double solve(final double min, final double max)
63        throws MaxIterationsExceededException, FunctionEvaluationException  {
64        return solve(f, min, max);
65    }
66
67    /** {@inheritDoc} */
68    @Deprecated
69    public double solve(final double min, final double max, final double startValue)
70        throws MaxIterationsExceededException, FunctionEvaluationException  {
71        return solve(f, min, max, startValue);
72    }
73
74    /**
75     * Find a zero near the midpoint of <code>min</code> and <code>max</code>.
76     *
77     * @param f the function to solve
78     * @param min the lower bound for the interval
79     * @param max the upper bound for the interval
80     * @param maxEval Maximum number of evaluations.
81     * @return the value where the function is zero
82     * @throws MaxIterationsExceededException if the maximum iteration count is exceeded
83     * @throws FunctionEvaluationException if an error occurs evaluating the function or derivative
84     * @throws IllegalArgumentException if min is not less than max
85     */
86    @Override
87    public double solve(int maxEval, final UnivariateRealFunction f,
88                        final double min, final double max)
89        throws MaxIterationsExceededException, FunctionEvaluationException  {
90        setMaximalIterationCount(maxEval);
91        return solve(f, min, max);
92    }
93
94    /**
95     * Find a zero near the midpoint of <code>min</code> and <code>max</code>.
96     *
97     * @param f the function to solve
98     * @param min the lower bound for the interval
99     * @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}
184