fit.c and Levenberg-Marquardt parameter lambda (fwd)

[Henri P G. <hp...@Du...>]

Hello Gnuplot-ers!

   First, I'd like to say that the Gnuplot fit function has always worked very 
well every time I've used it.  (Thank you.)

   Second, however, I think there is a bug (or "feature") in the implementation 
of the Levenberg-Marquardt algorithm, which may not have been intended.

   I think line 376 of fit.c should read

         tmp_C[num_data + i][i] = sqrt(*lambda);

   instead of

         tmp_C[num_data + i][i] = *lambda;


    The following explains why I think so.  (Please forgive the Matlab-oriented 
notation.)

   The Gnuplot implementation of Levenberg-Marquardt solves the
over-determined system of equations

   [ J ; lambda*eye(n) ] * da = [ dy ; zeros(n,1) ];  ,

which is related to

   [ J'*J + lambda^2*eye(n) ] * da = dy;

in which lambda is squared ... not necessarily the same as
the method proposed by Marquardt, ...

    http://en.wikipedia.org/wiki/Levenberg-Marquardt_algorithm

   On the other hand, the over-determined system of equations

    [ J ; sqrt(lambda)*eye(n) ] * da = [ dy ; zeros(n,1) ];

is related to

   [ J'*J + lambda*eye(n) ] * da = dy;

which *is* the usual form for the Levenberg-Marquardt equations.

Also see equation (1.4) of the Argonne National Lab page:

http://www-fp.mcs.anl.gov/otc/GUIDE/OptWeb/continuous/unconstrained/nonlinearls/section2_1_2.html


   Should fit.c be changed in the next release of Gnuplot?

   I'm not sure, since the fit function ain't necessarily broke, and since it 
converges really well every time I use it.  Although I've studied and studied 
fit.c, I may not have noticed where the sqrt(*lambda) comes in, if it does.

   Is the current implementation an improvement over the usual 
Levenberg-Marquardt method?

   This question would bear further investigation.

   At any rate, I'd be happy to know the outcome of this bug-report.


Henri Gavin


_________________________________________________________________________
Henri P. Gavin                                      Hen...@Du...
Department of Civil and Environmental Engineering   tel: 919 - 660 - 5201
Duke University, Box 90287                          fax: 919 - 660 - 5219
Durham, NC 27708--0287                              www.duke.edu/~hpgavin/