Finding the roots of a function like $3+\cos(x)+0.005/(x-a)$?

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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.