2
$\begingroup$

I met an equation of the following form:

$$\sum_{i=1}^nk_ip_i e^{-k_i\lambda}~~=~~b,$$

where $p_i\ge 0$, $k_i$ and $b$ are known for $i=1,\cdots, n$. I'd like to know how to find the solution $\lambda$ numerically. Basically, I consider two cases:

1. Assume that $k_i\ge 0$ for all $i=1,\cdots, n$. Then the function $\varphi(\lambda):=\sum_{i=1}^nk_ip_i e^{-k_i\lambda}$ is clearly decreasing and convex on $\mathbb R$. Under this situation, it is known that, for any $b<0$, there is no solution, and for any $b>0$, there is a unique solution. So does there exist some numerical scheme treating the special case?

2. Actually in my problem I can chose $k_i$ with some kind of freedom. So I can simply set $k_i=i/n$ w.l.o.g. and under this situation, solving the equation turns to solve the following polynomial

$$\sum_{i=1}^na_i z^i~~=~~b,$$

where $a_i=ip_i/n$ and $z=e^{-\lambda/n}$. My question is how to solve numerically this polynomial (assuming $b>0$)?

Many thanks for the idea and comment!

$\endgroup$
8
  • $\begingroup$ If you can set all but two or three k_i to zero, you might produce a quadratic or linear polynomial to solve. Even if you don't get an exact solution, it may point a way toward rapid approximation. Gerhard "Try N Equal To Three" Paseman, 2017.05.18. $\endgroup$ May 18, 2017 at 15:48
  • $\begingroup$ @GerhardPaseman Thanks for the reply. Could you please clarify your answer? Btw, I can't find the reference "Try N Equal To Three". Could you specify a bit more? Thanks so much! $\endgroup$
    – Higgs88
    May 18, 2017 at 16:12
  • $\begingroup$ Suppose n (N)=1. I can solve for lambda by direct inversion, getting Clog b + D which you can clarify. If N=2 and you have a choice of k's, proceed as you say and work with your linear equation in z. If you Try N Equal To Three (N=3), you have a quadratic in z if you choose. (You can also set some k's to zero to reduce to earlier problems.) When you understand N=3, you will either have insight to handle general N, or (we hope) a way to tweak things so that an N+1 problem reduces to fudging nicely a problem with N terms. Gerhard "Sort Of Like Fuzzy Induction" Paseman, 2017.05.18. $\endgroup$ May 18, 2017 at 16:36
  • $\begingroup$ Sorry. I should say quadratic for linear for N=2 and cubic for quadratic for N=3. Gerhard "Within An Order Of Magnitude" Paseman, 2017.05.18. $\endgroup$ May 18, 2017 at 16:44
  • 2
    $\begingroup$ I expect Newton's method will work quite well. Is there a reason you aren't satisfied with it? $\endgroup$ May 18, 2017 at 17:09

2 Answers 2

2
$\begingroup$

Pretty much any textbook method should work on a monotonic and convex function. Bisection, for instance, if you want to keep it simple (once you manage to find upper and lower bounds for the solution, which shouldn't be hard).

I recommend Newton's method, because your derivative is easy to compute and one can prove that (on a decreasing convex function) if you start from an $x_0$ smaller than the solution it always converges monotonically and at least quadratically to it: it is a variant of the result mentioned here -- just apply it to $f(-x)$).

I would avoid using solvers for polynomial equations, because it is going to be difficult to enforce that the solution is positive if you use one.

$\endgroup$
0
$\begingroup$

Let $f_r$ be the function $f_r(x)= re^{-rx}$. For real $r\gt 0$, $f_r$ strictly decreases as $x$ strictly increases, and so the same holds for any positive linear combination of the $f_r$ where $r$ ranges over a finite set of positive real numbers.

Suppose you have found $\lambda_n$ given $b$, a finite set of $n$ positive $r$'s, and your positive linear combination $C$ using $p_i$ of the $f_r$. Now you are given the next coefficient $p_{n+1}$ and you need to find a bigger $r$ and a bigger $\lambda$ to solve your system which now is $C(\lambda) + p_{n+1}f_r(\lambda)=b$.

Here is an approach. Pick a nice $\lambda \gt \lambda_n$, compute $y=b - C(\lambda)$ which is greater than 0, and now look for $r$ so that $p_{n+1}f_r(\lambda)=y$. You now have a new $r$ and a new $\lambda$ that you got to pick for your $n+1$ problem. You can even use the derivative of $C$ to guide your choice for $\lambda$.

Gerhard "Free To Choose The Answer" Paseman, 2017.05.18.

$\endgroup$

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