fzero f(x) vs. fminbnd f(x)^2
Ivan Werning
Is there any reason that minimizing the square of a function (using fminbnd say) could ever perform better than the search for a zero (using fzero say).
-Ivan
Matt J
> I need to find the zero of a function, many times, actually, within a loop, in my code. I am looking to improve the performance.
>
> Is there any reason that minimizing the square of a function (using fminbnd say) could ever perform better than the search for a zero (using fzero say).
Off the top of my head, fminbnd doesn't require that f(x1) and f(x2) be of opposite sign, where [x1,x2] is the search interval.
fzero does require this and therefore may require extra computational effort.
John D'Errico
NO! NO. NO. This advice is completely wrong.
Fzero does NOT require a bracket around the root.
Fzero works better if you give it a bracket, since
this assures a solution as long as your function is
continuous.
fzero(@sin,2)
ans =
3.14159265358979
On the other hand, fminbnd DOES require a
bracket, i.e., a pair of points that define the search
interval. So effectively, fminbnd is the routine that
needs a bracket!
There are other reasons to avoid the use of fminbnd
here. By squaring the objective, you may limit the
accuracy you can ever achieve in the root.
John
Matt J
> "Matt J " <mattja...@THISieee.spam> wrote in message <hnqrtd$sth$1...@fred.mathworks.com>...
> > "Ivan Werning" <iwer...@yahoo.com> wrote in message <hnqr5h$gl7$1...@fred.mathworks.com>...
> > > I need to find the zero of a function, many times, actually, within a loop, in my code. I am looking to improve the performance.
> > >
> > > Is there any reason that minimizing the square of a function (using fminbnd say) could ever perform better than the search for a zero (using fzero say).
> > ==============
> >
> > Off the top of my head, fminbnd doesn't require that f(x1) and f(x2) be of opposite sign, where [x1,x2] is the search interval.
> >
> > fzero does require this and therefore may require extra computational effort.
>
> NO! NO. NO. This advice is completely wrong.
>
> Fzero does NOT require a bracket around the root.
It doesn't require it, but what if you are only interested in solutions in a particular interval?
Additionally, suppose you are interested in finding a root in a particular interval where you know the function doesn't change sign? fminbnd may be your only option (admittedly, though, you wouldn't have to square the function in that case).
John D'Errico
> > Fzero does NOT require a bracket around the root.
>
>
> It doesn't require it, but what if you are only interested in solutions in a particular interval?
This is not an argument for fminbnd, but really an
argument for fzero in this situation.
fzero can happily work in either mode. fminbnd
REQUIRES a bracket. So fzero is more flexible here.
And given that fminbnd will potentially be less
accurate, there are few reasons why one might
choose that option.
> Additionally, suppose you are interested in finding a root in a particular interval where you know the function doesn't change sign? fminbnd may be your only option (admittedly, though, you wouldn't have to square the function in that case).
If there is a zero at a point where the function
does not change sign, then squaring it is a very
bad move. This point is a multiple root already,
so squaring it will cause a further loss of precision
in the root finding operation.
IF you are confident that the function truly has a
multiple root at a point (a root of specifically even
multiplicity), then use of fminbnd WITHOUT
squaring the function makes some sense, but only
in that fairly limited scenario.
Understand your problem, as well as the tools that
you use to solve it.
John
Matt J
> > It doesn't require it, but what if you are only interested in solutions in a particular interval?
>
> This is not an argument for fminbnd, but really an
> argument for fzero in this situation.
>
> fzero can happily work in either mode. fminbnd
> REQUIRES a bracket. So fzero is more flexible here.
=====================
No, as I posted initially, if fzero is supplied a bracket, it will work with it happily only if the function values at the bracket boundaries f(x1) and f(x2) are of opposite sign. Otherwise, according to the doc (in R2009b), it will return an error. Conversely, fminbnd does not have this restriction.
This means that if you start with endpoints where sign( f(x1) )=sign( f(x2)
and you insist on using fzero, you must spend some computation searching for a smaller bracket that satifies these requirements.
> IF you are confident that the function truly has a
> multiple root at a point (a root of specifically even
> multiplicity), then use of fminbnd WITHOUT
> squaring the function makes some sense, but only
> in that fairly limited scenario.
There is an additional scenario, which I wouldn't consider all that limited.
Suppose you are asked to analyze an interval [x1,x2] to see if it contains a root and if so, to determine the root's location. If you had f(x1) and f(x2) of opposite sign and you knew the function to be continuous, then you know right away that the interval contains a root and fzero will find it for you.
Conversley, though, if the signs at the boundaries are the same, it's not clear what better option you have than to run fminbnd on f(x)^2
Ivan Werning
I see the issues regarding potential non changing of signs the supplying of bounds, etc, if I didn't know that my function was well behaved. These are all good points and the comments here are useful. But in my current case, I am not that worried with the robustness across problems in this regard. Let's say I am confident that f crosses zero once and changes sign within an interval of interest. Thus, I would call either function with such interval.
I was wondering about the potential speed in finding a "good" solution.
Thanks!
-Ivan
Matt J
> I was wondering about the potential speed in finding a "good" solution.
That's probably going to take experimentation. Although the journal articles describing each algorithm are referenced in the docs for fminbnd and fzero, and you could read those to get an idea which would be faster (I haven't).
However, just from eyeballing the description there, I would say that fminbnd is going to give faster convergence the more linear is your function on the interval of interest.
In the extreme case where your function was exactly linear, you would be using quadratic interpolation on a quadratic function, which should reach the function in a single interpolation step.
Conversely, the algorithm for fzero uses, according to the doc, a combination of bisection, inverse quadratic interpolation, and secant method steps. The first two for sure wouldn't find the root of a linear function in a single step. A secant step would, but we don't know, without reading the articles, at what point the secant steps kick in...
Matt J
> In the extreme case where your function was exactly linear, you would be using quadratic interpolation on a quadratic function, which should reach the function in a single interpolation step.
>
> Conversely, the algorithm for fzero uses, according to the doc, a combination of bisection, inverse quadratic interpolation, and secant method steps. The first two for sure wouldn't find the root of a linear function in a single step. A secant step would, but we don't know, without reading the articles, at what point the secant steps kick in...
=======================
I was curious enough to go ahead and test the above theory using the code at the bottom of this post. The results were
>> test('fzero'), test('fminbnd')
ans =
AverageTime: 4.5154e-004
FunctionEvaluations: 3
iterations: 1
ans =
AverageTime: 5.4850e-004
FunctionEvaluations: 6
iterations: 5
So, in contrast to my expectations, it looks like fminbnd was a bit slower here. However, the results are somewhat confusing, the amount by which fminbnd was slower was not at all in proportion either to the number of iterations or the number of function evaluations. It's not clear where the overhead is coming from...
%%%%%%%%%%%%%%TEST CODE%%%%%%%%%%%
function results=test(fname)
Niter=3000;
x0=[0,2];
x1=x0(1);
x2=x0(2);
options.TolX=1e-6;
switch fname
case 'fzero'
fun=@line;
tic;
for ii=1:Niter
[x,fval,exitflag,output] = fzero(fun,[0,10],options);
end
results.AverageTime=toc/Niter;
results.FunctionEvaluations=output.funcCount;
results.iterations=output.iterations;
case 'fminbnd'
fun=@quadline;
tic;
for ii=1:Niter
[x,fval,exitflag,output] = fminbnd(fun,0,10,options);
end
results.AverageTime=toc/Niter;
results.FunctionEvaluations=output.funcCount;
results.iterations=output.iterations;
end
function f=line(x)
f=x-1;
function f=quadline(x)
f=(x-1).^2;
Ivan Werning
Perhaps fzero has overhead in deciding what method to use.
Interesting analysis. Thanks.
Jeff Freeman
I have to solve the following equation for the variable f (For those who recognize, f is the Darcy friction factor from the Moody diagram http://en.wikipedia.org/wiki/Moody_chart):
1/sqrt(f)) = -2.0 * log10(((epsilon/Dh)/3.7) + (2.51/(Re*sqrt(f))))
This equation is monotonically decreasing and generally behaves very well.
I repeat the process hundreds of times inside of multiple calls to ode45, and some testing with Profiler suggests that this is *the* most time consuming part of the entire code.
I tested four different root solving options, and they are listed below from most time (1) to least time (4). All for methods found the same solution. The solver (fzero or fminbnd) was called roughly 1100 times in each case. The total time of each program and the number of calls to the function [variants of @(f) (LHS - RHS)] are also listed below.
(1) f = fzero(@(f) (LHS - RHS), 0.01);
Time = 1.444 s
Calls = 25986
(3) f = fminbnd(@(f) abs(LHS - RHS), 0.0001, 0.1);
Time = 1.402 s
Calls = 15319
(2) f = fminbnd(@(f) (LHS - RHS)^2, 0.0001, 0.1);
Time = 1.203 s
Calls = 14156
(4) f = fzero(@(f) (LHS - RHS), [0.0001, 0.1]);
Time = 1.048 s
Calls = 13811
It seems that fzero has less overhead iff it is given a bounding interval, and you can't use fminbnd without a bounding interval anyways. I can't particularly talk to the robustness of the two different tools, but for simple root solving I recommend fzero with a bounding interval.
Hope this helps,
Jeff Freeman