MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
1  
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)$, \begin{equation} \sum_{i=1}^N\frac{z_i}{w-a_i}=0. \end{equation} 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)$.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.