From: israel@math.ubc.ca (Robert Israel)
Subject: Re: Finding all Roots
Date: 31 Dec 2001 07:00:57 GMT
Newsgroups: sci.math.symbolic
Summary: How to find all zeros of an analytic function

In article <3C2F9483.44299188@cyberlink.ch>,
Burse Jan  <jburse@cyberlink.ch> wrote:

>Maybe you could give me a hint what methods are available
>to find all the roots of a function (x such that f(x)=0)?
>I have a grip of newton, gradient, etc.. methods. But I am somehow
>lost on how to systematically collect all the roots.
>What systematical ways do exist to do that? Do they work for
>polynomials only or also for other classes of functions?

For polynomials, the standard method of counting the number of
real roots in an interval is Sturm's Theorem.  Once you have isolated
the roots in small intervals, you can use Newton's Method to find them.
For analytic functions in general, it can be hard unless you have some 
knowledge of the behaviour of the function as z -> infinity.  Of course
there may be infinitely many roots.  But if you are just working on an
interval (or can somehow determine an interval outside of which there are
no roots) and can generate bounds on the function and its derivatives 
on an interval, it's not too bad.  One method goes basically like this.

Given an interval J in which there might be roots, 
1) Try to prove f is monotone on J.  If so, it's easy to check if there
is a root in the interval, and to find it with bisection and Newton's 
method. 
2) Try to prove f is convex or concave on J.  If so, again it's easy.
3) If that doesn't work, try to reduce the length of the interval as much 
as possible (e.g. if x1 is an endpoint, f(x1) <> 0 and |f'(x)| <= B on J, 
there is no root r in J with |r - x1| < |f(x1)|/B).
4) If that doesn't reduce the length enough, bisect the interval  
and work on each recursively.

My Maple implementation of this idea, a procedure called "allsolve", is
available in my Maple Advisor Database, 
http://www.math.ubc.ca/~israel/advisor.

Robert Israel                                israel@math.ubc.ca
Department of Mathematics        http://www.math.ubc.ca/~israel 
University of British Columbia            
Vancouver, BC, Canada V6T 1Z2