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.FunctionEvaluationException;
021 import org.apache.commons.math.MathRuntimeException;
022 import org.apache.commons.math.MaxIterationsExceededException;
023 import org.apache.commons.math.analysis.DifferentiableUnivariateRealFunction;
024 import org.apache.commons.math.analysis.UnivariateRealFunction;
025
026 /**
027 * Implements <a href="http://mathworld.wolfram.com/NewtonsMethod.html">
028 * Newton's Method</a> for finding zeros of real univariate functions.
029 * <p>
030 * The function should be continuous but not necessarily smooth.</p>
031 *
032 * @version $Revision: 811685 $ $Date: 2009-09-05 13:36:48 -0400 (Sat, 05 Sep 2009) $
033 */
034 public class NewtonSolver extends UnivariateRealSolverImpl {
035
036 /**
037 * Construct a solver for the given function.
038 * @param f function to solve.
039 * @deprecated as of 2.0 the function to solve is passed as an argument
040 * to the {@link #solve(UnivariateRealFunction, double, double)} or
041 * {@link UnivariateRealSolverImpl#solve(UnivariateRealFunction, double, double, double)}
042 * method.
043 */
044 @Deprecated
045 public NewtonSolver(DifferentiableUnivariateRealFunction f) {
046 super(f, 100, 1E-6);
047 }
048
049 /**
050 * Construct a solver.
051 */
052 public NewtonSolver() {
053 super(100, 1E-6);
054 }
055
056 /** {@inheritDoc} */
057 @Deprecated
058 public double solve(final double min, final double max)
059 throws MaxIterationsExceededException,
060 FunctionEvaluationException {
061 return solve(f, min, max);
062 }
063
064 /** {@inheritDoc} */
065 @Deprecated
066 public double solve(final double min, final double max, final double startValue)
067 throws MaxIterationsExceededException, FunctionEvaluationException {
068 return solve(f, min, max, startValue);
069 }
070
071 /**
072 * Find a zero near the midpoint of <code>min</code> and <code>max</code>.
073 *
074 * @param f the function to solve
075 * @param min the lower bound for the interval
076 * @param max the upper bound for the interval
077 * @return the value where the function is zero
078 * @throws MaxIterationsExceededException if the maximum iteration count is exceeded
079 * @throws FunctionEvaluationException if an error occurs evaluating the
080 * function or derivative
081 * @throws IllegalArgumentException if min is not less than max
082 */
083 public double solve(final UnivariateRealFunction f,
084 final double min, final double max)
085 throws MaxIterationsExceededException, FunctionEvaluationException {
086 return solve(f, min, max, UnivariateRealSolverUtils.midpoint(min, max));
087 }
088
089 /**
090 * Find a zero near the value <code>startValue</code>.
091 *
092 * @param f the function to solve
093 * @param min the lower bound for the interval (ignored).
094 * @param max the upper bound for the interval (ignored).
095 * @param startValue the start value to use.
096 * @return the value where the function is zero
097 * @throws MaxIterationsExceededException if the maximum iteration count is exceeded
098 * @throws FunctionEvaluationException if an error occurs evaluating the
099 * function or derivative
100 * @throws IllegalArgumentException if startValue is not between min and max or
101 * if function is not a {@link DifferentiableUnivariateRealFunction} instance
102 */
103 public double solve(final UnivariateRealFunction f,
104 final double min, final double max, final double startValue)
105 throws MaxIterationsExceededException, FunctionEvaluationException {
106
107 try {
108
109 final UnivariateRealFunction derivative =
110 ((DifferentiableUnivariateRealFunction) f).derivative();
111 clearResult();
112 verifySequence(min, startValue, max);
113
114 double x0 = startValue;
115 double x1;
116
117 int i = 0;
118 while (i < maximalIterationCount) {
119
120 x1 = x0 - (f.value(x0) / derivative.value(x0));
121 if (Math.abs(x1 - x0) <= absoluteAccuracy) {
122 setResult(x1, i);
123 return x1;
124 }
125
126 x0 = x1;
127 ++i;
128 }
129
130 throw new MaxIterationsExceededException(maximalIterationCount);
131 } catch (ClassCastException cce) {
132 throw MathRuntimeException.createIllegalArgumentException("function is not differentiable");
133 }
134 }
135
136 }