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 }