Home > Archive > Fortran > February 2005 > Muller's method code ?
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Muller's method code ?
|
|
| Madhusudan Singh 2005-02-21, 8:59 pm |
| Hi
As a part of a problem I am solving, I need to find all the zeroes of a
complex function. I have found (through Google) that Muller's method is the
method of choice for this problem.
Though I have found the algorithm for real variables on mathworld :
http://mathworld.wolfram.com/MullersMethod.html,
I want to save myself some coding/debugging time. So, I was wondering if
someone knows of a URL for this algorithm coded in Fortran 77/95.
Thanks.
| |
| Steven G. Kargl 2005-02-21, 8:59 pm |
| In article <37v5l9F5iq3nfU1@individual.net>,
Madhusudan Singh <spammers-go-here@spam.invalid> writes:
> Hi
>
> As a part of a problem I am solving, I need to find all the zeroes of a
> complex function. I have found (through Google) that Muller's method is the
> method of choice for this problem.
>
> Though I have found the algorithm for real variables on mathworld :
>
> http://mathworld.wolfram.com/MullersMethod.html,
>
> I want to save myself some coding/debugging time. So, I was wondering if
> someone knows of a URL for this algorithm coded in Fortran 77/95.
>
> Thanks.
This came up several months ago. I don't recall a mention of
Muller's method, but this thread may interest you.
http://groups-beta.google.com/group...3DSearch+this+g
roup%26&_doneTitle=Back+to+Search&&d#af79590dca9c8ca5
--
Steve
http://troutmask.apl.washington.edu/~kargl/
| |
| Rich Townsend 2005-02-21, 8:59 pm |
| Madhusudan Singh wrote:
> Hi
>
> As a part of a problem I am solving, I need to find all the zeroes of a
> complex function. I have found (through Google) that Muller's method is the
> method of choice for this problem.
>
> Though I have found the algorithm for real variables on mathworld :
>
> http://mathworld.wolfram.com/MullersMethod.html,
>
> I want to save myself some coding/debugging time. So, I was wondering if
> someone knows of a URL for this algorithm coded in Fortran 77/95.
>
> Thanks.
Hi --
I attach my own implementation of Muller's method for complex variables,
based on Traub's implementation of the algorithm ("Iterative Methods for
the Solution of Equations", Prentice-Hall, Englewood Cliffs). I've found
that this routine works well, and appears to be robust.
A couple of points:
1) Muller's method is not guaranteed to find all roots; it is only as
good as the starting guesses you pass in z_1, z_2 and z_3; furthermore,
there is no guarantee that all roots have been found. This relates to
the larger problem that there is no sure-fire way of finding out how
many roots actually exist.
2) If your complex function is a polynomial, then you may be better off
using Laguerre's method (see Numerical Recipses), whick I believe *can*
find all of the (complex) roots.
cheers,
Rich
| |
| Rich Townsend 2005-02-21, 8:59 pm |
| Rich Townsend wrote:
<snip>
Oh, and one more thing: Mullers method only works for analytic
functions. If your function is non-analytic (because, for instance, you
are using complex variables to 'fake' a general 2D function), then it
simply won't work.
cheers,
Rich
| |
| Steven G. Kargl 2005-02-21, 8:59 pm |
| In article <cvds9j$ef4$1@scrotar.nss.udel.edu>,
Rich Townsend <rhdt@barVOIDtol.udel.edu> writes:
>
> Madhusudan Singh wrote:
>
> I attach my own implementation of Muller's method for complex variables,
> based on Traub's implementation of the algorithm ("Iterative Methods for
> the Solution of Equations", Prentice-Hall, Englewood Cliffs). I've found
> that this routine works well, and appears to be robust.
>
> A couple of points:
>
> 1) Muller's method is not guaranteed to find all roots; it is only as
> good as the starting guesses you pass in z_1, z_2 and z_3; furthermore,
> there is no guarantee that all roots have been found. This relates to
> the larger problem that there is no sure-fire way of finding out how
> many roots actually exist.
Well, you can determine the number of zeros (and poles) within
a closed contour by computing the winding number integral. You
can make the closed contour as large as you want provided it
does not cross a branch cut or include a zero or pole on the
contour itself.
--
Steve
http://troutmask.apl.washington.edu/~kargl/
| |
|
|
| Gert Van den Eynde 2005-02-22, 8:58 am |
| Madhusudan Singh wrote:
> Hi
>
> As a part of a problem I am solving, I need to find all the zeroes of a
> complex function. I have found (through Google) that Muller's method is
> the method of choice for this problem.
>
it all depends whether your complex function is a polynomial or not. If it
is not a polynomial, you'll have no guarantee that you have found all zeros
(unless you know their number already from another source). An other option
could be Newton-Raphson in the complex plane, but convergence is only
guaranteed when you start close enough to a zero. If your function is
polynomial, you could try the companion matrix method, Newton-Maehly or
Laguerre's method.
bye,
gert
| |
| Peter Spellucci 2005-02-22, 8:58 am |
|
In article <37v5l9F5iq3nfU1@individual.net>,
Madhusudan Singh <spammers-go-here@spam.invalid> writes:
>Hi
>
> As a part of a problem I am solving, I need to find all the zeroes of a
>complex function. I have found (through Google) that Muller's method is the
>method of choice for this problem.
this is far from being true. this is an only locally successful method
and will identify just one zero, leaving you even with the problem which one,
if there are more
>
> Though I have found the algorithm for real variables on mathworld :
>
> http://mathworld.wolfram.com/MullersMethod.html,
>
> I want to save myself some coding/debugging time. So, I was wondering if
>someone knows of a URL for this algorithm coded in Fortran 77/95.
>
>Thanks.
if you insist on this, there is it:
http://plato.la.asu.edu/topics/problems/zero.html
for the complex case, as you want it.
but if I had to find zeros of an analytic function, and even all of them, i would
use Laguerres method. (described in detail in P. Henrici's
complex and computational analysis, vol III)
or try a deterministic global minimizer (for abs(f(z)) after reformulating the
problem over R^2., for example globsol of Roger Kearfott
hth
peter
| |
| Gert Van den Eynde 2005-02-22, 8:58 am |
| Madhusudan Singh wrote:
> Hi
>
> As a part of a problem I am solving, I need to find all the zeroes of a
> complex function. I have found (through Google) that Muller's method is
> the method of choice for this problem.
>
it all depends whether your complex function is a polynomial or not. If it
is not a polynomial, you'll have no guarantee that you have found all zeros
(unless you know their number already from another source). An other option
could be Newton-Raphson in the complex plane, but convergence is only
guaranteed when you start close enough to a zero. If your function is
polynomial, you could try the companion matrix method, Newton-Maehly or
Laguerre's method.
bye,
gert
| |
| Madhusudan Singh 2005-02-22, 4:01 pm |
| Madhusudan Singh wrote:
> Hi
>
> As a part of a problem I am solving, I need to find all the zeroes of a
> complex function. I have found (through Google) that Muller's method is
> the method of choice for this problem.
>
> Though I have found the algorithm for real variables on mathworld :
>
> http://mathworld.wolfram.com/MullersMethod.html,
>
> I want to save myself some coding/debugging time. So, I was wondering if
> someone knows of a URL for this algorithm coded in Fortran 77/95.
>
> Thanks.
Thanks to everyone who responded and to Rich who attached his code :)
The function in question is calculated in a recursive fashion (its the most
convenient way to calculate it) but I think it can be expressed as a
rational expression with some effort (being composed of ratios of complex
polynomials).
I am interested in locating the poles of this function, or zeros of its
inverse.
I do not know if that helps in finding a more suited method.
| |
|
|
|
|
|
|
| Steven G. Kargl 2005-02-22, 4:01 pm |
| In article <380sfnF5iqi24U1@individual.net>,
Madhusudan Singh <spammers-go-here@spam.invalid> writes:
> Madhusudan Singh wrote:
>
> I am interested in locating the poles of this function, or zeros of its
> inverse.
>
> I do not know if that helps in finding a more suited method.
The winding number theorem and cauchy integral can be
use to find zeros and poles. I've already posted a
URL that points to previous discussion.
--
Steve
http://troutmask.apl.washington.edu/~kargl/
| |
| Michael Gray 2005-02-24, 8:58 am |
| On Mon, 21 Feb 2005 17:35:06 -0500, Madhusudan Singh
<spammers-go-here@spam.invalid> wrote:
>Hi
>
> As a part of a problem I am solving, I need to find all the zeroes of a
>complex function. I have found (through Google) that Muller's method is the
>method of choice for this problem.
>
> Though I have found the algorithm for real variables on mathworld :
>
> http://mathworld.wolfram.com/MullersMethod.html,
>
> I want to save myself some coding/debugging time. So, I was wondering if
>someone knows of a URL for this algorithm coded in Fortran 77/95.
>
>Thanks.
The Visual Numerics IMSL Library has 2 routines that employ Muller's
method:
The 1st finds zeros of a univariate complex function, the other finds
the real zeros of a real function.
http://www.vni.com/products/imsl/fortran/overview.html
I got my money's worth from this library in under a day.
|
|
|
|
|