View Javadoc

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.solvers;
19  
20  import org.apache.commons.math.FunctionEvaluationException;
21  import org.apache.commons.math.MathRuntimeException;
22  import org.apache.commons.math.MaxIterationsExceededException;
23  import org.apache.commons.math.analysis.DifferentiableUnivariateRealFunction;
24  import org.apache.commons.math.analysis.UnivariateRealFunction;
25  
26  /**
27   * Implements <a href="http://mathworld.wolfram.com/NewtonsMethod.html">
28   * Newton's Method</a> for finding zeros of real univariate functions. 
29   * <p> 
30   * The function should be continuous but not necessarily smooth.</p>
31   *
32   * @version $Revision: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $
33   */
34  public class NewtonSolver extends UnivariateRealSolverImpl {
35      
36      /**
37       * Construct a solver for the given function.
38       * @param f function to solve.
39       * @deprecated as of 2.0 the function to solve is passed as an argument
40       * to the {@link #solve(UnivariateRealFunction, double, double)} or
41       * {@link UnivariateRealSolverImpl#solve(UnivariateRealFunction, double, double, double)}
42       * method.
43       */
44      @Deprecated
45      public NewtonSolver(DifferentiableUnivariateRealFunction f) {
46          super(f, 100, 1E-6);
47      }
48  
49      /**
50       * Construct a solver.
51       */
52      public NewtonSolver() {
53          super(100, 1E-6);
54      }
55  
56      /** {@inheritDoc} */
57      @Deprecated
58      public double solve(final double min, final double max)
59          throws MaxIterationsExceededException, 
60          FunctionEvaluationException  {
61          return solve(f, min, max);
62      }
63  
64      /** {@inheritDoc} */
65      @Deprecated
66      public double solve(final double min, final double max, final double startValue)
67          throws MaxIterationsExceededException, FunctionEvaluationException  {
68          return solve(f, min, max, startValue);
69      }
70  
71      /**
72       * Find a zero near the midpoint of <code>min</code> and <code>max</code>.
73       * 
74       * @param f the function to solve
75       * @param min the lower bound for the interval
76       * @param max the upper bound for the interval
77       * @return the value where the function is zero
78       * @throws MaxIterationsExceededException if the maximum iteration count is exceeded 
79       * @throws FunctionEvaluationException if an error occurs evaluating the
80       * function or derivative
81       * @throws IllegalArgumentException if min is not less than max
82       */
83      public double solve(final UnivariateRealFunction f,
84                          final double min, final double max)
85          throws MaxIterationsExceededException, FunctionEvaluationException  {
86          return solve(f, min, max, UnivariateRealSolverUtils.midpoint(min, max));
87      }
88  
89      /**
90       * Find a zero near the value <code>startValue</code>.
91       * 
92       * @param f the function to solve
93       * @param min the lower bound for the interval (ignored).
94       * @param max the upper bound for the interval (ignored).
95       * @param startValue the start value to use.
96       * @return the value where the function is zero
97       * @throws MaxIterationsExceededException if the maximum iteration count is exceeded 
98       * @throws FunctionEvaluationException if an error occurs evaluating the
99       * function or derivative
100      * @throws IllegalArgumentException if startValue is not between min and max or
101      * if function is not a {@link DifferentiableUnivariateRealFunction} instance
102      */
103     public double solve(final UnivariateRealFunction f,
104                         final double min, final double max, final double startValue)
105         throws MaxIterationsExceededException, FunctionEvaluationException {
106 
107         try {
108 
109             final UnivariateRealFunction derivative =
110                 ((DifferentiableUnivariateRealFunction) f).derivative();
111             clearResult();
112             verifySequence(min, startValue, max);
113 
114             double x0 = startValue;
115             double x1;
116 
117             int i = 0;
118             while (i < maximalIterationCount) {
119 
120                 x1 = x0 - (f.value(x0) / derivative.value(x0));
121                 if (Math.abs(x1 - x0) <= absoluteAccuracy) {
122                     setResult(x1, i);
123                     return x1;
124                 }
125 
126                 x0 = x1;
127                 ++i;
128             }
129 
130             throw new MaxIterationsExceededException(maximalIterationCount);
131         } catch (ClassCastException cce) {
132             throw MathRuntimeException.createIllegalArgumentException("function is not differentiable");
133         }
134     }
135     
136 }