Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2010

[Date Index] [Thread Index] [Author Index]

Search the Archive

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/




  • Prev by Date: Re: What is the problem? There are no images and no wrong reports for
  • Next by Date: Re: notebooks default context
  • Previous by thread: Re: FindRoots?
  • Next by thread: Re: FindRoots?