1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18 package org.apache.commons.math.analysis; 19 20 import java.io.IOException; 21 import org.apache.commons.math.FunctionEvaluationException; 22 import org.apache.commons.math.MaxIterationsExceededException; 23 24 /** 25 * Implements <a href="http://mathworld.wolfram.com/NewtonsMethod.html"> 26 * Newton's Method</a> for finding zeros of real univariate functions. 27 * <p> 28 * The function should be continuous but not necessarily smooth.</p> 29 * 30 * @version $Revision: 615734 $ $Date: 2008-01-27 23:10:03 -0700 (Sun, 27 Jan 2008) $ 31 */ 32 public class NewtonSolver extends UnivariateRealSolverImpl { 33 34 /** Serializable version identifier */ 35 private static final long serialVersionUID = 2067325783137941016L; 36 37 /** The first derivative of the target function. */ 38 private transient UnivariateRealFunction derivative; 39 40 /** 41 * Construct a solver for the given function. 42 * @param f function to solve. 43 */ 44 public NewtonSolver(DifferentiableUnivariateRealFunction f) { 45 super(f, 100, 1E-6); 46 derivative = f.derivative(); 47 } 48 49 /** 50 * Find a zero near the midpoint of <code>min</code> and <code>max</code>. 51 * 52 * @param min the lower bound for the interval 53 * @param max the upper bound for the interval 54 * @return the value where the function is zero 55 * @throws MaxIterationsExceededException if the maximum iteration count is exceeded 56 * @throws FunctionEvaluationException if an error occurs evaluating the 57 * function or derivative 58 * @throws IllegalArgumentException if min is not less than max 59 */ 60 public double solve(double min, double max) throws MaxIterationsExceededException, 61 FunctionEvaluationException { 62 return solve(min, max, UnivariateRealSolverUtils.midpoint(min, max)); 63 } 64 65 /** 66 * Find a zero near the value <code>startValue</code>. 67 * 68 * @param min the lower bound for the interval (ignored). 69 * @param max the upper bound for the interval (ignored). 70 * @param startValue the start value to use. 71 * @return the value where the function is zero 72 * @throws MaxIterationsExceededException if the maximum iteration count is exceeded 73 * @throws FunctionEvaluationException if an error occurs evaluating the 74 * function or derivative 75 * @throws IllegalArgumentException if startValue is not between min and max 76 */ 77 public double solve(double min, double max, double startValue) 78 throws MaxIterationsExceededException, FunctionEvaluationException { 79 80 clearResult(); 81 verifySequence(min, startValue, max); 82 83 double x0 = startValue; 84 double x1; 85 86 int i = 0; 87 while (i < maximalIterationCount) { 88 x1 = x0 - (f.value(x0) / derivative.value(x0)); 89 if (Math.abs(x1 - x0) <= absoluteAccuracy) { 90 91 setResult(x1, i); 92 return x1; 93 } 94 95 x0 = x1; 96 ++i; 97 } 98 99 throw new MaxIterationsExceededException(maximalIterationCount); 100 } 101 102 /** 103 * Custom deserialization to initialize transient deriviate field. 104 * 105 * @param in serialized object input stream 106 * @throws IOException if IO error occurs 107 * @throws ClassNotFoundException if instantiation error occurs 108 */ 109 private void readObject(java.io.ObjectInputStream in) 110 throws IOException, ClassNotFoundException { 111 in.defaultReadObject(); 112 derivative = ((DifferentiableUnivariateRealFunction) f).derivative(); 113 } 114 }