4
$\begingroup$

I am facing a problem where I want to find the complex roots of $f(z)=z-sin(z)=0$ numerically.

There are infinitely many roots of the function, but I am only interested in the $N$ closest to the origin, or to put it more general, within a certain domain in the complex plane.

The Newton-Raphson method also works on complex functions, so given some initial $z_0$, I end up in some root of $f(z)$. However, this is not giving me all roots. I know that the roots will have a basin of attraction, so I will basically need a $z_0$ in every basin of attraction, except that I don't have this basin to start with. Smartest I can come up with, is starting with a grid of $z_0$'s, and to select the uniques. This seems very inefficient.

Therefor my question: is there an efficient method to find all complex roots of $f(z)$ within a domain of the complex plane?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
2
$\begingroup$

To find all complex roots in some domain you need to employ a branch and bound method. Typically one begins with an enclosing box and splits it recursively into subboxes, then applies some constructive method for getting lower and/or upper bounds on the number of solutions in the box. If no solution exists in a box it can be discarded.

Some applicable test are for example in my paper
A. Neumaier, Enclosing clusters of zeros of polynomials, J. Comput. Appl. Math. 156 (2003), 389-401.
http://www.mat.univie.ac.at/~neum/ms/polzer.pdf

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for your answer. I skimmed your paper, but have to take a much more detailed look to get it to work. $\endgroup$
    – Bernhard
    Commented Nov 16, 2012 at 7:01
  • $\begingroup$ Online, I found this paper (pdf-alert) journal.austms.org.au/ojs/index.php/ANZIAMJ/article/download/… , describing more extensively the method you propose. Can you see this as a feasible approach to my problem? (The authors don't claim efficiency, but robustness) $\endgroup$
    – Bernhard
    Commented Nov 22, 2012 at 20:29
  • 1
    $\begingroup$ @Bernhard: Yes, it is feasible, but the calculation of the contour integrals is quite costly. Perhaps you can combine the method there with the tests from my paper (which are fairly cheap in comparison). $\endgroup$
    – Arnold Neumaier
    Commented Nov 23, 2012 at 10:53
  • $\begingroup$ Thanks. I was able to implement the method I provided in the comment. For the specific case I am considering, I have some knowledge about the pole distribution, which allows me in principle to dismiss a lot of the squares on beforehand. I don't think it is necessary for me to implement the tests you provided. $\endgroup$
    – Bernhard
    Commented Nov 23, 2012 at 14:14
1
$\begingroup$

Arnold has already given a good answer. In general, what you are asking for is similar to a global optimization algorithm for finding all the minima of a function (in your case, the minima would be those of $|f(z)|^2=f(z)\overline{f(z)}$. There is a vast amount of literature on this issue if you know the keyword (global optimization) to look for.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Do you have any advised reading or authors on global optimization? $\endgroup$
    – Bernhard
    Commented Nov 16, 2012 at 7:02
  • $\begingroup$ Your local library. $\endgroup$
    – Wolfgang Bangerth
    Commented Nov 17, 2012 at 11:35
  • $\begingroup$ Off course I can find books, but as I am absolutely not familiar with this material, I'd rather pick the right one right away. $\endgroup$
    – Bernhard
    Commented Nov 18, 2012 at 9:23
  • $\begingroup$ I have nothing concrete. I've mostly learned optimization from the book by Nocedal and Wright (who I think have a section on global optimization) and from papers. I know that there are books on global optimization but I haven't looked at any of them. $\endgroup$
    – Wolfgang Bangerth
    Commented Nov 19, 2012 at 2:51

Your Answer

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

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