2

I'm looking for a Python algorithm to find the root of a function f(x) using bisection, equivalent to scipy.optimize.bisect, but allowing for discontinuities (jumps) in f. The function f is weakly monotonous.

It would be nice but not necessary for the algorithm to flag if the crossing (root) is directly 'at' a jump, and in this case to return the exact value x at which the relevant jump occurs (i.e. say the x for which sign(f(x-e)) != sign(f(x+e)) and abs(f(x-e)-f(x+e)>a for infinitesimal e>0 and non-infinitesimal a>0). It is also okay if instead the algorithm, for example, simply returns an x within a certain tolerance in this case.

As the function is only weakly monotonous, it can have flat areas, and theoretically these can occur 'at' the root, i.e. where f=0: f(x)=0 for an entire range, x in [x_0,x_1]. In this case again, nice but not necessary for the algo to flag this particularity, and to, say, ensure an x from the range [x_0,x_1] is returned.

FlorianH
  • 600
  • 7
  • 18

1 Answers1

2

As long as you supply (possibly very small) strictly positive positives for xtol and rtol, the function will work with discontinuities:

import numpy as np
>>> optimize.bisect(f=np.sign, a=-1, b=1, xtol=0.0001, rtol=0.001)
0.0

If you look in the scipy codebase at the C source code implementation of the function you can see that this is a very simple function that makes no assumptions on continuity. It basically takes two points which have a sign change, and switches to a smaller range with a sign change, until the iterations run out or the tolerances are met.

Given your requirements that functions might be discontinuous / flat, it is in fact necessary (for any algorithm) to supply these tolerances. Without them, it could be impossible for an optimization function to converge to a solution.

Ami Tavory
  • 74,578
  • 11
  • 141
  • 185