001 /* 002 * Licensed to the Apache Software Foundation (ASF) under one or more 003 * contributor license agreements. See the NOTICE file distributed with 004 * this work for additional information regarding copyright ownership. 005 * The ASF licenses this file to You under the Apache License, Version 2.0 006 * (the "License"); you may not use this file except in compliance with 007 * the License. You may obtain a copy of the License at 008 * 009 * http://www.apache.org/licenses/LICENSE-2.0 010 * 011 * Unless required by applicable law or agreed to in writing, software 012 * distributed under the License is distributed on an "AS IS" BASIS, 013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 014 * See the License for the specific language governing permissions and 015 * limitations under the License. 016 */ 017 package org.apache.commons.math.analysis.solvers; 018 019 import org.apache.commons.math.FunctionEvaluationException; 020 import org.apache.commons.math.ConvergenceException; 021 import org.apache.commons.math.MathRuntimeException; 022 import org.apache.commons.math.analysis.UnivariateRealFunction; 023 024 /** 025 * Utility routines for {@link UnivariateRealSolver} objects. 026 * 027 * @version $Revision: 885278 $ $Date: 2009-11-29 16:47:51 -0500 (Sun, 29 Nov 2009) $ 028 */ 029 public class UnivariateRealSolverUtils { 030 031 /** Message for null function.*/ 032 private static final String NULL_FUNCTION_MESSAGE = 033 "function is null"; 034 035 /** 036 * Default constructor. 037 */ 038 private UnivariateRealSolverUtils() { 039 super(); 040 } 041 042 /** 043 * Convenience method to find a zero of a univariate real function. A default 044 * solver is used. 045 * 046 * @param f the function. 047 * @param x0 the lower bound for the interval. 048 * @param x1 the upper bound for the interval. 049 * @return a value where the function is zero. 050 * @throws ConvergenceException if the iteration count was exceeded 051 * @throws FunctionEvaluationException if an error occurs evaluating 052 * the function 053 * @throws IllegalArgumentException if f is null or the endpoints do not 054 * specify a valid interval 055 */ 056 public static double solve(UnivariateRealFunction f, double x0, double x1) 057 throws ConvergenceException, FunctionEvaluationException { 058 setup(f); 059 return LazyHolder.FACTORY.newDefaultSolver().solve(f, x0, x1); 060 } 061 062 /** 063 * Convenience method to find a zero of a univariate real function. A default 064 * solver is used. 065 * 066 * @param f the function 067 * @param x0 the lower bound for the interval 068 * @param x1 the upper bound for the interval 069 * @param absoluteAccuracy the accuracy to be used by the solver 070 * @return a value where the function is zero 071 * @throws ConvergenceException if the iteration count is exceeded 072 * @throws FunctionEvaluationException if an error occurs evaluating the 073 * function 074 * @throws IllegalArgumentException if f is null, the endpoints do not 075 * specify a valid interval, or the absoluteAccuracy is not valid for the 076 * default solver 077 */ 078 public static double solve(UnivariateRealFunction f, double x0, double x1, 079 double absoluteAccuracy) throws ConvergenceException, 080 FunctionEvaluationException { 081 082 setup(f); 083 UnivariateRealSolver solver = LazyHolder.FACTORY.newDefaultSolver(); 084 solver.setAbsoluteAccuracy(absoluteAccuracy); 085 return solver.solve(f, x0, x1); 086 } 087 088 /** 089 * This method attempts to find two values a and b satisfying <ul> 090 * <li> <code> lowerBound <= a < initial < b <= upperBound</code> </li> 091 * <li> <code> f(a) * f(b) < 0 </code></li> 092 * </ul> 093 * If f is continuous on <code>[a,b],</code> this means that <code>a</code> 094 * and <code>b</code> bracket a root of f. 095 * <p> 096 * The algorithm starts by setting 097 * <code>a := initial -1; b := initial +1,</code> examines the value of the 098 * function at <code>a</code> and <code>b</code> and keeps moving 099 * the endpoints out by one unit each time through a loop that terminates 100 * when one of the following happens: <ul> 101 * <li> <code> f(a) * f(b) < 0 </code> -- success!</li> 102 * <li> <code> a = lower </code> and <code> b = upper</code> 103 * -- ConvergenceException </li> 104 * <li> <code> Integer.MAX_VALUE</code> iterations elapse 105 * -- ConvergenceException </li> 106 * </ul></p> 107 * <p> 108 * <strong>Note: </strong> this method can take 109 * <code>Integer.MAX_VALUE</code> iterations to throw a 110 * <code>ConvergenceException.</code> Unless you are confident that there 111 * is a root between <code>lowerBound</code> and <code>upperBound</code> 112 * near <code>initial,</code> it is better to use 113 * {@link #bracket(UnivariateRealFunction, double, double, double, int)}, 114 * explicitly specifying the maximum number of iterations.</p> 115 * 116 * @param function the function 117 * @param initial initial midpoint of interval being expanded to 118 * bracket a root 119 * @param lowerBound lower bound (a is never lower than this value) 120 * @param upperBound upper bound (b never is greater than this 121 * value) 122 * @return a two element array holding {a, b} 123 * @throws ConvergenceException if a root can not be bracketted 124 * @throws FunctionEvaluationException if an error occurs evaluating the 125 * function 126 * @throws IllegalArgumentException if function is null, maximumIterations 127 * is not positive, or initial is not between lowerBound and upperBound 128 */ 129 public static double[] bracket(UnivariateRealFunction function, 130 double initial, double lowerBound, double upperBound) 131 throws ConvergenceException, FunctionEvaluationException { 132 return bracket( function, initial, lowerBound, upperBound, 133 Integer.MAX_VALUE ) ; 134 } 135 136 /** 137 * This method attempts to find two values a and b satisfying <ul> 138 * <li> <code> lowerBound <= a < initial < b <= upperBound</code> </li> 139 * <li> <code> f(a) * f(b) <= 0 </code> </li> 140 * </ul> 141 * If f is continuous on <code>[a,b],</code> this means that <code>a</code> 142 * and <code>b</code> bracket a root of f. 143 * <p> 144 * The algorithm starts by setting 145 * <code>a := initial -1; b := initial +1,</code> examines the value of the 146 * function at <code>a</code> and <code>b</code> and keeps moving 147 * the endpoints out by one unit each time through a loop that terminates 148 * when one of the following happens: <ul> 149 * <li> <code> f(a) * f(b) <= 0 </code> -- success!</li> 150 * <li> <code> a = lower </code> and <code> b = upper</code> 151 * -- ConvergenceException </li> 152 * <li> <code> maximumIterations</code> iterations elapse 153 * -- ConvergenceException </li></ul></p> 154 * 155 * @param function the function 156 * @param initial initial midpoint of interval being expanded to 157 * bracket a root 158 * @param lowerBound lower bound (a is never lower than this value) 159 * @param upperBound upper bound (b never is greater than this 160 * value) 161 * @param maximumIterations maximum number of iterations to perform 162 * @return a two element array holding {a, b}. 163 * @throws ConvergenceException if the algorithm fails to find a and b 164 * satisfying the desired conditions 165 * @throws FunctionEvaluationException if an error occurs evaluating the 166 * function 167 * @throws IllegalArgumentException if function is null, maximumIterations 168 * is not positive, or initial is not between lowerBound and upperBound 169 */ 170 public static double[] bracket(UnivariateRealFunction function, 171 double initial, double lowerBound, double upperBound, 172 int maximumIterations) throws ConvergenceException, 173 FunctionEvaluationException { 174 175 if (function == null) { 176 throw MathRuntimeException.createIllegalArgumentException(NULL_FUNCTION_MESSAGE); 177 } 178 if (maximumIterations <= 0) { 179 throw MathRuntimeException.createIllegalArgumentException( 180 "bad value for maximum iterations number: {0}", maximumIterations); 181 } 182 if (initial < lowerBound || initial > upperBound || lowerBound >= upperBound) { 183 throw MathRuntimeException.createIllegalArgumentException( 184 "invalid bracketing parameters: lower bound={0}, initial={1}, upper bound={2}", 185 lowerBound, initial, upperBound); 186 } 187 double a = initial; 188 double b = initial; 189 double fa; 190 double fb; 191 int numIterations = 0 ; 192 193 do { 194 a = Math.max(a - 1.0, lowerBound); 195 b = Math.min(b + 1.0, upperBound); 196 fa = function.value(a); 197 198 fb = function.value(b); 199 numIterations++ ; 200 } while ((fa * fb > 0.0) && (numIterations < maximumIterations) && 201 ((a > lowerBound) || (b < upperBound))); 202 203 if (fa * fb > 0.0 ) { 204 throw new ConvergenceException( 205 "number of iterations={0}, maximum iterations={1}, " + 206 "initial={2}, lower bound={3}, upper bound={4}, final a value={5}, " + 207 "final b value={6}, f(a)={7}, f(b)={8}", 208 numIterations, maximumIterations, initial, 209 lowerBound, upperBound, a, b, fa, fb); 210 } 211 212 return new double[]{a, b}; 213 } 214 215 /** 216 * Compute the midpoint of two values. 217 * 218 * @param a first value. 219 * @param b second value. 220 * @return the midpoint. 221 */ 222 public static double midpoint(double a, double b) { 223 return (a + b) * .5; 224 } 225 226 /** 227 * Checks to see if f is null, throwing IllegalArgumentException if so. 228 * @param f input function 229 * @throws IllegalArgumentException if f is null 230 */ 231 private static void setup(UnivariateRealFunction f) { 232 if (f == null) { 233 throw MathRuntimeException.createIllegalArgumentException(NULL_FUNCTION_MESSAGE); 234 } 235 } 236 237 // CHECKSTYLE: stop HideUtilityClassConstructor 238 /** Holder for the factory. 239 * <p>We use here the Initialization On Demand Holder Idiom.</p> 240 */ 241 private static class LazyHolder { 242 /** Cached solver factory */ 243 private static final UnivariateRealSolverFactory FACTORY = UnivariateRealSolverFactory.newInstance(); 244 } 245 // CHECKSTYLE: resume HideUtilityClassConstructor 246 247 }