4
$\begingroup$

How to find the solutions $x $ of the following equation: $$\frac{n_1}{x + n_1} + \frac{n_2}{x + n_2} + \cdots +\frac{n_k}{x + n_k} = 1$$ where $n_i$s are natural numbers.

For the case $k=2$, I get the solutions $\pm \sqrt{n_1n_2}$. I was trying to use Vieta's formulas to simplify the expression, but I am unable to do make any progress. Kindly share your thoughts. Thank you.

  1. I was trying induction on $k$ but didn't lead anywhere.
  2. I tried to represent it as some indefinite integral. But no success.

Also, is there any theoretical significance of these polynomials? Kindly share some references. Thanks again.

$\endgroup$
6
  • $\begingroup$ What do you mean by "to find"? Numerically? $\endgroup$ Commented Aug 9, 2020 at 12:33
  • $\begingroup$ @AlexandreEremenko I want to find a closed-form for the roots. Numerical solution also helps me and appreciated. Thank you. $\endgroup$
    – GA316
    Commented Aug 9, 2020 at 12:40
  • $\begingroup$ "Closed form", whatever it can mean, is unlikely. $\endgroup$ Commented Aug 9, 2020 at 12:55
  • $\begingroup$ Thank you. For a suitable choice of $n_i$s can we say something? $\endgroup$
    – GA316
    Commented Aug 9, 2020 at 13:27
  • $\begingroup$ Not $2$ years but $27$ !!! $\endgroup$ Commented Aug 10, 2020 at 8:42

2 Answers 2

8
$\begingroup$

This equation is a particular case of the so-called Underwood equation $$\sum_{i=1}^n \frac{\alpha_i\, z_i}{\alpha_i- \theta}=1-q$$ where the $\alpha_i> 0$ and $z_i >0$ and $n$ can be very large (potentially up to thousands) and $q$ is given.

With my former research group we spent decades to find efficient numerical methods to solve it since, in chemical engineering, it has to be solved zillions of times in a single simulation.

For sure, as soon as $n>4$, there is no nalytical solutions and numerical methods are required. To me, the key point is to avoid its transform into a polynomial.

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).

If you are not too concerned by computing time, there are simple things you could do. Using you equation, for the root between, say, $n_1$ and $n_2$ which correspond to the vertical asymptotes, transform $$f(x)=\sum_{k=1}^p\frac{n_k}{x + n_k} - 1$$ as $$g(x)=(x+n_1)(x+n_2)f(x)$$ which is the most basic form of the so-called Leibovici & Neoschil method which has been widely used for this class of problems during the last $27$ years. $$g(x)=n_1(x+n_2)+n_2(x+n_1)-(x+n_1)(x+n_2)+(x+n_1)(x+n_2)\sum_{k=3}^p\frac{n_k}{x + n_k}$$ which gives $$g(-n_1)=n_1(n_2-n_1)\qquad \text{and}\qquad g(-n_2)=-n_2(n_2-n_1)$$ Then, a linear interpolation gives, as an estimate, $$x_0=-\frac {2\,n_1\,n_2}{n_1+n_2}$$

The problem is that, in the range, $g(x)$ go through an extremum and using directly Newton method is dangerous. A very good way to avoid any problem is to use a method which combine Newton steps and bisection steps (when Newton method tends to lead outside the range).

I would recommend for example subroutine rtsafe from "Numerical Recipes" which does it. The code is here.

This works quite well without any convergence problem (but it is much less efficient than what was proposed in our paper). For $99.9$% of the zillions of cases we worked, only one bisection step is used.

Edit

Revisiting all the things we tried, another possibility is, for each interval, to change variable : $$x=-n_{1}+\frac{n_{1}-n_2} {1+e^{-t}}$$ and use Newton method for $f(t)$ using $$t_0=\log \left(\frac{n_2}{n_1}\right)$$

For example, using $p=5$ and $n_i=p_{i+3}$ Newton iterates will be $$\left( \begin{array}{cc} n & t_n \\ 0 & 0.4519851 \\ 1 & 1.4953866 \\ 2 & 1.3605234 \\ 3 & 1.3532976 \\ 4 & 1.3532792 \end{array} \right)$$

$\endgroup$
2
  • $\begingroup$ Thank you very much. It is an interesting direction (but I am not very familiar with so I need some time to go through it). I will look at your papers and go through the details. If I have some doubts, I will ask you here. Thanks again for the nice answer. $\endgroup$
    – GA316
    Commented Aug 10, 2020 at 9:51
  • $\begingroup$ @GA316. You are very welcome ! You made me (feeling) younger with this problem. Do not hesitate to contact me for any clarification or whatever. I did not recat to the first version of the problem when the $n_k$ are complex since this is a very, very difficult problem. Cheers :-) $\endgroup$ Commented Aug 10, 2020 at 10:05
3
$\begingroup$

These are zeros of $g'(x)$, where $$g(x) :=\frac{(x+n_1)\cdots(x+n_k)}{x^{k-1}}.$$ Or, switching to $y:=\frac1x$, they correspond to zeroes of $f'(y)$, where $$f(y) := \frac{(1+n_1y)\cdots(1+n_ky)}y.$$

$\endgroup$
4
  • $\begingroup$ Thank you. I like the expression $g(x)$ more. But I am unable to see how to proceed further. Any idea, please? $\endgroup$
    – GA316
    Commented Aug 9, 2020 at 17:24
  • $\begingroup$ E.g., one can use Rolle's theorem to localize the zeros of the derivative. $\endgroup$ Commented Aug 9, 2020 at 18:46
  • $\begingroup$ We write $n_1 < n_2 < \cdots < n_k$ then between $-n_{i+1}$ and $-n_i$ there is a root of $g^{'}(x)$? Any other method to locate the roots more accurately? Thank you. $\endgroup$
    – GA316
    Commented Aug 10, 2020 at 0:48
  • 2
    $\begingroup$ Perhaps you should guide us benevolent commenters by providing more background to your question: what is the motivation? why do you think there miight be sensible answers? why could these answers be interesting? etc. $\endgroup$ Commented Aug 10, 2020 at 3:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .