[SciPy-user] zeros of a function

[william ratcliff]

What about re-expressing the problem as a nonlinear optimization problem
where you're fitting a function function to a vector of zeros?  Then, use
your favorite global optimizer to try to find the minima of the "chi^2" of
this function.  The issue here is that for some functions, even a global
optimizer could run into problems...

William

On 5/23/07, Anne Archibald <peridot.faceted at gmail.com> wrote:
>
> On 23/05/07, John Hassler <hasslerjc at comcast.net> wrote:
>
> >  I don't know of any way that is guaranteed to find _all_ of the zeros
> of an
> > arbitrary function.  Think of a parabola, for example.  A very tiny
> change
> > in coefficients can shift the problem from no roots, to a pair of equal
> > roots, to a pair of distinct roots.  Even a direct search would be
> > problematical, since there might be no axis crossing to help you.
> >
> >  If you know something of the properties of the function, analytical
> > mathematics might help.  If it were my problem, I would try to find out
> as
> > much as I could of the properties of my function before I
> started.  Other
> > than that, your method of 'scanning' by using different starting points
> is
> > as good as any, but there is no way to assure that you have found _all_
> of
> > the zeros without bringing in some other mathematics.
>
> Let me elaborate on this:
>
> If you have a vector-valued function, that is if you are trying to
> find simultaneous zeros of several functions, it is going to be very
> difficult to find even one zero, let alone be confident that you have
> found all of them. See Numerical Recipes (
> http://www.nrbook.com/b/bookcpdf.php ) for a discussion of why this
> is.so difficult.
>
> If you have a scalar function of vector inputs, you probably have
> infinitely many zeros (lying on hypersurfaces), and if you don't the
> equation is guaranteed to be a numerical nightmare.
>
> If you have a scalar function of scalar inputs, it's not hard to close
> in on a zero once you're sure you've found one (by having a bracket,
> one point with a negative value and the other with a positive value).
> In general it is indeed difficult (and perhaps impossible) to be
> certain you have found all the zeros. If you have analytic
> derivatives, you can use, for example, an upper bound on the second
> derivative to come up with a minimum distance to the nearest root; a
> method based on this idea could probably be written to confidently
> find all zeros (though it will probably be slow and laborious).  If
> your function is a solution to a second-order linear differential
> equation (as many special functions are), there are tricks you can do
> based on Sturm theory (using for example the fact that between every
> two zeros of one solution there must be a zero of the other).
>
> If you have a (univariate) polynomial, you can use polynomial
> factorization to find all its complex roots; numpy's poly1d class does
> just that. You have to be very careful how you represent your
> polynomial (if it is nontrivial) or your roots will be obliterated by
> roundoff error (and I think numpy.poly1d takes a naive approach to
> this).
>
> There is one case where you can actually find all the zeros of a
> system of equations. If they are multivariate polynomials, Grobner
> basis methods will give you an explicit description of all the zeros,
> and will let you do all kinds of other things besides. I don't know
> what their roundoff behaviour is like - almost certainly poor, they
> are normally used with exact arithmetic - and they're exponential in
> the number of variables, but they do work.
>
> Anne
> _______________________________________________
> SciPy-user mailing list
> SciPy-user at scipy.org
> http://projects.scipy.org/mailman/listinfo/scipy-user
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.scipy.org/pipermail/scipy-user/attachments/20070523/38a7e939/attachment.html>