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 }