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 java.io.IOException;
20  import org.apache.commons.math.ConvergenceException;
21  import org.apache.commons.math.FunctionEvaluationException; 
22  
23  /**
24   * Implements <a href="http://mathworld.wolfram.com/NewtonsMethod.html">
25   * Newton's Method</a> for finding zeros of real univariate functions. 
26   * <p> 
27   * The function should be continuous but not necessarily smooth.
28   *
29   * @version $Revision: 348791 $ $Date: 2005-11-24 12:50:36 -0700 (Thu, 24 Nov 2005) $
30   */
31  public class NewtonSolver extends UnivariateRealSolverImpl {
32      
33      /** Serializable version identifier */
34      private static final long serialVersionUID = 2606474895443431607L;
35      
36      /** The first derivative of the target function. */
37      private transient UnivariateRealFunction derivative;
38      
39      /**
40       * Construct a solver for the given function.
41       * @param f function to solve.
42       */
43      public NewtonSolver(DifferentiableUnivariateRealFunction f) {
44          super(f, 100, 1E-6);
45          derivative = f.derivative();
46      }
47  
48      /**
49       * Find a zero near the midpoint of <code>min</code> and <code>max</code>.
50       * 
51       * @param min the lower bound for the interval
52       * @param max the upper bound for the interval
53       * @return the value where the function is zero
54       * @throws ConvergenceException if the maximum iteration count is exceeded 
55       * @throws FunctionEvaluationException if an error occurs evaluating the
56       * function or derivative
57       * @throws IllegalArgumentException if min is not less than max
58       */
59      public double solve(double min, double max) throws ConvergenceException, 
60          FunctionEvaluationException  {
61          return solve(min, max, UnivariateRealSolverUtils.midpoint(min, max));
62      }
63  
64      /**
65       * Find a zero near the value <code>startValue</code>.
66       * 
67       * @param min the lower bound for the interval (ignored).
68       * @param max the upper bound for the interval (ignored).
69       * @param startValue the start value to use.
70       * @return the value where the function is zero
71      * @throws ConvergenceException if the maximum iteration count is exceeded 
72       * @throws FunctionEvaluationException if an error occurs evaluating the
73       * function or derivative
74       * @throws IllegalArgumentException if startValue is not between min and max
75       */
76      public double solve(double min, double max, double startValue)
77          throws ConvergenceException, FunctionEvaluationException {
78          
79          clearResult();
80          verifySequence(min, startValue, max);
81  
82          double x0 = startValue;
83          double x1;
84          
85          int i = 0;
86          while (i < maximalIterationCount) {
87              x1 = x0 - (f.value(x0) / derivative.value(x0));
88              if (Math.abs(x1 - x0) <= absoluteAccuracy) {
89                  
90                  setResult(x1, i);
91                  return x1;
92              }
93              
94              x0 = x1;
95              ++i;
96          }
97          
98          throw new ConvergenceException
99              ("Maximum number of iterations exceeded " + i);
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 }