[Octave-bug-tracker] Re: [bug #31070] fzero cannot compute initial bracketing

[Jaroslav Hajek]

On Mon, Sep 20, 2010 at 8:48 AM, c. <address@hidden> wrote:
> Hi,
>
> On 20 Sep 2010, at 08:07, Jaroslav Hajek wrote:
>
> [...]
>
> I was prompted to look into this by one of the authors of this book
> <http://books.google.com/books?id=RytYRWlbuCsC&lpg=PP1&dq=quarteroni%20saleri&pg=PP1#v=onepage&q&f=false>
>
> as she was getting complaints about the fzero examples on page 20 and 70
> working differently
> in Octave and Matlab.
>

Just explain to her to explain to them that Octave's algorithms simply
won't in general work identically to Matlab's, and that's a fact.
Unless they convince MathWorks to release their code under GPL.

>> fzero is designed to work with a bracketing, and it is unrealistic to
>> expect
>> it to always find one, as well as to expect it to behave identically to
>> Matlab.
>> Therefore, I don't see anything "incorrect" about the result.
>
> Oh, well sorry, no offense intended there, it was just because I didn't find
> a "result can be slightly improved"
> option in the "Item Group" menu ;)
>

OK, "Feature Request" is not the best description for an intrinsic
improvement, so I created a new field.

>> If a valid bracketing is not given, fzero simply tries a number of trial
>> points, and in this case none of them works. Of course, for *any* trial
>> sequence you can construct a failing case.
>
>> I don't object to using a better trial sequence, but please
>>
>> 1: Make it separate from any other changes.
>
> Is there a way of splitting a changeset in mercurial or am I better off
> redoing the patch?
>

You can use Mercurial queues.

hg qinit (unless done already)
hg qimp -r tip
hg qpop
... apply part of the patch in .hg/series/ using e.g. vim or emacs.

>> 2: Document what exactly the new sequence is and why is it better. It
>> should
>> be clear from the above that merely pointing out an example where this
>> sequence works and the existing one doesn't is not enough, you should
>> present
>> some sort of discussion about common and uncommon use cases.
>
> The new sequence is essentially
> a +- [(a/100)]
> a +- [(a/100) + (a/100)*sqrt(2)]
> a +- [(a/100) + (a/100)*sqrt(2) + (a/100)*2]
> a +- [(a/100) + (a/100)*sqrt(2) + (a/100)*2 + (a/100)*2^3/2] ...
>
> as opposed to the original one which was
> a +- .1*a, a +- a, a +- 1.5*a, a +- 2*a
>

My motivation was to avoid screwing around in close neighborhood for
too long. For instance, if one solves log10 (x) = 3.5 and uses x =
10^3 as a starting guess, your sequence will take ages to get there,
and those 10 steps you used won't be enough.

> the idea is the same, start close to the guess provided by the user then
> gradually further away,
> simply it is more fine-grained, increases the step more gradually and tries
> a few more choices.

I don't think that is any better, actually.

> Although I agree that there is now general way to make sure a correct
> initial bracketing is always found,
> I believe fzero should at least try a bit harder before failing, so if you
> have ideas for a different approach
> it is OK with me as long as the generated sequence is longer and more
> fine-grained than the current one.
>

I don't, sorry. I'll just wait for others' attempts to criticize them :)

>> PS. If you want to change the default tolerance, make it a separate change
>> with an explanation why.
>
> That was really to copy the default used in Matlab:
>>> optimget(optimset ('fzero'), 'tolx')
> ans =
>   2.2204e-16
>

I don't think that makes sense here. Octave's algorithm is completely
different. If you want to change the tolerance, demonstrate why the
new value is better.


-- 
RNDr. Jaroslav Hajek, PhD
computing expert & GNU Octave developer
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz