# Looking for tighter bounds

I have to solve an equation which is $$\sum_{i=1}^N x_i = \sum_{i=1}^N y_i,$$ where
$$x_i = \frac{z_i}{1 + (K_i - 1) w}$$ and $$y_i = \frac{K_i z_i}{1 + (K_i - 1) w}.$$

The $z_i$ are all positive and add to $1$; the $K_i$ are positive but range from very small to very large (at least, one is strictly greater than $1$ and one is strictly smaller than $1$).

The solution ($w$) looked for is between two vertical asymptotes corresponding to $-1 / (K_{\text{max}} - 1)$ (which is negative) and $1 / (1 - K_{\text{min}})$ (which is greater than $1$). Considering the fact that, at solution, all $x_i$ and $y_i$ must be positive and smaller than $1$ (since they both must add to $1$), I have been able to find a left bound corresponding to the maximum value of $\dfrac{K_i z_i - 1}{K_i-1}$ (considering only the $K_i > 1$) and a right bound corresponding to the minimum value of $\dfrac{1 - z_i}{1 - K_i}$ (considering only the $K_i < 1$). These bounds are inside the asymptotes but I need a tighter interval.

I have not been able to go further. Any help will be more than welcome.

-
Why must $\sum x_i$ equal 1? I get that it equals $1/(2-w)$. Note that $y_i = K_i x_i$, then sum the equation $x_i(1+(K_i-1)w)=z_i$ over $i$ and apply $\sum x_i=\sum y_i$. – Brendan McKay Nov 1 '13 at 13:41
@BrendanMcKay. At solution, the sum of the x[i]'s and the sum of the y[i]'s must be equal to 1. Each of these quantities will be computable and computed when the solution (w) looked for will be obtained. – Claude Leibovici Nov 2 '13 at 9:08
Sorry, I miscalculated. – Brendan McKay Nov 2 '13 at 10:46
A colleague of mine, Leonardo Robol, defended a thesis on the numerical solution of this kind of equations as a method to compute eigenvalues and polynomial zeros. – Federico Poloni Apr 1 at 6:37

The equation rewrites as $$\sum_{i=1}^N \frac{(K_i-1)z_i}{1+(K_i-1)w}=0,$$ or with $a_i=1/(1-K_i)$, $$\sum_{i=1}^N\frac{z_i}{w-a_i}=0.$$ Let $Q(w)$ be the monic polynomial of degree $N$ with roots the $a_i$'s, and $P(w)$ some polynomial of degree $N-1$. Assuming all the $a_i$'s are distinct, we have $$\frac{P(w)}{Q(w)}=\sum_{i=1}^N\frac{P(a_i)}{Q'(a_i)}\frac{1}{w-a_i}.$$ If we choose $P(w)$ as the unique interpolating polynomial such that $$P(a_i)=z_iQ'(a_i),\qquad i=1,\ldots,N,$$ the equation simply becomes $$P(w)=0,$$ which has exactly $N-1$ roots. Assume that $$0<K_{1}<\cdots K_i<1<K_{i+1}<\cdots<K_N$$ so that $$a_{i+1}<\cdots<a_N<0<a_1<\cdots<a_i.$$ Since, by assumption, the $z_i$'s are positive, the signs of the $P(a_{i+1}), P(a_{i+2}),\ldots,P(a_i)$ alternate and thus each of the intervals $(a_{i+1},a_{i+2}),\ldots,(a_{i-1},a_i)$ contains exactly one root of the equation. A lower bound for the smallest root is $a_{i+1}=1/(1-K_{i+1})$, and an upper bound for the largest root is $a_i=1/(1-K_i)$.