Solving sum of fractions equations

52 Views Asked by At

Suppose you have a large number of values; $${a_i}, {b_i} \ and \ {c_i} $$

And you wish to approximate the solution, for x real, of:

$$ \sum_{i=1}^{n} \frac{a_i}{{b_i}+x*{c_i}} = 0 $$ IE, with n large, n = 100, 1000 etc.

I know this is non-linear programming/optimization. Something like Newton's method occurs to me but avoiding all the poles would be a challenge. Are there any standard method for systems of equations in this form? (also, there may be as many zeros as n as well as poles to avoid). Also it would be good to be able consider the multi-variable case (with x, y, z..).

1

There are 1 best solutions below

1
On BEST ANSWER

You have to pay attention to the poles. As we can divide an $a_i,b_i,c_i$ set by $c_i$ without changing anything, we can insist that all the $c_i =1$, making each term be of the form $\frac {a_i'}{x+b_i'}$. If you consider two neighboring poles $p_i=-b_i$ and $p_j=-b_j$, the interval $(p_i,p_j)$ is free of poles. If $a_i' \gt 0$ the sum with $x$ just above $p_i$ will be large and positive. If $a_j'\gt 0)$ the sum with $x$ just below $p_j$ will be large and negative. There must then be an odd number of roots,at least one, in $(p_i,p_j)$. The same happens if $a_i,a_j$ are both negative. If they are of opposite signs the sum is large and of the same sign near the two ends of the interval. You will have an even number of roots in the interval, which could be zero. You can find values where it is hard to tell whether there are two roots or none.

I would worry less about saving time with Newton and more about finding approximate roots and maintaining a bracket on them. You might need to use a function minimizer between poles with opposite signs to see if there are two roots or none. If you find there are two, you have a bracket on each one. I like the discussion in Numerical Recipes. It has code and obsolete versions are free online.

Added: here is an example of what I was thinking about no vs. two roots. Say you just have two poles, $\frac 1x + \frac {-1}{x-1}$. there is a local minimum at $x=\frac 12$ of $4$. We can add in another pole $\frac {8}{x-2.5}$ and get a double root at zero. If either the $8$ or the $2.5$ in this pole are a little uncertain, it will be hard to tell if there are roots or not. Presumably you get your $a_i,b_i$ as floats, not as integers, so there will be some uncertainty.