How Many Users Are Happy With FindRoot?
David Park
I am continually being frustrated with the usage and performance of FindRoot. Consider the problem of finding the roots lying between -3 Pi and 3 Pi of the following function.
f[x_] = Tan[x] - (x/2)^2*Tanh[x];
If we plot the function we can see why FindRoot runs into difficulty.
Plot[f[x], {x, -3*Pi, 3*Pi}, Frame -> True,
Axes -> {True, False}, PlotRange -> {-15, 15}];
If we pick starting values that are close enough we obtain the actual roots.
FindRoot[f[x], {x, {-7.5, -4, 2, 4, 7.5}}]
{x -> {-7.78813, -4.51891, 0., 4.51891, 7.78813}}
But I object to having to pick the initial values that closely. This is not convenient and should not be necessary. If we pick the starting values to just be in the middle of each branch, we only obtain one correct root out of five.
FindRoot[f[x], {x, {-2*Pi, -Pi, 0, Pi, 2*Pi}}]
{x -> {-4.51891, 0., 0., 0., 4.51891}}
With the algorithm that Mathematica uses there is no reason we should expect any better. The root searching is jumping from branch to branch. So let's confine it to a single branch. We obtain an error message and an incorrect answer.
FindRoot[f[x], {x, -2*Pi, -5*(Pi/2), -3*(Pi/2)}]
{x -> -5.36881}
It appears that in being ambitious enought to handle complex roots and multiple equations FindRoot has skimped on finding real roots of real equations. Mathematica should use more adaptive methods, perhaps using bisection or other methods to locate roots in a fixed region. One should not even have to give a starting point. These are probably the most common applications of FindRoot and we should expect better performance.
There is a solution. There is a package in MathSource, Enhancements`RootSearch`, by Ted Ersek. It is far better at handling roots of real expressions.
Needs["Enhancements`RootSearch`"]
RootSearch[f[x] == 0, {x, -3*Pi, 3*Pi}]
{{x -> -7.78813}, {x -> -4.51891}, {x -> 0.}, {x -> 4.51891}, {x -> 7.78813}}
This shouldn't be buried away in MathSource. It should be part of Mathematica proper, on an equal par with FindRoot. It should be the user's first choice for finding real roots of real equations. One shouldn't spend time fumbling with FindRoot and then searching outside Mathematica proper for a solution.
David Park
dj...@earthlink.net
http://home.earthlink.net/~djmp/
Janos D. Pinter
Colleagues,
as I mentioned in several recent postings, nonlinear equations (even more
so, systems of such equations) can be tricky... In particular, they may
have no solutions, or a multitude of solutions, and anything in between.
Furthermore, we may not always have a good guess to initialize search for
the root(s). (FindRoot, similarly, to FindMinimum, is based on local search
methodology.) If one wishes to search for roots globally on a given
interval (in R^n, n>=1), then e.g. NMinimize or my third party packages
(MathOptimizer and MathOptimizer Professional) can be used to do that.
Consult, e.g., my book 'Global Optimization in Action', Ch. 4.1. for
technical details.
This note is of course, not to contradict to what David says: rather, added
information that some of you may find useful.
Regards,
Janos Pinter
www.pinterconsulting.com
Andrzej Kozlowski
> *This message was transferred with a trial version of CommuniGate(tm)
> Pro*
I agree that Ted's package is nice, but Mathematica already included
means of solving this sort of problem, e.g.
<< "NumericalMath`IntervalRoots`"
f[x_] = Tan[x] - (x/2)^2*Tanh[x];
IntervalBisection[f[x], x, Interval[{-3*N[Pi], 3*N[Pi]}],
0.1, MaxRecursion -> 10]
Interval[{-7.8048942487621495, -7.7312631709436355},
{-4.565126824747676, -4.491495746929162},
{-0.07363107781851091, 0.07363107781851091},
{4.491495746929162, 4.565126824747676},
{7.7312631709436355, 7.8048942487621495}]
Andrzej Kozlowski
Chiba, Japan
http://www.mimuw.edu.pl/~akoz/
David Park
Your routine looks nice enough, but still most users aren't going to think
of it. One of my beliefs is that Mathematica is not so much a toolbox for
doing mathematics as a meta toolbox for making the tools to do mathematics.
But I make an exception for FindRoot. I think it should be more robust and
have simpler usage out of the box for real roots of real functions. This is
a bread and butter function.
The completion of Andrzej's routine is
<< "NumericalMath`IntervalRoots`"
f[x_] = Tan[x] - (x/2)^2*Tanh[x];
intervals =
IntervalBisection[f[x], x, Interval[{-3*N[Pi], 3*N[Pi]}],
0.1, MaxRecursion -> 10];
MapThread[FindRoot[f[x], {x, Plus @@ #/2}] &, {List @@ intervals}]
{{x -> -7.78813}, {x -> -4.51891}, {x -> 0.}, {x -> 4.51891}, {x ->
7.78813}}
But I was unaware of or had forgotten about IntervalRoots. Again, how many
people are going to think of it BEFORE spending a lot of time with FindRoot,
which they might expect to easily solve a problem like this?
It's true that there is no such thing as perfect root finder even for real
functions. I once wrote a very robust routine for solving the mass action
chemical equilibrium equation. It will quickly solve for all concentrations
to nearly the full precision of the floating point processor over nearly the
full number range of the processor. But it uses a special transformation of
the function and only works for that type of equation. I tried Ted's routine
on these equations and found it worked extremely well. I was able to break
it but it wasn't easy.
That's why I think a significantly better FindRoot could be provided to
Mathematica users.
From: Thomas Burton [mailto:tbu...@brahea.com]
[[ This message was both posted and mailed: see
the 'To' and 'Newsgroups' headers for details. ]]
Golly! I'm pleased as punch with FindRoot :-)
Seriously, the following short, simple-minded, and obvious extension has so
far bailed me out of the kind of problem you describe:
rootSearch[f_,{x_,xMin_,xMax_,dx_,eps_}]:=
Union[Table[FindRoot[f,{x,x0}],{x0,xMin,xMax,dx}],
SameTest -> (Abs[#1[[1,-1]]-#2[[1,-1]]]<eps&)]
I plot the function and then choose limits xMin and xMax and increment dx
appropriately. I get more frustrated when an upgrade to Mathematica breaks
existing code. I had a client frozen to version 4.x because I didn't have
time to sort out why version 5 broke code I wrote for them. Among the issues
were new failures in (my usage of) FindRoot (not for closed-form
expressions).
Which is partly why I am wary of Mathgroup extensions. If the evolution of
core Mathematica functions breaks my code, what about MathSource?
Finding real roots of closed-form expressions is, I should think, a common
application of Mathematica that deserves a method more sophisticated than
Newton and secant. One one hand, to upgrade Mr Ersek's RootSearch from
MathSource to Mathematica's core entails a lot of work: vetting of methods,
extensive quality assurance, commitment to perpetual maintenance, etc.
On the other hand, Mr. Ersek has already done some of the work. Also it's
easy to check the results of a root finder. I always check FindRoot.
RootSearch would be no different. Perhaps the case could be made that
Wolfram
should upgrade Ersek's RootSearch to a standard add-on.
Tom Burton
On Sun, 4 Jul 2004 23:09:59 -1000, David Park wrote
(in article <ccb5t7$enc$1...@smc.vnet.net>):
> Dear MathGroup,
>
> I am continually being frustrated with the usage and performance of
> FindRoot....