tree 70668cc29220316e235774669f5df19de2198553
parent 967122def6fea54d36df4294a0275e88c0ff46d9
author Sameer Agarwal <sandwichmaker@gmail.com> 1431576799 -0700
committer Sameer Agarwal <sameeragarwal@google.com> 1431578235 -0700

Improve numeric differentation near zero.

Before this change, the default step size
for a function F(x) at x was

step_size = |x| * relative_step_size

if step_size was exactly zero, then to prevent
division by zero we would fall back to relative_step_size.

This however is not good enough, as values of x say 1e-64
would lead to step sizes ~ 1e-70 and dividing by such numbers
leads to inaccurate results. For even smaller numbers, like
1e-300, which I have observed can occur as the optimization
algorithm makes progress, this leads to NaNs.

The key change in this CL is to change the fallback mechanism
to be

step_size = max(|x| * relative_step_size, min_step_size)

where

min_step_size = sqrt(DBL_EPSILON)

This is the recommended minimum value for the step size
for double precision arithmetic on the interwebs.

This results in a small loss of precision in the transcendental
functions test, but that is unavoidable as we are not taking
sufficiently small steps anymore.

On the whole though this will improve the numerical performance
of the algorithm.

To validate this approach, one of the parameter values for the
EasyFunctorTest has been set to 1e-64, which causes the test
to start failing without the corrected fallback logic.

This change should also address some if not all of

https://github.com/ceres-solver/ceres-solver/issues/121

Change-Id: I4a9013ef358626c1ba7b8abad60b3904163d63f6