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
018package org.apache.commons.math3.analysis.solvers;
019
020import org.apache.commons.math3.analysis.differentiation.DerivativeStructure;
021import org.apache.commons.math3.analysis.differentiation.UnivariateDifferentiableFunction;
022import org.apache.commons.math3.util.FastMath;
023import 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 */
032public class NewtonRaphsonSolver extends AbstractUnivariateDifferentiableSolver {
033    /** Default absolute accuracy. */
034    private static final double DEFAULT_ABSOLUTE_ACCURACY = 1e-6;
035
036    /**
037     * Construct a solver.
038     */
039    public NewtonRaphsonSolver() {
040        this(DEFAULT_ABSOLUTE_ACCURACY);
041    }
042    /**
043     * Construct a solver.
044     *
045     * @param absoluteAccuracy Absolute accuracy.
046     */
047    public NewtonRaphsonSolver(double absoluteAccuracy) {
048        super(absoluteAccuracy);
049    }
050
051    /**
052     * Find a zero near the midpoint of {@code min} and {@code max}.
053     *
054     * @param f Function to solve.
055     * @param min Lower bound for the interval.
056     * @param max Upper bound for the interval.
057     * @param maxEval Maximum number of evaluations.
058     * @return the value where the function is zero.
059     * @throws org.apache.commons.math3.exception.TooManyEvaluationsException
060     * if the maximum evaluation count is exceeded.
061     * @throws org.apache.commons.math3.exception.NumberIsTooLargeException
062     * if {@code min >= max}.
063     */
064    @Override
065    public double solve(int maxEval, final UnivariateDifferentiableFunction f,
066                        final double min, final double max)
067        throws TooManyEvaluationsException {
068        return super.solve(maxEval, f, UnivariateSolverUtils.midpoint(min, max));
069    }
070
071    /**
072     * {@inheritDoc}
073     */
074    @Override
075    protected double doSolve()
076        throws TooManyEvaluationsException {
077        final double startValue = getStartValue();
078        final double absoluteAccuracy = getAbsoluteAccuracy();
079
080        double x0 = startValue;
081        double x1;
082        while (true) {
083            final DerivativeStructure y0 = computeObjectiveValueAndDerivative(x0);
084            x1 = x0 - (y0.getValue() / y0.getPartialDerivative(1));
085            if (FastMath.abs(x1 - x0) <= absoluteAccuracy) {
086                return x1;
087            }
088
089            x0 = x1;
090        }
091    }
092}