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.math3.analysis.solvers;
019    
020    import org.apache.commons.math3.analysis.differentiation.DerivativeStructure;
021    import org.apache.commons.math3.analysis.differentiation.UnivariateDifferentiableFunction;
022    import org.apache.commons.math3.util.FastMath;
023    import org.apache.commons.math3.exception.TooManyEvaluationsException;
024    
025    /**
026     * Implements <a href="http://mathworld.wolfram.com/NewtonsMethod.html">
027     * Newton's Method</a> for finding zeros of real univariate differentiable
028     * functions.
029     *
030     * @since 3.1
031     * @version $Id: NewtonRaphsonSolver.java 1383441 2012-09-11 14:56:39Z luc $
032     */
033    public class NewtonRaphsonSolver extends AbstractUnivariateDifferentiableSolver {
034        /** Default absolute accuracy. */
035        private static final double DEFAULT_ABSOLUTE_ACCURACY = 1e-6;
036    
037        /**
038         * Construct a solver.
039         */
040        public NewtonRaphsonSolver() {
041            this(DEFAULT_ABSOLUTE_ACCURACY);
042        }
043        /**
044         * Construct a solver.
045         *
046         * @param absoluteAccuracy Absolute accuracy.
047         */
048        public NewtonRaphsonSolver(double absoluteAccuracy) {
049            super(absoluteAccuracy);
050        }
051    
052        /**
053         * Find a zero near the midpoint of {@code min} and {@code max}.
054         *
055         * @param f Function to solve.
056         * @param min Lower bound for the interval.
057         * @param max Upper bound for the interval.
058         * @param maxEval Maximum number of evaluations.
059         * @return the value where the function is zero.
060         * @throws org.apache.commons.math3.exception.TooManyEvaluationsException
061         * if the maximum evaluation count is exceeded.
062         * @throws org.apache.commons.math3.exception.NumberIsTooLargeException
063         * if {@code min >= max}.
064         */
065        @Override
066        public double solve(int maxEval, final UnivariateDifferentiableFunction f,
067                            final double min, final double max)
068            throws TooManyEvaluationsException {
069            return super.solve(maxEval, f, UnivariateSolverUtils.midpoint(min, max));
070        }
071    
072        /**
073         * {@inheritDoc}
074         */
075        @Override
076        protected double doSolve()
077            throws TooManyEvaluationsException {
078            final double startValue = getStartValue();
079            final double absoluteAccuracy = getAbsoluteAccuracy();
080    
081            double x0 = startValue;
082            double x1;
083            while (true) {
084                final DerivativeStructure y0 = computeObjectiveValueAndDerivative(x0);
085                x1 = x0 - (y0.getValue() / y0.getPartialDerivative(1));
086                if (FastMath.abs(x1 - x0) <= absoluteAccuracy) {
087                    return x1;
088                }
089    
090                x0 = x1;
091            }
092        }
093    }