2
$\begingroup$

I have a blackbox function that (for the purposes of this question) looks like $3+\cos(x) + 0.005/(x-a)$. The location of this $a$ is unknown (but within $0\to2\pi$). (The $3+\cos(x)$ is just a (bad) approximation.) I need to find the roots of this function. Unfortunately the functional form is too complicated to be analyzed (it involves hypergeometric function), so there is no straightforward bracketing that I can do to find the roots. So I am a bit stuck on it.

My idea so far:

  • Generate a grid that is closely packed enough to see a small bump. near $x=a$. (When the element-wise differences of the grid change sign, further optimize this region.)
  • Do some optimization algorithm to find $a$ (?)
  • Bracket left & right from $a$ to find the root.

Ideas on how to approach this?

$\endgroup$
4
$\begingroup$

I suggest you sample the function and fit a rational function to the samples. You can find $a$ among the poles of the rational function, and the root among the real zeros.

There are many good methods for finding rational function fits, and they would lead to extremely accurate approximations for this type of function with just a small number of samples.

Some packages that you could use are: Vector fitting: https://www.sintef.no/projectweb/vectorfitting/

Rational-Krylov fitting: http://guettel.com/rktoolbox/examples/html/example_frequency.html

The AAA function in Chebfun: http://www.chebfun.org

$\endgroup$
3
  • $\begingroup$ OP here (forgot my login yesterday), thanks, I tried a few of these, but they don't seem to be super reliable on their own (I suppose my function is not as rational as I thought and the pole might not be simple). But in combination with some other methods they might work, I'll keep experimenting! $\endgroup$ – Ewoud Feb 27 at 5:02
  • $\begingroup$ Can you describe the problem with more detail? Rational functions are extremely versatile and can approximate functions with other singularities remarkably well. $\endgroup$ – Amit Hochman Feb 27 at 6:42
  • $\begingroup$ In the end I decided to dive deeper into the 'blackbox' and found a way to avoid the pole altogether. So although this question is now solved, I think the reason that the rational approximation failed is that the pole was not of integer order, and closer to 1/(x-a)^t, where t is some real number. Additionally, I could't sample the function very finely for performance reasons, so these libraries often missed the pole. Thank you for your help in any case - I am sure I will use this at some point in the future! $\endgroup$ – Ewoud Feb 28 at 1:31
3
$\begingroup$

This is a standard problem in numerical analysis. The standard approach if you can't compute derivatives of the function is to use a "bisection search" or, if you want to be fancy, its improvement using the golden ratio or Bent's method. See https://en.wikipedia.org/wiki/Bisection_method and https://en.wikipedia.org/wiki/Brent%27s_method

If you can compute derivatives of the function, then you want to use Newton's method.

Every textbook on numerical methods or numerical analysis will discuss these methods. In fact, there is a whole wikipedia article just on this topic: https://en.wikipedia.org/wiki/Root-finding_algorithms

$\endgroup$
3
  • $\begingroup$ OP here (forgot my login yesterday), but the issue is that the root is only there because of the pole, of which the location is unknown, so there is no bracketing available. $\endgroup$ – Ewoud Feb 27 at 4:31
  • 1
    $\begingroup$ Not true. If you plot the function you mentioned, then at $x=a-\varepsilon$ the function is negative whereas for $x=0$ it is positive. So you can bracket. $\endgroup$ – Wolfgang Bangerth Feb 27 at 20:53
  • 1
    $\begingroup$ I agree, but in practice the sampling would have to be done very finely if to catch the function at a negative value (note the small factor for the pole), so this is computationally not practical $\endgroup$ – Ewoud Feb 28 at 1:24
1
$\begingroup$

As I understand, your function (call it $f(x)$) has only one simple pole at $x=a$ and possibly more than one zero, and $a$ is not known, except that it is in $[0,2\pi]$. In addition, you do not know $f(x)$ in analytical form, which means that you cannot differentiate it analytically. In view of all this, I would suggest the following:

  1. Determine $a$ by applying a root finder to the equation $1/f(x)=0$. (I believe it is important that $a$ be determined accurately, as its degree of accuracy will influence the accuracy of the zeros of $f(x)$.)
  2. After determining $a$, apply a root finder to $f(x)=0$ (or, better, $(x-a)f(x)=0$(?)) to find the zero(s) of $f(x)$.

Of course, you can only use a root finder that does not involve derivatives of $f(x)$. In such a case, I would suggest the generalized secant method'' that I developed for finding simple roots that has order close to 2 (hence efficiency index close to 2 as well) and is easy to apply. You can find it in Wikipedia under the title Sidi's generalized secant method.'' The original paper can be downloaded from http://www.math.nthu.edu.tw/~amen/2008/070227-1.pdf I hope this helps you solve your problem.

$\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.