Re: FindRoots?
Ted Ersek
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/
Andrzej Kozlowski
>
>
> 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 above is a misstatement of what I wrote. I wrote that one can do so in the case of a function (on a closed bounded set) which satisfies certain "mild" condition. The conditions are that it has to be C2 (have a continuos second derivative) and have a non-vanishing Jacobian on the bounded set.
>
>
> (***** 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.
>
I did write once that SearchRoot used FindRoot, probably because I myself used FindRoot in my demonstration but I corrected this myself in a subsequent rely to David Park.
I still do not see any reason for not using FindRoot in RootSearch or any way in which RootSearch is superior to FindRoot for finding a single root (which is the only task FindRoot attempts). The Secant method of finding roots is about 3000 years old. Brent's method originated in early 1970s. Both are hardly "state of the art".
I should also add that there is are a lot of published papers on related to pics, and a lot of research that has been done in recent years. I implemented Semenev's method in my demonstrations because it is so simple, but a more general (though more complicated) techniques had earlier been developed in papers by Michael Dellinitz of the University of Paderborn in Germany and various collaborators. See for example:
Dellnitz, M, Schutze, O, Sertl, S. "Finding zeros by multilevel subdivision techniques" in IMA Journal of Numerical Analysis, volume 22 Issue 2, pp. 167-185
or
Dellnitz, M, Sch=FCtze, O, Zheng, Q."Locating all the zeros of an analytic function in one complex variable."
Journal of Computational and Applied Mathematics (2002) vol. 138 (2) pp. 325-333
There has actually been a great deal of progress in this are in this century.
Andrzej Kozlowski
Andrzej Kozlowski
>
> The conditions are that it has to be C2 (have a continuos second derivative) and have a non-vanishing Jacobian on the bounded set.
I misstated the Jacobian condition. The simplest way to state it is that the function should not have multiple roots in the domain of definition.
Andrzej Kozlowski
On 11 Sep 2010, at 18:39, Andrzej Kozlowski wrote:
> On 11 Sep 2010, at 11:42, Ted Ersek wrote:
>
>>
>>
>> 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 above is a misstatement of what I wrote. I wrote that one can do so in the case of a function (on a closed bounded set) which satisfies certain "mild" condition. The conditions are that it has to be C2 (have a continuos second derivative) and have a non-vanishing Jacobian on the bounded set.
>>
>>
>> (***** 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.
>>
>
> I did write once that SearchRoot used FindRoot, probably because I myself used FindRoot in my demonstration but I corrected this myself in a subsequent rely to David Park.
>
> I still do not see any reason for not using FindRoot in RootSearch or anyway in which RootSearch is superior to FindRoot for finding a single root (which is the only task FindRoot attempts). The Secant method of finding roots is about 3000 years old. Brent's method originated in early 1970s. Both are hardly "state of the art".
>
> I should also add that there is are a lot of published papers on related topics, and a lot of research that has been done in recent years. I implemented Semenev's method in my demonstrations because it is so simple, but a more general (though more complicated) techniques had earlier been developed in papers by Michael Dellinitz of the University of Paderborn in Germany and various collaborators. See for example: