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  package org.apache.commons.math.analysis.solvers;
18  
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.UnivariateRealFunction;
24  
25  /**
26   * Implements the <a href="http://mathworld.wolfram.com/BrentsMethod.html">
27   * Brent algorithm</a> for  finding zeros of real univariate functions.
28   * <p>
29   * The function should be continuous but not necessarily smooth.</p>
30   *  
31   * @version $Revision:670469 $ $Date:2008-06-23 10:01:38 +0200 (lun., 23 juin 2008) $
32   */
33  public class BrentSolver extends UnivariateRealSolverImpl {
34      
35      /** Serializable version identifier */
36      private static final long serialVersionUID = 7694577816772532779L;
37  
38      /**
39       * Construct a solver for the given function.
40       * 
41       * @param f function to solve.
42       * @deprecated as of 2.0 the function to solve is passed as an argument
43       * to the {@link #solve(UnivariateRealFunction, double, double)} or
44       * {@link UnivariateRealSolverImpl#solve(UnivariateRealFunction, double, double, double)}
45       * method.
46       */
47      @Deprecated
48      public BrentSolver(UnivariateRealFunction f) {
49          super(f, 100, 1E-6);
50      }
51  
52      /**
53       * Construct a solver.
54       */
55      public BrentSolver() {
56          super(100, 1E-6);
57      }
58  
59      /** {@inheritDoc} */
60      @Deprecated
61      public double solve(double min, double max)
62          throws MaxIterationsExceededException, FunctionEvaluationException {
63          return solve(f, min, max);
64      }
65  
66      /** {@inheritDoc} */
67      @Deprecated
68      public double solve(double min, double max, double initial)
69          throws MaxIterationsExceededException, FunctionEvaluationException {
70          return solve(f, min, max, initial);
71      }
72  
73      /**
74       * Find a zero in the given interval with an initial guess.
75       * <p>Throws <code>IllegalArgumentException</code> if the values of the
76       * function at the three points have the same sign (note that it is
77       * allowed to have endpoints with the same sign if the initial point has
78       * opposite sign function-wise).</p>
79       * 
80       * @param f function to solve.
81       * @param min the lower bound for the interval.
82       * @param max the upper bound for the interval.
83       * @param initial the start value to use (must be set to min if no
84       * initial point is known).
85       * @return the value where the function is zero
86       * @throws MaxIterationsExceededException the maximum iteration count
87       * is exceeded 
88       * @throws FunctionEvaluationException if an error occurs evaluating
89       *  the function
90       * @throws IllegalArgumentException if initial is not between min and max
91       * (even if it <em>is</em> a root)
92       */
93      public double solve(final UnivariateRealFunction f,
94                          final double min, final double max, final double initial)
95          throws MaxIterationsExceededException, FunctionEvaluationException {
96  
97          clearResult();
98          verifySequence(min, initial, max);
99  
100         // return the initial guess if it is good enough
101         double yInitial = f.value(initial);
102         if (Math.abs(yInitial) <= functionValueAccuracy) {
103             setResult(initial, 0);
104             return result;
105         }
106 
107         // return the first endpoint if it is good enough
108         double yMin = f.value(min);
109         if (Math.abs(yMin) <= functionValueAccuracy) {
110             setResult(yMin, 0);
111             return result;
112         }
113 
114         // reduce interval if min and initial bracket the root
115         if (yInitial * yMin < 0) {
116             return solve(f, min, yMin, initial, yInitial, min, yMin);
117         }
118 
119         // return the second endpoint if it is good enough
120         double yMax = f.value(max);
121         if (Math.abs(yMax) <= functionValueAccuracy) {
122             setResult(yMax, 0);
123             return result;
124         }
125 
126         // reduce interval if initial and max bracket the root
127         if (yInitial * yMax < 0) {
128             return solve(f, initial, yInitial, max, yMax, initial, yInitial);
129         }
130 
131         // full Brent algorithm starting with provided initial guess
132         return solve(f, min, yMin, max, yMax, initial, yInitial);
133 
134     }
135     
136     /**
137      * Find a zero in the given interval.
138      * <p>
139      * Requires that the values of the function at the endpoints have opposite
140      * signs. An <code>IllegalArgumentException</code> is thrown if this is not
141      * the case.</p>
142      * 
143      * @param f the function to solve
144      * @param min the lower bound for the interval.
145      * @param max the upper bound for the interval.
146      * @return the value where the function is zero
147      * @throws MaxIterationsExceededException if the maximum iteration count is exceeded
148      * @throws FunctionEvaluationException if an error occurs evaluating the
149      * function 
150      * @throws IllegalArgumentException if min is not less than max or the
151      * signs of the values of the function at the endpoints are not opposites
152      */
153     public double solve(final UnivariateRealFunction f,
154                         final double min, final double max)
155         throws MaxIterationsExceededException, 
156         FunctionEvaluationException {
157         
158         clearResult();
159         verifyInterval(min, max);
160         
161         double ret = Double.NaN;
162         
163         double yMin = f.value(min);
164         double yMax = f.value(max);
165         
166         // Verify bracketing
167         double sign = yMin * yMax;
168         if (sign > 0) {
169             // check if either value is close to a zero
170             if (Math.abs(yMin) <= functionValueAccuracy) {
171                 setResult(min, 0);
172                 ret = min;
173             } else if (Math.abs(yMax) <= functionValueAccuracy) {
174                 setResult(max, 0);
175                 ret = max;
176             } else {
177                 // neither value is close to zero and min and max do not bracket root.
178                 throw MathRuntimeException.createIllegalArgumentException(
179                         "function values at endpoints do not have different signs.  " +
180                         "Endpoints: [{0}, {1}], Values: [{2}, {3}]",
181                         min, max, yMin, yMax);       
182             }
183         } else if (sign < 0){
184             // solve using only the first endpoint as initial guess
185             ret = solve(f, min, yMin, max, yMax, min, yMin);
186         } else {
187             // either min or max is a root
188             if (yMin == 0.0) {
189                 ret = min;
190             } else {
191                 ret = max;
192             }
193         }
194 
195         return ret;
196     }
197         
198     /**
199      * Find a zero starting search according to the three provided points.
200      * @param f the function to solve
201      * @param x0 old approximation for the root
202      * @param y0 function value at the approximation for the root
203      * @param x1 last calculated approximation for the root
204      * @param y1 function value at the last calculated approximation
205      * for the root
206      * @param x2 bracket point (must be set to x0 if no bracket point is
207      * known, this will force starting with linear interpolation)
208      * @param y2 function value at the bracket point.
209      * @return the value where the function is zero
210      * @throws MaxIterationsExceededException if the maximum iteration count
211      * is exceeded
212      * @throws FunctionEvaluationException if an error occurs evaluating
213      * the function 
214      */
215     private double solve(final UnivariateRealFunction f,
216                          double x0, double y0,
217                          double x1, double y1,
218                          double x2, double y2)
219     throws MaxIterationsExceededException, FunctionEvaluationException {
220 
221         double delta = x1 - x0;
222         double oldDelta = delta;
223 
224         int i = 0;
225         while (i < maximalIterationCount) {
226             if (Math.abs(y2) < Math.abs(y1)) {
227                 // use the bracket point if is better than last approximation
228                 x0 = x1;
229                 x1 = x2;
230                 x2 = x0;
231                 y0 = y1;
232                 y1 = y2;
233                 y2 = y0;
234             }
235             if (Math.abs(y1) <= functionValueAccuracy) {
236                 // Avoid division by very small values. Assume
237                 // the iteration has converged (the problem may
238                 // still be ill conditioned)
239                 setResult(x1, i);
240                 return result;
241             }
242             double dx = (x2 - x1);
243             double tolerance =
244                 Math.max(relativeAccuracy * Math.abs(x1), absoluteAccuracy);
245             if (Math.abs(dx) <= tolerance) {
246                 setResult(x1, i);
247                 return result;
248             }
249             if ((Math.abs(oldDelta) < tolerance) ||
250                     (Math.abs(y0) <= Math.abs(y1))) {
251                 // Force bisection.
252                 delta = 0.5 * dx;
253                 oldDelta = delta;
254             } else {
255                 double r3 = y1 / y0;
256                 double p;
257                 double p1;
258                 // the equality test (x0 == x2) is intentional,
259                 // it is part of the original Brent's method,
260                 // it should NOT be replaced by proximity test
261                 if (x0 == x2) {
262                     // Linear interpolation.
263                     p = dx * r3;
264                     p1 = 1.0 - r3;
265                 } else {
266                     // Inverse quadratic interpolation.
267                     double r1 = y0 / y2;
268                     double r2 = y1 / y2;
269                     p = r3 * (dx * r1 * (r1 - r2) - (x1 - x0) * (r2 - 1.0));
270                     p1 = (r1 - 1.0) * (r2 - 1.0) * (r3 - 1.0);
271                 }
272                 if (p > 0.0) {
273                     p1 = -p1;
274                 } else {
275                     p = -p;
276                 }
277                 if (2.0 * p >= 1.5 * dx * p1 - Math.abs(tolerance * p1) ||
278                         p >= Math.abs(0.5 * oldDelta * p1)) {
279                     // Inverse quadratic interpolation gives a value
280                     // in the wrong direction, or progress is slow.
281                     // Fall back to bisection.
282                     delta = 0.5 * dx;
283                     oldDelta = delta;
284                 } else {
285                     oldDelta = delta;
286                     delta = p / p1;
287                 }
288             }
289             // Save old X1, Y1 
290             x0 = x1;
291             y0 = y1;
292             // Compute new X1, Y1
293             if (Math.abs(delta) > tolerance) {
294                 x1 = x1 + delta;
295             } else if (dx > 0.0) {
296                 x1 = x1 + 0.5 * tolerance;
297             } else if (dx <= 0.0) {
298                 x1 = x1 - 0.5 * tolerance;
299             }
300             y1 = f.value(x1);
301             if ((y1 > 0) == (y2 > 0)) {
302                 x2 = x0;
303                 y2 = y0;
304                 delta = x1 - x0;
305                 oldDelta = delta;
306             }
307             i++;
308         }
309         throw new MaxIterationsExceededException(maximalIterationCount);
310     }
311 }