Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/scipy/optimize/_root_scalar.py: 15%
123 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-12-12 06:31 +0000
1"""
2Unified interfaces to root finding algorithms for real or complex
3scalar functions.
5Functions
6---------
7- root : find a root of a scalar function.
8"""
9import numpy as np
11from . import _zeros_py as optzeros
13__all__ = ['root_scalar']
15ROOT_SCALAR_METHODS = ['bisect', 'brentq', 'brenth', 'ridder', 'toms748',
16 'newton', 'secant', 'halley']
19class MemoizeDer:
20 """Decorator that caches the value and derivative(s) of function each
21 time it is called.
23 This is a simplistic memoizer that calls and caches a single value
24 of `f(x, *args)`.
25 It assumes that `args` does not change between invocations.
26 It supports the use case of a root-finder where `args` is fixed,
27 `x` changes, and only rarely, if at all, does x assume the same value
28 more than once."""
29 def __init__(self, fun):
30 self.fun = fun
31 self.vals = None
32 self.x = None
33 self.n_calls = 0
35 def __call__(self, x, *args):
36 r"""Calculate f or use cached value if available"""
37 # Derivative may be requested before the function itself, always check
38 if self.vals is None or x != self.x:
39 fg = self.fun(x, *args)
40 self.x = x
41 self.n_calls += 1
42 self.vals = fg[:]
43 return self.vals[0]
45 def fprime(self, x, *args):
46 r"""Calculate f' or use a cached value if available"""
47 if self.vals is None or x != self.x:
48 self(x, *args)
49 return self.vals[1]
51 def fprime2(self, x, *args):
52 r"""Calculate f'' or use a cached value if available"""
53 if self.vals is None or x != self.x:
54 self(x, *args)
55 return self.vals[2]
57 def ncalls(self):
58 return self.n_calls
61def root_scalar(f, args=(), method=None, bracket=None,
62 fprime=None, fprime2=None,
63 x0=None, x1=None,
64 xtol=None, rtol=None, maxiter=None,
65 options=None):
66 """
67 Find a root of a scalar function.
69 Parameters
70 ----------
71 f : callable
72 A function to find a root of.
73 args : tuple, optional
74 Extra arguments passed to the objective function and its derivative(s).
75 method : str, optional
76 Type of solver. Should be one of
78 - 'bisect' :ref:`(see here) <optimize.root_scalar-bisect>`
79 - 'brentq' :ref:`(see here) <optimize.root_scalar-brentq>`
80 - 'brenth' :ref:`(see here) <optimize.root_scalar-brenth>`
81 - 'ridder' :ref:`(see here) <optimize.root_scalar-ridder>`
82 - 'toms748' :ref:`(see here) <optimize.root_scalar-toms748>`
83 - 'newton' :ref:`(see here) <optimize.root_scalar-newton>`
84 - 'secant' :ref:`(see here) <optimize.root_scalar-secant>`
85 - 'halley' :ref:`(see here) <optimize.root_scalar-halley>`
87 bracket: A sequence of 2 floats, optional
88 An interval bracketing a root. `f(x, *args)` must have different
89 signs at the two endpoints.
90 x0 : float, optional
91 Initial guess.
92 x1 : float, optional
93 A second guess.
94 fprime : bool or callable, optional
95 If `fprime` is a boolean and is True, `f` is assumed to return the
96 value of the objective function and of the derivative.
97 `fprime` can also be a callable returning the derivative of `f`. In
98 this case, it must accept the same arguments as `f`.
99 fprime2 : bool or callable, optional
100 If `fprime2` is a boolean and is True, `f` is assumed to return the
101 value of the objective function and of the
102 first and second derivatives.
103 `fprime2` can also be a callable returning the second derivative of `f`.
104 In this case, it must accept the same arguments as `f`.
105 xtol : float, optional
106 Tolerance (absolute) for termination.
107 rtol : float, optional
108 Tolerance (relative) for termination.
109 maxiter : int, optional
110 Maximum number of iterations.
111 options : dict, optional
112 A dictionary of solver options. E.g., ``k``, see
113 :obj:`show_options()` for details.
115 Returns
116 -------
117 sol : RootResults
118 The solution represented as a ``RootResults`` object.
119 Important attributes are: ``root`` the solution , ``converged`` a
120 boolean flag indicating if the algorithm exited successfully and
121 ``flag`` which describes the cause of the termination. See
122 `RootResults` for a description of other attributes.
124 See also
125 --------
126 show_options : Additional options accepted by the solvers
127 root : Find a root of a vector function.
129 Notes
130 -----
131 This section describes the available solvers that can be selected by the
132 'method' parameter.
134 The default is to use the best method available for the situation
135 presented.
136 If a bracket is provided, it may use one of the bracketing methods.
137 If a derivative and an initial value are specified, it may
138 select one of the derivative-based methods.
139 If no method is judged applicable, it will raise an Exception.
141 Arguments for each method are as follows (x=required, o=optional).
143 +-----------------------------------------------+---+------+---------+----+----+--------+---------+------+------+---------+---------+
144 | method | f | args | bracket | x0 | x1 | fprime | fprime2 | xtol | rtol | maxiter | options |
145 +===============================================+===+======+=========+====+====+========+=========+======+======+=========+=========+
146 | :ref:`bisect <optimize.root_scalar-bisect>` | x | o | x | | | | | o | o | o | o |
147 +-----------------------------------------------+---+------+---------+----+----+--------+---------+------+------+---------+---------+
148 | :ref:`brentq <optimize.root_scalar-brentq>` | x | o | x | | | | | o | o | o | o |
149 +-----------------------------------------------+---+------+---------+----+----+--------+---------+------+------+---------+---------+
150 | :ref:`brenth <optimize.root_scalar-brenth>` | x | o | x | | | | | o | o | o | o |
151 +-----------------------------------------------+---+------+---------+----+----+--------+---------+------+------+---------+---------+
152 | :ref:`ridder <optimize.root_scalar-ridder>` | x | o | x | | | | | o | o | o | o |
153 +-----------------------------------------------+---+------+---------+----+----+--------+---------+------+------+---------+---------+
154 | :ref:`toms748 <optimize.root_scalar-toms748>` | x | o | x | | | | | o | o | o | o |
155 +-----------------------------------------------+---+------+---------+----+----+--------+---------+------+------+---------+---------+
156 | :ref:`newton <optimize.root_scalar-newton>` | x | o | | x | | x | | o | o | o | o |
157 +-----------------------------------------------+---+------+---------+----+----+--------+---------+------+------+---------+---------+
158 | :ref:`secant <optimize.root_scalar-secant>` | x | o | | x | x | | | o | o | o | o |
159 +-----------------------------------------------+---+------+---------+----+----+--------+---------+------+------+---------+---------+
160 | :ref:`halley <optimize.root_scalar-halley>` | x | o | | x | | x | x | o | o | o | o |
161 +-----------------------------------------------+---+------+---------+----+----+--------+---------+------+------+---------+---------+
163 Examples
164 --------
166 Find the root of a simple cubic
168 >>> from scipy import optimize
169 >>> def f(x):
170 ... return (x**3 - 1) # only one real root at x = 1
172 >>> def fprime(x):
173 ... return 3*x**2
175 The `brentq` method takes as input a bracket
177 >>> sol = optimize.root_scalar(f, bracket=[0, 3], method='brentq')
178 >>> sol.root, sol.iterations, sol.function_calls
179 (1.0, 10, 11)
181 The `newton` method takes as input a single point and uses the
182 derivative(s).
184 >>> sol = optimize.root_scalar(f, x0=0.2, fprime=fprime, method='newton')
185 >>> sol.root, sol.iterations, sol.function_calls
186 (1.0, 11, 22)
188 The function can provide the value and derivative(s) in a single call.
190 >>> def f_p_pp(x):
191 ... return (x**3 - 1), 3*x**2, 6*x
193 >>> sol = optimize.root_scalar(
194 ... f_p_pp, x0=0.2, fprime=True, method='newton'
195 ... )
196 >>> sol.root, sol.iterations, sol.function_calls
197 (1.0, 11, 11)
199 >>> sol = optimize.root_scalar(
200 ... f_p_pp, x0=0.2, fprime=True, fprime2=True, method='halley'
201 ... )
202 >>> sol.root, sol.iterations, sol.function_calls
203 (1.0, 7, 8)
206 """
207 if not isinstance(args, tuple):
208 args = (args,)
210 if options is None:
211 options = {}
213 # fun also returns the derivative(s)
214 is_memoized = False
215 if fprime2 is not None and not callable(fprime2):
216 if bool(fprime2):
217 f = MemoizeDer(f)
218 is_memoized = True
219 fprime2 = f.fprime2
220 fprime = f.fprime
221 else:
222 fprime2 = None
223 if fprime is not None and not callable(fprime):
224 if bool(fprime):
225 f = MemoizeDer(f)
226 is_memoized = True
227 fprime = f.fprime
228 else:
229 fprime = None
231 # respect solver-specific default tolerances - only pass in if actually set
232 kwargs = {}
233 for k in ['xtol', 'rtol', 'maxiter']:
234 v = locals().get(k)
235 if v is not None:
236 kwargs[k] = v
238 # Set any solver-specific options
239 if options:
240 kwargs.update(options)
241 # Always request full_output from the underlying method as _root_scalar
242 # always returns a RootResults object
243 kwargs.update(full_output=True, disp=False)
245 # Pick a method if not specified.
246 # Use the "best" method available for the situation.
247 if not method:
248 if bracket:
249 method = 'brentq'
250 elif x0 is not None:
251 if fprime:
252 if fprime2:
253 method = 'halley'
254 else:
255 method = 'newton'
256 else:
257 method = 'secant'
258 if not method:
259 raise ValueError('Unable to select a solver as neither bracket '
260 'nor starting point provided.')
262 meth = method.lower()
263 map2underlying = {'halley': 'newton', 'secant': 'newton'}
265 try:
266 methodc = getattr(optzeros, map2underlying.get(meth, meth))
267 except AttributeError as e:
268 raise ValueError('Unknown solver %s' % meth) from e
270 if meth in ['bisect', 'ridder', 'brentq', 'brenth', 'toms748']:
271 if not isinstance(bracket, (list, tuple, np.ndarray)):
272 raise ValueError('Bracket needed for %s' % method)
274 a, b = bracket[:2]
275 r, sol = methodc(f, a, b, args=args, **kwargs)
276 elif meth in ['secant']:
277 if x0 is None:
278 raise ValueError('x0 must not be None for %s' % method)
279 if x1 is None:
280 raise ValueError('x1 must not be None for %s' % method)
281 if 'xtol' in kwargs:
282 kwargs['tol'] = kwargs.pop('xtol')
283 r, sol = methodc(f, x0, args=args, fprime=None, fprime2=None,
284 x1=x1, **kwargs)
285 elif meth in ['newton']:
286 if x0 is None:
287 raise ValueError('x0 must not be None for %s' % method)
288 if not fprime:
289 raise ValueError('fprime must be specified for %s' % method)
290 if 'xtol' in kwargs:
291 kwargs['tol'] = kwargs.pop('xtol')
292 r, sol = methodc(f, x0, args=args, fprime=fprime, fprime2=None,
293 **kwargs)
294 elif meth in ['halley']:
295 if x0 is None:
296 raise ValueError('x0 must not be None for %s' % method)
297 if not fprime:
298 raise ValueError('fprime must be specified for %s' % method)
299 if not fprime2:
300 raise ValueError('fprime2 must be specified for %s' % method)
301 if 'xtol' in kwargs:
302 kwargs['tol'] = kwargs.pop('xtol')
303 r, sol = methodc(f, x0, args=args, fprime=fprime, fprime2=fprime2, **kwargs)
304 else:
305 raise ValueError('Unknown solver %s' % method)
307 if is_memoized:
308 # Replace the function_calls count with the memoized count.
309 # Avoids double and triple-counting.
310 n_calls = f.n_calls
311 sol.function_calls = n_calls
313 return sol
316def _root_scalar_brentq_doc():
317 r"""
318 Options
319 -------
320 args : tuple, optional
321 Extra arguments passed to the objective function.
322 bracket: A sequence of 2 floats, optional
323 An interval bracketing a root. `f(x, *args)` must have different
324 signs at the two endpoints.
325 xtol : float, optional
326 Tolerance (absolute) for termination.
327 rtol : float, optional
328 Tolerance (relative) for termination.
329 maxiter : int, optional
330 Maximum number of iterations.
331 options: dict, optional
332 Specifies any method-specific options not covered above
334 """
335 pass
338def _root_scalar_brenth_doc():
339 r"""
340 Options
341 -------
342 args : tuple, optional
343 Extra arguments passed to the objective function.
344 bracket: A sequence of 2 floats, optional
345 An interval bracketing a root. `f(x, *args)` must have different
346 signs at the two endpoints.
347 xtol : float, optional
348 Tolerance (absolute) for termination.
349 rtol : float, optional
350 Tolerance (relative) for termination.
351 maxiter : int, optional
352 Maximum number of iterations.
353 options: dict, optional
354 Specifies any method-specific options not covered above.
356 """
357 pass
359def _root_scalar_toms748_doc():
360 r"""
361 Options
362 -------
363 args : tuple, optional
364 Extra arguments passed to the objective function.
365 bracket: A sequence of 2 floats, optional
366 An interval bracketing a root. `f(x, *args)` must have different
367 signs at the two endpoints.
368 xtol : float, optional
369 Tolerance (absolute) for termination.
370 rtol : float, optional
371 Tolerance (relative) for termination.
372 maxiter : int, optional
373 Maximum number of iterations.
374 options: dict, optional
375 Specifies any method-specific options not covered above.
377 """
378 pass
381def _root_scalar_secant_doc():
382 r"""
383 Options
384 -------
385 args : tuple, optional
386 Extra arguments passed to the objective function.
387 xtol : float, optional
388 Tolerance (absolute) for termination.
389 rtol : float, optional
390 Tolerance (relative) for termination.
391 maxiter : int, optional
392 Maximum number of iterations.
393 x0 : float, required
394 Initial guess.
395 x1 : float, required
396 A second guess.
397 options: dict, optional
398 Specifies any method-specific options not covered above.
400 """
401 pass
404def _root_scalar_newton_doc():
405 r"""
406 Options
407 -------
408 args : tuple, optional
409 Extra arguments passed to the objective function and its derivative.
410 xtol : float, optional
411 Tolerance (absolute) for termination.
412 rtol : float, optional
413 Tolerance (relative) for termination.
414 maxiter : int, optional
415 Maximum number of iterations.
416 x0 : float, required
417 Initial guess.
418 fprime : bool or callable, optional
419 If `fprime` is a boolean and is True, `f` is assumed to return the
420 value of derivative along with the objective function.
421 `fprime` can also be a callable returning the derivative of `f`. In
422 this case, it must accept the same arguments as `f`.
423 options: dict, optional
424 Specifies any method-specific options not covered above.
426 """
427 pass
430def _root_scalar_halley_doc():
431 r"""
432 Options
433 -------
434 args : tuple, optional
435 Extra arguments passed to the objective function and its derivatives.
436 xtol : float, optional
437 Tolerance (absolute) for termination.
438 rtol : float, optional
439 Tolerance (relative) for termination.
440 maxiter : int, optional
441 Maximum number of iterations.
442 x0 : float, required
443 Initial guess.
444 fprime : bool or callable, required
445 If `fprime` is a boolean and is True, `f` is assumed to return the
446 value of derivative along with the objective function.
447 `fprime` can also be a callable returning the derivative of `f`. In
448 this case, it must accept the same arguments as `f`.
449 fprime2 : bool or callable, required
450 If `fprime2` is a boolean and is True, `f` is assumed to return the
451 value of 1st and 2nd derivatives along with the objective function.
452 `fprime2` can also be a callable returning the 2nd derivative of `f`.
453 In this case, it must accept the same arguments as `f`.
454 options: dict, optional
455 Specifies any method-specific options not covered above.
457 """
458 pass
461def _root_scalar_ridder_doc():
462 r"""
463 Options
464 -------
465 args : tuple, optional
466 Extra arguments passed to the objective function.
467 bracket: A sequence of 2 floats, optional
468 An interval bracketing a root. `f(x, *args)` must have different
469 signs at the two endpoints.
470 xtol : float, optional
471 Tolerance (absolute) for termination.
472 rtol : float, optional
473 Tolerance (relative) for termination.
474 maxiter : int, optional
475 Maximum number of iterations.
476 options: dict, optional
477 Specifies any method-specific options not covered above.
479 """
480 pass
483def _root_scalar_bisect_doc():
484 r"""
485 Options
486 -------
487 args : tuple, optional
488 Extra arguments passed to the objective function.
489 bracket: A sequence of 2 floats, optional
490 An interval bracketing a root. `f(x, *args)` must have different
491 signs at the two endpoints.
492 xtol : float, optional
493 Tolerance (absolute) for termination.
494 rtol : float, optional
495 Tolerance (relative) for termination.
496 maxiter : int, optional
497 Maximum number of iterations.
498 options: dict, optional
499 Specifies any method-specific options not covered above.
501 """
502 pass