    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    }