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.analysis.DifferentiableUnivariateRealFunction;
021    import org.apache.commons.math.util.FastMath;
022    
023    /**
024     * Implements <a href="http://mathworld.wolfram.com/NewtonsMethod.html">
025     * Newton's Method</a> for finding zeros of real univariate functions.
026     * <p>
027     * The function should be continuous but not necessarily smooth.</p>
028     *
029     * @version $Id: NewtonSolver.java 1143729 2011-07-07 09:36:54Z erans $
030     */
031    public class NewtonSolver extends AbstractDifferentiableUnivariateRealSolver {
032        /** Default absolute accuracy. */
033        private static final double DEFAULT_ABSOLUTE_ACCURACY = 1e-6;
034    
035        /**
036         * Construct a solver.
037         */
038        public NewtonSolver() {
039            this(DEFAULT_ABSOLUTE_ACCURACY);
040        }
041        /**
042         * Construct a solver.
043         *
044         * @param absoluteAccuracy Absolute accuracy.
045         */
046        public NewtonSolver(double absoluteAccuracy) {
047            super(absoluteAccuracy);
048        }
049    
050        /**
051         * Find a zero near the midpoint of {@code min} and {@code max}.
052         *
053         * @param f Function to solve.
054         * @param min Lower bound for the interval.
055         * @param max Upper bound for the interval.
056         * @param maxEval Maximum number of evaluations.
057         * @return the value where the function is zero.
058         * @throws org.apache.commons.math.exception.TooManyEvaluationsException
059         * if the maximum evaluation count is exceeded.
060         * @throws org.apache.commons.math.exception.NumberIsTooLargeException
061         * if {@code min >= max}.
062         */
063        @Override
064        public double solve(int maxEval, final DifferentiableUnivariateRealFunction f,
065                            final double min, final double max) {
066            return super.solve(maxEval, f, UnivariateRealSolverUtils.midpoint(min, max));
067        }
068    
069        /**
070         * {@inheritDoc}
071         */
072        @Override
073        protected double doSolve() {
074            final double startValue = getStartValue();
075            final double absoluteAccuracy = getAbsoluteAccuracy();
076    
077            double x0 = startValue;
078            double x1;
079            while (true) {
080                x1 = x0 - (computeObjectiveValue(x0) / computeDerivativeObjectiveValue(x0));
081                if (FastMath.abs(x1 - x0) <= absoluteAccuracy) {
082                    return x1;
083                }
084    
085                x0 = x1;
086            }
087        }
088    }