0
$\begingroup$

Suppose $a_i,q_i,b_0$ are positive real numbers. I need to solve the following equation for $k$

$$\sum_i^d a_i \exp(-q_i k)=b_0$$

Is this a well-known problem? One my special cases has $a_i=q_i$

In my application $d> 20000$, $q_i\approx 0$. Wondering if equation structure makes it possible to solve faster than Newton's method.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ If the $q$ are all small, and if you expect $k$ to be of moderate size, then $e^{-q_ik}\approx 1-q_ik$ and the whole problem becomes one simple linear equation in $k$. At the very least, this will provide for a good starting guess for a Newton method for solving the "real" problem. $\endgroup$
    – Wolfgang Bangerth
    Mar 1 at 22:31
  • $\begingroup$ I think it becomes $(1-q_i)^k$. This is actually the equation I started with, before switching to $e$ approximation, assuming some transform or series expansion of $e$ might be useful here $\endgroup$
    – Yaroslav Bulatov
    Mar 1 at 23:03
  • $\begingroup$ Cross-posted on dsp.SE $\endgroup$
    – Yaroslav Bulatov
    Mar 2 at 17:52
  • 1
    $\begingroup$ The first order Taylor expansions of $e^{-qk}$ and $(1-q)^k$ are both $1-qk$ (as you can see by multiplying out what $(1-q)^k$ actually is). If $qk\ll 1$, you can choose whichever you want, and $1-qk$ is definitely the easier one. $\endgroup$
    – Wolfgang Bangerth
    Mar 2 at 22:13
  • $\begingroup$ Newton should converge in very few steps and without numerical problems, since the function and all its derivatives are monotonic; and each step costs 2x as much as evaluating the function itself. It seems hard to beat if you consider these points. $\endgroup$
    – Federico Poloni
    Mar 4 at 21:46

1 Answer 1

Reset to default
3
$\begingroup$

If $q_i$ are small, you might get away with solving for k with only one summand where q_i is smallest, as that will be the dominant term. The other terms where q_i are larger will be small due to the exponential function. As the comments suggest, that might just serve as a good starting point for a newton iteration.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Good point, that approach gives a lower bound on true value. And I can get upper bound by averaging $q_i$'s together and using Jensen's $\endgroup$
    – Yaroslav Bulatov
    Mar 3 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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