0
$\begingroup$

My question follows from

Fast root finding for strictly decreasing function

I am a bit surprised from the above page that there is even no efficient root finding algorithm (RFA) for a strictly monotonic function. Consider $f: \mathbb R\to\mathbb R$ defined by $f(z)=\sum_{k=1}^n p_k y_k e^{z y_k} -x$, where $p_k>0$ for all $k=1,\ldots, n\ge 2$. Assume further $y_1<y_2<\cdots<y_n$, and there exists a root $z_*$ for $f$, i.e. $f(z_*)=0$. Then it follows from the assumptions that $f$ is strictly increasing and thus $z^*$ is unique. My concern is to find a numerical approximation of $z^*$.

A straightforward computation yields that

$$f'(z)=\sum_{k=1}^n p_k y_k^2 e^{z y_k}~>~0,\quad \mbox{for all } z\in\mathbb R.$$

Is there any competitive computational method designed for $f$? Comments or remarks are highly appreciated!

PS: My first attempt is to apply Newton's method. Actually, it is easy to remark that

  1. if $y_1\ge 0$, then $f$ is convex;
  2. if $y_n\le 0$, then $f$ is concave;

For these two cases, I think Newton's method may work. As for $y_1< 0<y_n$, I think it holds $\inf_{z\in\mathbb R}f'(z)>0$.

$\endgroup$
  • 2
    $\begingroup$ My favorite approach to finding roots of smooth function is the combination of Newton with bisection (of course, you need also to find an interval with different signs at endpoints for that). The algorithm is very simple: if the Newton iteration is within the interval given by the bisection, you keep it, and if it goes outside, you discard it and continue the Newton iterations from the midpoint of the interval given by the bisection. Usually it works pretty well, but I don't know if the speed it gives is sufficient for you. $\endgroup$ – fedja Apr 29 '19 at 23:30
  • $\begingroup$ @fedja Thanks for the response. Is there a convergence rate analysis? If so, could you please provide a reference for the algorithm that you mentioned? $\endgroup$ – Neymar Apr 30 '19 at 10:46
1
$\begingroup$

Before any algorithm is applied, I recommend rescaling by letting $t=e^z$ and considering $t\in(0,\infty)$. This will make the function more "linear", which will likely prove to be beneficial. If the root is very large, it may even be beneficial to take the log of the function to make it even more linear. If $y_k$ are integers (I assume they are positive since $f$ is supposed to be increasing), then you end up with a polynomial in $t$, of which there are many root-finding algorithms for.

The algorithm fedja mentions in the comments is known as the Newt-safe algorithm. Oscar Veliz has a nice explanation of the method on YouTube. Asymptotically the convergence is the same as Newton's method. The only difference is that it's "safe" to use, provided you have a bound on $z^\star$. A simple bound can be obtained by requiring all terms be greater (less) than $x/n$.

Although I do not think there should be any issues with Newt-safe for this problem, since it is increasing and convex, some other algorithms such as Brent's method or Chandrupatla's method may be of interest to you. Unlike Newt-safe, they are more likely to use bisection for faster initial convergence when the function may not be very linear, causing something such as Newton's method to progress very slowly. They also require no evaluation of the derivative, which, if $n$ is very large, may save enough time per iteration to be faster than Newt-safe.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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