Best root find algorithm for a sum of a specific exponential functions (Sigmoid functions)?

Question

I have to solve a equation of of the form: \begin{align} F = f_1 + f_2 + ... + f_{100} = 0. \end{align} Where $f_{i}$ $(i = 1,2,...,100)$ can be: \begin{align} a_i - \frac{a_ie^{a_i(x-b_i)}}{1+e^{a_i(x-b_i)}} \end{align} or \begin{align} - \frac{a_ie^{a_i(x-b_i)}}{1+e^{a_i(x-b_i)}} \end{align} with $ai, bi$ real numbers on the interval $(0,1)$.

I know $F$ has the following graph's, if all $f_i$ are different:

Since I know tha graph of my function I wanted to use the bissection method. The problem is that I don't know a good interval for my algorithm, which is the $a$ and $b$ of the graph above. I could use $a=-100$ and $b=100$, but since I adding $100$ functions, $F$ at $a=-100$ could be a very large, or very small number, which is a problem in Java, also the root could be out of the interval $[-100,100]$, maybe if this happens I can use a "if, else" to increase my interval to $[-200,200]$, and so on? The main problem is defining a interval for the bissection method.

What is a good root find algorithm for this problem?

Maybe Newton's method, since doesn't require a interval?

I don't know the right tags for this question, or if this is a appropriate site.

Answer 1

Solving your equation $2000$ times is nothing compared to the time it will take you to code even a stupid solution. So any time you spend on being clever is wasted. Be stupid!

Each of your $f_i$s is a sigmoid function which will pretty much have reached its left or right limit when $|a_i(x-b_i)|\ge 20$. So compute all the solutions to $a_i(x-b_i)=\pm 20$, and take the interval between leftmost and rightmost of the solutions. Then use bisection!

To avoid overflow when $a_i(x-b_i)$ is large, use $$ \frac{e^t}{1+e^t} = \frac{1}{1+e^{-t}} $$ to compute it whenever $a_i(x-b_i)>0$.

Answer 2

For this kind of problems, in the chapter "Bracketing and Bisection", Numerical Recipes provides some interesting subroutines.

• zbrac : "given a function and an initial guessed range $x_1$ to $x_2$, the subroutine expands the range geometrically until the root is bracketed by the returned values $x_1$ and $x_2$"
• zbrak : "given a function defined on the interval from $x_1$ to $x_2$, the subroutine subdivides the interval into $n$ equally spaced segments and searches for zero crossings of the function"

When the range is known, one of my favored subroutines is rtsafe which combines bisection and Newton-Raphson methods in the given interval.