Coverage for /usr/lib/python3/dist-packages/scipy/optimize/_root

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

12from ._numdiff import approx_derivative

14__all__ = ['root_scalar']

16ROOT_SCALAR_METHODS = ['bisect', 'brentq', 'brenth', 'ridder', 'toms748',

17 'newton', 'secant', 'halley']

20class MemoizeDer:

21 """Decorator that caches the value and derivative(s) of function each

22 time it is called.

24 This is a simplistic memoizer that calls and caches a single value

25 of `f(x, *args)`.

26 It assumes that `args` does not change between invocations.

27 It supports the use case of a root-finder where `args` is fixed,

28 `x` changes, and only rarely, if at all, does x assume the same value

29 more than once."""

30 def __init__(self, fun):

31 self.fun = fun

32 self.vals = None

33 self.x = None

34 self.n_calls = 0

36 def __call__(self, x, *args):

37 r"""Calculate f or use cached value if available"""

38 # Derivative may be requested before the function itself, always check

39 if self.vals is None or x != self.x:

40 fg = self.fun(x, *args)

41 self.x = x

42 self.n_calls += 1

43 self.vals = fg[:]

44 return self.vals[0]

46 def fprime(self, x, *args):

47 r"""Calculate f' or use a cached value if available"""

48 if self.vals is None or x != self.x:

49 self(x, *args)

50 return self.vals[1]

52 def fprime2(self, x, *args):

53 r"""Calculate f'' or use a cached value if available"""

54 if self.vals is None or x != self.x:

55 self(x, *args)

56 return self.vals[2]

58 def ncalls(self):

59 return self.n_calls

62def root_scalar(f, args=(), method=None, bracket=None,

63 fprime=None, fprime2=None,

64 x0=None, x1=None,

65 xtol=None, rtol=None, maxiter=None,

66 options=None):

67 """

68 Find a root of a scalar function.

70 Parameters

71 ----------

72 f : callable

73 A function to find a root of.

74 args : tuple, optional

75 Extra arguments passed to the objective function and its derivative(s).

76 method : str, optional

77 Type of solver. Should be one of

79 - 'bisect' :ref:`(see here) <optimize.root_scalar-bisect>`

80 - 'brentq' :ref:`(see here) <optimize.root_scalar-brentq>`

81 - 'brenth' :ref:`(see here) <optimize.root_scalar-brenth>`

82 - 'ridder' :ref:`(see here) <optimize.root_scalar-ridder>`

83 - 'toms748' :ref:`(see here) <optimize.root_scalar-toms748>`

84 - 'newton' :ref:`(see here) <optimize.root_scalar-newton>`

85 - 'secant' :ref:`(see here) <optimize.root_scalar-secant>`

86 - 'halley' :ref:`(see here) <optimize.root_scalar-halley>`

88 bracket: A sequence of 2 floats, optional

89 An interval bracketing a root. `f(x, *args)` must have different

90 signs at the two endpoints.

91 x0 : float, optional

92 Initial guess.

93 x1 : float, optional

94 A second guess.

95 fprime : bool or callable, optional

96 If `fprime` is a boolean and is True, `f` is assumed to return the

97 value of the objective function and of the derivative.

98 `fprime` can also be a callable returning the derivative of `f`. In

99 this case, it must accept the same arguments as `f`.

100 fprime2 : bool or callable, optional

101 If `fprime2` is a boolean and is True, `f` is assumed to return the

102 value of the objective function and of the

103 first and second derivatives.

104 `fprime2` can also be a callable returning the second derivative of `f`.

105 In this case, it must accept the same arguments as `f`.

106 xtol : float, optional

107 Tolerance (absolute) for termination.

108 rtol : float, optional

109 Tolerance (relative) for termination.

110 maxiter : int, optional

111 Maximum number of iterations.

112 options : dict, optional

113 A dictionary of solver options. E.g., ``k``, see

114 :obj:`show_options()` for details.

115

116 Returns

117 -------

118 sol : RootResults

119 The solution represented as a ``RootResults`` object.

120 Important attributes are: ``root`` the solution , ``converged`` a

121 boolean flag indicating if the algorithm exited successfully and

122 ``flag`` which describes the cause of the termination. See

123 `RootResults` for a description of other attributes.

124

125 See also

126 --------

127 show_options : Additional options accepted by the solvers

128 root : Find a root of a vector function.

129

130 Notes

131 -----

132 This section describes the available solvers that can be selected by the

133 'method' parameter.

134

135 The default is to use the best method available for the situation

136 presented.

137 If a bracket is provided, it may use one of the bracketing methods.

138 If a derivative and an initial value are specified, it may

139 select one of the derivative-based methods.

140 If no method is judged applicable, it will raise an Exception.

141

142 Arguments for each method are as follows (x=required, o=optional).

143

144 +-----------------------------------------------+---+------+---------+----+----+--------+---------+------+------+---------+---------+

146 +===============================================+===+======+=========+====+====+========+=========+======+======+=========+=========+

147 | :ref:`bisect <optimize.root_scalar-bisect>` | x | o | x | | | | | o | o | o | o |

148 +-----------------------------------------------+---+------+---------+----+----+--------+---------+------+------+---------+---------+

149 | :ref:`brentq <optimize.root_scalar-brentq>` | x | o | x | | | | | o | o | o | o |

150 +-----------------------------------------------+---+------+---------+----+----+--------+---------+------+------+---------+---------+

151 | :ref:`brenth <optimize.root_scalar-brenth>` | x | o | x | | | | | o | o | o | o |

152 +-----------------------------------------------+---+------+---------+----+----+--------+---------+------+------+---------+---------+

153 | :ref:`ridder <optimize.root_scalar-ridder>` | x | o | x | | | | | o | o | o | o |

154 +-----------------------------------------------+---+------+---------+----+----+--------+---------+------+------+---------+---------+

155 | :ref:`toms748 <optimize.root_scalar-toms748>` | x | o | x | | | | | o | o | o | o |

156 +-----------------------------------------------+---+------+---------+----+----+--------+---------+------+------+---------+---------+

157 | :ref:`secant <optimize.root_scalar-secant>` | x | o | | x | o | | | o | o | o | o |

158 +-----------------------------------------------+---+------+---------+----+----+--------+---------+------+------+---------+---------+

159 | :ref:`newton <optimize.root_scalar-newton>` | x | o | | x | | o | | o | o | o | o |

160 +-----------------------------------------------+---+------+---------+----+----+--------+---------+------+------+---------+---------+

161 | :ref:`halley <optimize.root_scalar-halley>` | x | o | | x | | x | x | o | o | o | o |

162 +-----------------------------------------------+---+------+---------+----+----+--------+---------+------+------+---------+---------+

163

164 Examples

165 --------

166

167 Find the root of a simple cubic

168

169 >>> from scipy import optimize

170 >>> def f(x):

171 ... return (x**3 - 1) # only one real root at x = 1

172

173 >>> def fprime(x):

174 ... return 3*x**2

175

176 The `brentq` method takes as input a bracket

177

178 >>> sol = optimize.root_scalar(f, bracket=[0, 3], method='brentq')

179 >>> sol.root, sol.iterations, sol.function_calls

180 (1.0, 10, 11)

181

182 The `newton` method takes as input a single point and uses the

183 derivative(s).

184

185 >>> sol = optimize.root_scalar(f, x0=0.2, fprime=fprime, method='newton')

186 >>> sol.root, sol.iterations, sol.function_calls

187 (1.0, 11, 22)

188

189 The function can provide the value and derivative(s) in a single call.

190

191 >>> def f_p_pp(x):

192 ... return (x**3 - 1), 3*x**2, 6*x

193

194 >>> sol = optimize.root_scalar(

195 ... f_p_pp, x0=0.2, fprime=True, method='newton'

196 ... )

197 >>> sol.root, sol.iterations, sol.function_calls

198 (1.0, 11, 11)

199

200 >>> sol = optimize.root_scalar(

201 ... f_p_pp, x0=0.2, fprime=True, fprime2=True, method='halley'

202 ... )

203 >>> sol.root, sol.iterations, sol.function_calls

204 (1.0, 7, 8)

205

206

207 """ # noqa

208 if not isinstance(args, tuple):

209 args = (args,)

210

211 if options is None:

212 options = {}

213

214 # fun also returns the derivative(s)

215 is_memoized = False

216 if fprime2 is not None and not callable(fprime2):

217 if bool(fprime2):

218 f = MemoizeDer(f)

219 is_memoized = True

220 fprime2 = f.fprime2

221 fprime = f.fprime

222 else:

223 fprime2 = None

224 if fprime is not None and not callable(fprime):

225 if bool(fprime):

226 f = MemoizeDer(f)

227 is_memoized = True

228 fprime = f.fprime

229 else:

230 fprime = None

231

232 # respect solver-specific default tolerances - only pass in if actually set

233 kwargs = {}

234 for k in ['xtol', 'rtol', 'maxiter']:

235 v = locals().get(k)

236 if v is not None:

237 kwargs[k] = v

238

239 # Set any solver-specific options

240 if options:

241 kwargs.update(options)

242 # Always request full_output from the underlying method as _root_scalar

243 # always returns a RootResults object

244 kwargs.update(full_output=True, disp=False)

245

246 # Pick a method if not specified.

247 # Use the "best" method available for the situation.

248 if not method:

249 if bracket:

250 method = 'brentq'

251 elif x0 is not None:

252 if fprime:

253 if fprime2:

254 method = 'halley'

255 else:

256 method = 'newton'

257 elif x1 is not None:

258 method = 'secant'

259 else:

260 method = 'newton'

261 if not method:

262 raise ValueError('Unable to select a solver as neither bracket '

263 'nor starting point provided.')

264

265 meth = method.lower()

266 map2underlying = {'halley': 'newton', 'secant': 'newton'}

267

268 try:

269 methodc = getattr(optzeros, map2underlying.get(meth, meth))

270 except AttributeError as e:

271 raise ValueError('Unknown solver %s' % meth) from e

272

273 if meth in ['bisect', 'ridder', 'brentq', 'brenth', 'toms748']:

274 if not isinstance(bracket, (list, tuple, np.ndarray)):

275 raise ValueError('Bracket needed for %s' % method)

276

277 a, b = bracket[:2]

278 try:

279 r, sol = methodc(f, a, b, args=args, **kwargs)

280 except ValueError as e:

281 # gh-17622 fixed some bugs in low-level solvers by raising an error

282 # (rather than returning incorrect results) when the callable

283 # returns a NaN. It did so by wrapping the callable rather than

284 # modifying compiled code, so the iteration count is not available.

285 if hasattr(e, "_x"):

286 sol = optzeros.RootResults(root=e._x,

287 iterations=np.nan,

288 function_calls=e._function_calls,

289 flag=str(e))

290 else:

291 raise

292

293 elif meth in ['secant']:

294 if x0 is None:

295 raise ValueError('x0 must not be None for %s' % method)

296 if 'xtol' in kwargs:

297 kwargs['tol'] = kwargs.pop('xtol')

298 r, sol = methodc(f, x0, args=args, fprime=None, fprime2=None,

299 x1=x1, **kwargs)

300 elif meth in ['newton']:

301 if x0 is None:

302 raise ValueError('x0 must not be None for %s' % method)

303 if not fprime:

304 # approximate fprime with finite differences

305

306 def fprime(x):

307 # `root_scalar` doesn't actually seem to support vectorized

308 # use of `newton`. In that case, `approx_derivative` will

309 # always get scalar input. Nonetheless, it always returns an

310 # array, so we extract the element to produce scalar output.

311 return approx_derivative(f, x, method='2-point')[0]

312

313 if 'xtol' in kwargs:

314 kwargs['tol'] = kwargs.pop('xtol')

315 r, sol = methodc(f, x0, args=args, fprime=fprime, fprime2=None,

316 **kwargs)

317 elif meth in ['halley']:

318 if x0 is None:

319 raise ValueError('x0 must not be None for %s' % method)

320 if not fprime:

321 raise ValueError('fprime must be specified for %s' % method)

322 if not fprime2:

323 raise ValueError('fprime2 must be specified for %s' % method)

324 if 'xtol' in kwargs:

325 kwargs['tol'] = kwargs.pop('xtol')

326 r, sol = methodc(f, x0, args=args, fprime=fprime, fprime2=fprime2, **kwargs)

327 else:

328 raise ValueError('Unknown solver %s' % method)

329

330 if is_memoized:

331 # Replace the function_calls count with the memoized count.

332 # Avoids double and triple-counting.

333 n_calls = f.n_calls

334 sol.function_calls = n_calls

335

336 return sol

337

338

339def _root_scalar_brentq_doc():

340 r"""

341 Options

342 -------

343 args : tuple, optional

344 Extra arguments passed to the objective function.

345 bracket: A sequence of 2 floats, optional

346 An interval bracketing a root. `f(x, *args)` must have different

347 signs at the two endpoints.

348 xtol : float, optional

349 Tolerance (absolute) for termination.

350 rtol : float, optional

351 Tolerance (relative) for termination.

352 maxiter : int, optional

353 Maximum number of iterations.

354 options: dict, optional

355 Specifies any method-specific options not covered above

356

357 """

358 pass

359

360

361def _root_scalar_brenth_doc():

362 r"""

363 Options

364 -------

365 args : tuple, optional

366 Extra arguments passed to the objective function.

367 bracket: A sequence of 2 floats, optional

368 An interval bracketing a root. `f(x, *args)` must have different

369 signs at the two endpoints.

370 xtol : float, optional

371 Tolerance (absolute) for termination.

372 rtol : float, optional

373 Tolerance (relative) for termination.

374 maxiter : int, optional

375 Maximum number of iterations.

376 options: dict, optional

377 Specifies any method-specific options not covered above.

378

379 """

380 pass

381

382def _root_scalar_toms748_doc():

383 r"""

384 Options

385 -------

386 args : tuple, optional

387 Extra arguments passed to the objective function.

388 bracket: A sequence of 2 floats, optional

389 An interval bracketing a root. `f(x, *args)` must have different

390 signs at the two endpoints.

391 xtol : float, optional

392 Tolerance (absolute) for termination.

393 rtol : float, optional

394 Tolerance (relative) for termination.

395 maxiter : int, optional

396 Maximum number of iterations.

397 options: dict, optional

398 Specifies any method-specific options not covered above.

399

400 """

401 pass

402

403

404def _root_scalar_secant_doc():

405 r"""

406 Options

407 -------

408 args : tuple, optional

409 Extra arguments passed to the objective function.

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 x1 : float, required

419 A second guess.

420 options: dict, optional

421 Specifies any method-specific options not covered above.

422

423 """

424 pass

425

426

427def _root_scalar_newton_doc():

428 r"""

429 Options

430 -------

431 args : tuple, optional

432 Extra arguments passed to the objective function and its derivative.

433 xtol : float, optional

434 Tolerance (absolute) for termination.

435 rtol : float, optional

436 Tolerance (relative) for termination.

437 maxiter : int, optional

438 Maximum number of iterations.

439 x0 : float, required

440 Initial guess.

441 fprime : bool or callable, optional

442 If `fprime` is a boolean and is True, `f` is assumed to return the

443 value of derivative along with the objective function.

444 `fprime` can also be a callable returning the derivative of `f`. In

445 this case, it must accept the same arguments as `f`.

446 options: dict, optional

447 Specifies any method-specific options not covered above.

448

449 """

450 pass

451

452

453def _root_scalar_halley_doc():

454 r"""

455 Options

456 -------

457 args : tuple, optional

458 Extra arguments passed to the objective function and its derivatives.

459 xtol : float, optional

460 Tolerance (absolute) for termination.

461 rtol : float, optional

462 Tolerance (relative) for termination.

463 maxiter : int, optional

464 Maximum number of iterations.

465 x0 : float, required

466 Initial guess.

467 fprime : bool or callable, required

468 If `fprime` is a boolean and is True, `f` is assumed to return the

469 value of derivative along with the objective function.

470 `fprime` can also be a callable returning the derivative of `f`. In

471 this case, it must accept the same arguments as `f`.

472 fprime2 : bool or callable, required

473 If `fprime2` is a boolean and is True, `f` is assumed to return the

474 value of 1st and 2nd derivatives along with the objective function.

475 `fprime2` can also be a callable returning the 2nd derivative of `f`.

476 In this case, it must accept the same arguments as `f`.

477 options: dict, optional

478 Specifies any method-specific options not covered above.

479

480 """

481 pass

482

483

484def _root_scalar_ridder_doc():

485 r"""

486 Options

487 -------

488 args : tuple, optional

489 Extra arguments passed to the objective function.

490 bracket: A sequence of 2 floats, optional

491 An interval bracketing a root. `f(x, *args)` must have different

492 signs at the two endpoints.

493 xtol : float, optional

494 Tolerance (absolute) for termination.

495 rtol : float, optional

496 Tolerance (relative) for termination.

497 maxiter : int, optional

498 Maximum number of iterations.

499 options: dict, optional

500 Specifies any method-specific options not covered above.

501

502 """

503 pass

504

505

506def _root_scalar_bisect_doc():

507 r"""

508 Options

509 -------

510 args : tuple, optional

511 Extra arguments passed to the objective function.

512 bracket: A sequence of 2 floats, optional

513 An interval bracketing a root. `f(x, *args)` must have different

514 signs at the two endpoints.

515 xtol : float, optional

516 Tolerance (absolute) for termination.

517 rtol : float, optional

518 Tolerance (relative) for termination.

519 maxiter : int, optional

520 Maximum number of iterations.

521 options: dict, optional

522 Specifies any method-specific options not covered above.

523

524 """

525 pass

Coverage for /usr/lib/python3/dist-packages/scipy/optimize/_root_scalar.py: 15%

130 statements