Re: FindRoots?
- To: mathgroup at smc.vnet.net
- Subject: [mg112362] Re: FindRoots?
- From: "Ted Ersek" <ersekt at md.metrocast.net>
- Date: Sat, 11 Sep 2010 05:42:52 -0400 (EDT)
(**** What do we need RootSearch for? ****)
In [1] Andrzej Kozlowski showed that Reduce in Mathematica 7 can quickly
locate many roots of a transcendental equation. He then asked,
"So what do you need RootSearch for?" Well I think RootSearch is still an
important tool in cases that are not at all rare such as ...
Others were correct when they mentioned that RootSearch is very good at
finding roots of an InterpolatingFunction such as the ones we get from the
built-in functions NDSolve, and Interpolation.
In [2] Ingolf Dahl gave two examples of finding solutions of closed form
equations
where Reduce is very slow, but RootSearch can quickly find all the roots
provided
the search interval isn't too large.
RootSearch also comes to the rescue in cases like
Foo[x_Real] := SomeNumericalAlgorithm[x]
RootSearch[ Foo[x]==0, {x, xmin, xmax} ]
We also know from [3] that Reduce can't handle branch cuts. The same Blog
post also
seems to indicate that Reduce can only find roots of holomorphic functions.
That probably
gives us other problems where we need RootSearch.
In [4] Andrzej Kozlowski said, "there are ways to do essentially the same
things that
RootSearch attempts to do and obtain the complete set of roots (provably
complete)."
Are these methods practical in every conceivable case? I wonder if it's even
possible in every case.
In [3] Roger Germundsson of Wolfram Research said there are theorems about
undecidability
of finding roots of a general numeric function.
The new capability of Reduce is a wonderful addition, and in many cases
Reduce
should be preferred over RootSearch. However, I think we will always have a
need
for RootSearch (or a similar function) just as we will always have a need
for NIntegrate,
NDSolve even though Integrate, DSolve are state-of-the-art.
(**** Limitations of Numerical Root Finding ****)
Of course RootSearch has its own limitations as does any numerical method
for Root Finding,
Numerical Integration, or Solving Differential Equations. All such
algorithms are limited
by the number of discrete samples taken and the number of iterations
allowed. In
addition for any such algorithm to be practical, it must use approximate
numbers.
As with other numerical methods we can use RootSearch options to make it
more robust
at the expense of needing more time to get a result.
(****** Why I wrote RootSearch ******)
When I wrote the RootSearch package several years ago there was much more
need
for it because FindRoot was the best thing Wolfram provided for solving
transcendental
functions. Mathematica is a fantastic application, and nearly all its
algorithms have
amazing power. However, my RootSearch package is proof that FindRoot is far
from
state-of-the-art when it comes to finding roots in one-dimension. It should
be an
embarrassment to Wolfram that the "rather primitive" methods in my
"amateurish package"
perform far better than FindRoot in the case of searching in one-dimension.
(***** Wolfram Can Improve RootSearch. Then Include it in Mathematica
*****)
Several times I told Wolfram Research they can use any of the packages I
posted on
MathSource in future versions of Mathematica. I also told them they can make
any
changes to my code that they want, and I expect nothing in return. I don't
even care
if I get credit for my contribution.
Actually, I don't want Wolfram to use my RootSearch package verbatim in
Mathematica.
Instead I want them to implement a state-of-the-art routine with the same
design goals
as RootSearch. However, I think they should study my implementation because
I may
have had some good ideas. Also, I don't care if they call the function
RootSearch,
NReduce, or whatever.
(***** Searching for Roots in N-dimensions *****)
RootSearch doesn't attempt to find all roots of N-equations in a finite
region of
N-dimensions. I would have included that capability, but I still have a lot
to learn before
I can do that. I hope Wolfram will implement a state-of-the-art numerical
algorithm to
search for roots in N-dimensions. As Andrzej Kozlowski mentioned in this
thread, he explains
how this could be done in a Mathematica demonstration [5].
(***** Other Routines That Search for All Roots? *****)
As a side note, I have tried to find evidence that someone else has
written a routine with the same design goal as RootSearch. I have yet to
find such evidence in any journal, math library, commercial application,
free-ware, etc. In particular Mathematica's competition only provides
functions similar to FindRoot. It's a great mystery to me why this
subject is so neglected. I think the subject has important applications,
and the algorithms needed are probably is simple compared to what's
inside NDSolve.
(***** FindRoot Is Not Used In RootSearch *****)
Contrary to what Andrzej Kozlowski said my RootSearch package doesn't
use Mathematica's FindRoot. I had to write my own implementations of
Secant-Method and Brent's-Method to give RootSearch some of it's nice
features.
(****** RootSearch posts a message about $MinPrecision=-Infinity ******)
With recent versions of Mathematica RootSearch posts a message about
$MinPrecision=-Infinity. This is due to a few places where my
implementation uses
Block[ {$MinPrecision=-Infinity}, expr ]
It makes more sense to use the following instead.
Block[ {$MinPrecision=0}, expr ]
You can make that change in the code and RootSearch will stop posting the
message
with no adverse consequences.
(****** My Next RootSearch Version ******)
A while ago I started work on a major overhaul of my code.
I have made slow progress on it with the little bit of time I have for
Mathematica.
Ted Ersek
(*********** References ***********)
[1] http://forums.wolfram.com/mathgroup/archive/2010/Sep/msg00009.html
[2] http://forums.wolfram.com/mathgroup/archive/2010/Sep/msg00148.html
[3]
http://blog.wolfram.com/2008/12/18/mathematica-7-johannes-kepler-and-transce
ndental-roots/
[4] http://forums.wolfram.com/mathgroup/archive/2010/Sep/msg00168.html
[5]
http://demonstrations.wolfram.com/SolvingSystemsOfTranscendentalEquations/