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 import org.apache.commons.math.exception.util.LocalizedFormats; 026 import org.apache.commons.math.util.FastMath; 027 028 /** 029 * Implements <a href="http://mathworld.wolfram.com/NewtonsMethod.html"> 030 * Newton's Method</a> for finding zeros of real univariate functions. 031 * <p> 032 * The function should be continuous but not necessarily smooth.</p> 033 * 034 * @version $Revision: 1070725 $ $Date: 2011-02-15 02:31:12 +0100 (mar. 15 f??vr. 2011) $ 035 */ 036 public class NewtonSolver extends UnivariateRealSolverImpl { 037 038 /** 039 * Construct a solver for the given function. 040 * @param f function to solve. 041 * @deprecated as of 2.0 the function to solve is passed as an argument 042 * to the {@link #solve(UnivariateRealFunction, double, double)} or 043 * {@link UnivariateRealSolverImpl#solve(UnivariateRealFunction, double, double, double)} 044 * method. 045 */ 046 @Deprecated 047 public NewtonSolver(DifferentiableUnivariateRealFunction f) { 048 super(f, 100, 1E-6); 049 } 050 051 /** 052 * Construct a solver. 053 * @deprecated in 2.2 (to be removed in 3.0). 054 */ 055 @Deprecated 056 public NewtonSolver() { 057 super(100, 1E-6); 058 } 059 060 /** {@inheritDoc} */ 061 @Deprecated 062 public double solve(final double min, final double max) 063 throws MaxIterationsExceededException, FunctionEvaluationException { 064 return solve(f, min, max); 065 } 066 067 /** {@inheritDoc} */ 068 @Deprecated 069 public double solve(final double min, final double max, final double startValue) 070 throws MaxIterationsExceededException, FunctionEvaluationException { 071 return solve(f, min, max, startValue); 072 } 073 074 /** 075 * Find a zero near the midpoint of <code>min</code> and <code>max</code>. 076 * 077 * @param f the function to solve 078 * @param min the lower bound for the interval 079 * @param max the upper bound for the interval 080 * @param maxEval Maximum number of evaluations. 081 * @return the value where the function is zero 082 * @throws MaxIterationsExceededException if the maximum iteration count is exceeded 083 * @throws FunctionEvaluationException if an error occurs evaluating the function or derivative 084 * @throws IllegalArgumentException if min is not less than max 085 */ 086 @Override 087 public double solve(int maxEval, final UnivariateRealFunction f, 088 final double min, final double max) 089 throws MaxIterationsExceededException, FunctionEvaluationException { 090 setMaximalIterationCount(maxEval); 091 return solve(f, min, max); 092 } 093 094 /** 095 * Find a zero near the midpoint of <code>min</code> and <code>max</code>. 096 * 097 * @param f the function to solve 098 * @param min the lower bound for the interval 099 * @param max the upper bound for the interval 100 * @return the value where the function is zero 101 * @throws MaxIterationsExceededException if the maximum iteration count is exceeded 102 * @throws FunctionEvaluationException if an error occurs evaluating the function or derivative 103 * @throws IllegalArgumentException if min is not less than max 104 * @deprecated in 2.2 (to be removed in 3.0). 105 */ 106 @Deprecated 107 public double solve(final UnivariateRealFunction f, 108 final double min, final double max) 109 throws MaxIterationsExceededException, FunctionEvaluationException { 110 return solve(f, min, max, UnivariateRealSolverUtils.midpoint(min, max)); 111 } 112 113 /** 114 * Find a zero near the value <code>startValue</code>. 115 * 116 * @param f the function to solve 117 * @param min the lower bound for the interval (ignored). 118 * @param max the upper bound for the interval (ignored). 119 * @param startValue the start value to use. 120 * @param maxEval Maximum number of evaluations. 121 * @return the value where the function is zero 122 * @throws MaxIterationsExceededException if the maximum iteration count is exceeded 123 * @throws FunctionEvaluationException if an error occurs evaluating the function or derivative 124 * @throws IllegalArgumentException if startValue is not between min and max or 125 * if function is not a {@link DifferentiableUnivariateRealFunction} instance 126 */ 127 @Override 128 public double solve(int maxEval, final UnivariateRealFunction f, 129 final double min, final double max, final double startValue) 130 throws MaxIterationsExceededException, FunctionEvaluationException { 131 setMaximalIterationCount(maxEval); 132 return solve(f, min, max, startValue); 133 } 134 135 /** 136 * Find a zero near the value <code>startValue</code>. 137 * 138 * @param f the function to solve 139 * @param min the lower bound for the interval (ignored). 140 * @param max the upper bound for the interval (ignored). 141 * @param startValue the start value to use. 142 * @return the value where the function is zero 143 * @throws MaxIterationsExceededException if the maximum iteration count is exceeded 144 * @throws FunctionEvaluationException if an error occurs evaluating the function or derivative 145 * @throws IllegalArgumentException if startValue is not between min and max or 146 * if function is not a {@link DifferentiableUnivariateRealFunction} instance 147 * @deprecated in 2.2 (to be removed in 3.0). 148 */ 149 @Deprecated 150 public double solve(final UnivariateRealFunction f, 151 final double min, final double max, final double startValue) 152 throws MaxIterationsExceededException, FunctionEvaluationException { 153 154 try { 155 156 final UnivariateRealFunction derivative = 157 ((DifferentiableUnivariateRealFunction) f).derivative(); 158 clearResult(); 159 verifySequence(min, startValue, max); 160 161 double x0 = startValue; 162 double x1; 163 164 int i = 0; 165 while (i < maximalIterationCount) { 166 167 x1 = x0 - (f.value(x0) / derivative.value(x0)); 168 if (FastMath.abs(x1 - x0) <= absoluteAccuracy) { 169 setResult(x1, i); 170 return x1; 171 } 172 173 x0 = x1; 174 ++i; 175 } 176 177 throw new MaxIterationsExceededException(maximalIterationCount); 178 } catch (ClassCastException cce) { 179 throw MathRuntimeException.createIllegalArgumentException(LocalizedFormats.FUNCTION_NOT_DIFFERENTIABLE); 180 } 181 } 182 183 }