An algorithm for iteratively changing a complex function?

Question

This algorithm finds the given value of n by iterating between the lower bound and the upper bound, similar to a binary search. How can I improve this algorithm? A few details. The value of n almost always less than 1.0, but this is not a boundary condition. This, however, is not less than 0.

 def approx_value(n, lower_bound, upper_bound, precision = 0.001): approx = (lower_bound + upper_bound) / 2.0 while (abs(approx - n) > precision): if n > approx: lower_bound = approx else: upper_bound = approx approx = (lower_bound + upper_bound) / 2.0 return approx def approx_value_no_bounds(n, precision = 0.0001): approx = 1.0 while (abs(approx - n) > precision): if approx > n: #decrease volatility return approx_value(n, 0.0, approx) else: approx *= 2 return approx 

I know this seems weird because the value of n has already been sent, but the algorithm is not complete. Basically, n is a solution to a complex equation that cannot be solved for approx in closed form, so I do iteratively. In the end, this algorithm will compare the value of the function when using approx with the value n , and return approx approximate the input variable quite well.

I hope to keep the running time in O(log(n)) , so I modeled it several times after a binary search, albeit a little, because the upper bound is not necessarily immediately known.

Answer 1

This sounds like a classic optimization problem. They are well studied and there are several well-known algorithms. Some simple but reasonably effective Newton's method or gradient descent .

You can also try the nonlinear simplex algorithm if the above does not work very well for your function.

The time spent against compromising accuracy here depends on the nature of the function you are trying to solve.

Answer 2

The Optimization and Root Search functions (scipy.optimize) can be useful here .

Here is an example that overrides the sun_altitude(time) function using scipy.optimize.brentq() .