Re: fzero initial bracketing [WAS: bug #31070]

[Jaroslav Hajek]

On Tue, Sep 21, 2010 at 1:38 PM, c. <address@hidden> wrote:
>
> On 21 Sep 2010, at 13:05, Jaroslav Hajek wrote:
>
>> x0 = initial guess;
>> n = 1;
>> fx0 = fun (x0);
>>
>> while (1)
>>  for k = 1:2:n
>>   d = k*2^(k-n);
>>   x1 = x0 + d;
>>   if (sign (fun (x1)) * sign (fx0) <= 0)
>>     break;
>>   endif
>>   x1 = x0 - d;
>>   if (sign (fun (x1)) * sign (fx0) <= 0)
>>     break;
>>   endif
>>  endfor
>>  n++;
>> endwhile
>
> BTW that is the same approach I had in mind except for imposing a lower and
> upper limit to d: tolx*abs(x0) < d < abs (x0).

No, it isn't, as far as I can see. Your sequence was simply partial
sum of bstep * 2^(n/2). Hence, intervals like x0 + (0.1..0.5) * bstep
were never reached. This sequence is different; essentially it picks a
dense subset of real numbers (dyadic numbers) and traverses it in a
defined order. That alone suffices to ensure that any interval is hit
sooner or later.

> I agree that it is unpractical to search for the bracketing over the whole
> real axis, but a finite number of attempts
> might still make sense.
>

Yes, but what attempts? My example algorithm will find the bracketing
almost always (despite the finite precision), and a simple
modification can make it always find the bracketing if it exists. It
may be impractical nevertheless.

I think a much better (and truly practical) algorithm would not just
try a number of trial steps, but make use of the function value
information gathered in the process to attempt to construct "smart"
trials.

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