View Javadoc

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