Solving for a variable inside summation

283 Views Asked by At

The equation is: $$ 0=\sum_{i=1}^{N} -\frac{x_i - y_i}{wx_i+(1-w)y_i} $$ I want to solve for the variable $w$ when the expression is equal to $0$. For a start i tried to solve for $w$ in the case:

$$ 0=\sum_{i=1}^{2} -\frac{x_i - y_i}{wx_i+(1-w)y_i} =-\frac{x_1 - y_1}{wx_1+(1-w)y_1}-\frac{x_2 - y_2}{wx_2+(1-w)y_2} = 0$$

$$w=\frac{-2y_{1}y_{2}+x_{2}y_{1}+x_{1}y_{2}}{2\left(-x_{1}+y_{1}\right)\left(x_{2}-y_{2}\right)}$$

I'm quite confused with how to deal with the summation, is a closed form solution possible ?

1

There are 1 best solutions below

3
On BEST ANSWER

Without any loss of generality, we can assume there there is no $k$ such that $x_k=y_k$. If there is, just change the index skipping the corresponding terms.

In any manner, there is no analytical solution as soon as $n>5$. If $n\leq 5$, reduce to same denominator to face a polynomial of degree $n-1$. For $n>5$, only numerical methods can solve the problem.

We can rewrite the equation as $$f(w)=\sum_{i=1}^n \frac 1{w-a_i}=0 \qquad \text{where} \qquad a_i=\frac{y_i}{y_i-x_i}\tag 1$$

Because of the asymptotes, there are $(n-1)$ solutions.

This is a quite difficult problem I have been working for many years.

It is a particular case of the so-called Underwood equation which appear in chemical engineering where it uses to write $$\sum_{i=1}^n \frac{\alpha_i\, z_i}{ \theta-\alpha_i}=1-q$$

Our most recent work was published in $2014$ in this paper (you can also find it here) where we proposed rapid and robust solution methods using convex transformations. Beside, and this is a key point, for any root, we proposed simple and efficient starting guesses which,typically, make that very few iterations are required (this is illustrated in the first figure showing that the starting guess is almost the solution).

Example

Let us consider the case of equation $(1)$ in which the $a_i$ has been sorted (take care : all of them must be different; otherwise, it is adifferent problem for which I have the solution). So, we have one root in each interval $(a_k,a_{k+1})$ and this is the one we shall look for. The derivatives being all negative, in each interval $f(w)$ is a decreasing function with $f(a_k+\epsilon) \to +\infty$ and $f(a_{k+1}-\epsilon) \to -\infty$.

Now, the trick : instead of considering function $f(w)$, we shall consider function $$g(w)=(w-a_k)(w-a_{k+1})f(w)$$ that is to say $$g(w)=(w-a_k)(w-a_{k+1})\sum_{i=1}^{k-1} \frac 1{w-a_i}+$$ $$(w-a_{k+1})+(w-a_{k})+$$ $$(w-a_k)(x-a_{k+1})\sum_{i=k+2}^{n} \frac 1{w-a_i}$$ This removes the two asymptotes between which is the solution we look for. Now, notice that $$g(a_k)=a_k-a_{k+1} \qquad \text{and}\qquad g(a_{k+1})=a_{k+1}-a_k$$ Drawing a straight line between these two points, we can generate an estimate $w_0=\frac{a_k+a_{k+1}}2$ which could be a good starting point for Newton method.

For an easy example, take $n=10$ and let the $a_i$'s be the square root of the $n$ first prime numbers and we shall search for the solution between $\sqrt 7$ and $\sqrt {11}$. Our starting point will be $w_0=\frac {\sqrt 7+\sqrt {11}}2$; below are reproduce Newton iterates $$\left( \begin{array}{cc} n & w_n \\ 0 & 2.981188051 \\ 1 & 2.925520713 \\ 2 & 2.926397375 \\ 3 & 2.926397421 \end{array} \right)$$

As said, this looks simple; however we must take care that, inside the search interval, $g(w)$ uses to go through a maximum value (in the worked example, at $w=3.27248$ and this is not good for Newton method.

So, what I strongly recommend is to use in the searched interval a combination of bisection and Newton-Raphson steps. You can use for example subroutine rtsafe from "Numerical Recipes" (the code is here). It is simple and robust and for this type of problem, very few bisections steps are required. You even do not need to specify the starting point.