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    
026    /**
027     * Implements <a href="http://mathworld.wolfram.com/NewtonsMethod.html">
028     * Newton's Method</a> for finding zeros of real univariate functions.
029     * <p>
030     * The function should be continuous but not necessarily smooth.</p>
031     *
032     * @version $Revision: 811685 $ $Date: 2009-09-05 13:36:48 -0400 (Sat, 05 Sep 2009) $
033     */
034    public class NewtonSolver extends UnivariateRealSolverImpl {
035    
036        /**
037         * Construct a solver for the given function.
038         * @param f function to solve.
039         * @deprecated as of 2.0 the function to solve is passed as an argument
040         * to the {@link #solve(UnivariateRealFunction, double, double)} or
041         * {@link UnivariateRealSolverImpl#solve(UnivariateRealFunction, double, double, double)}
042         * method.
043         */
044        @Deprecated
045        public NewtonSolver(DifferentiableUnivariateRealFunction f) {
046            super(f, 100, 1E-6);
047        }
048    
049        /**
050         * Construct a solver.
051         */
052        public NewtonSolver() {
053            super(100, 1E-6);
054        }
055    
056        /** {@inheritDoc} */
057        @Deprecated
058        public double solve(final double min, final double max)
059            throws MaxIterationsExceededException,
060            FunctionEvaluationException  {
061            return solve(f, min, max);
062        }
063    
064        /** {@inheritDoc} */
065        @Deprecated
066        public double solve(final double min, final double max, final double startValue)
067            throws MaxIterationsExceededException, FunctionEvaluationException  {
068            return solve(f, min, max, startValue);
069        }
070    
071        /**
072         * Find a zero near the midpoint of <code>min</code> and <code>max</code>.
073         *
074         * @param f the function to solve
075         * @param min the lower bound for the interval
076         * @param max the upper bound for the interval
077         * @return the value where the function is zero
078         * @throws MaxIterationsExceededException if the maximum iteration count is exceeded
079         * @throws FunctionEvaluationException if an error occurs evaluating the
080         * function or derivative
081         * @throws IllegalArgumentException if min is not less than max
082         */
083        public double solve(final UnivariateRealFunction f,
084                            final double min, final double max)
085            throws MaxIterationsExceededException, FunctionEvaluationException  {
086            return solve(f, min, max, UnivariateRealSolverUtils.midpoint(min, max));
087        }
088    
089        /**
090         * Find a zero near the value <code>startValue</code>.
091         *
092         * @param f the function to solve
093         * @param min the lower bound for the interval (ignored).
094         * @param max the upper bound for the interval (ignored).
095         * @param startValue the start value to use.
096         * @return the value where the function is zero
097         * @throws MaxIterationsExceededException if the maximum iteration count is exceeded
098         * @throws FunctionEvaluationException if an error occurs evaluating the
099         * 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    }