4 * This source code is part of
8 * GROningen MAchine for Chemical Simulations
11 * Copyright (c) 1991-2001, University of Groningen, The Netherlands
12 * This program is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU General Public License
14 * as published by the Free Software Foundation; either version 2
15 * of the License, or (at your option) any later version.
17 * If you want to redistribute modifications, please consider that
18 * scientific software is very special. Version control is crucial -
19 * bugs must be traceable. We will be happy to consider code for
20 * inclusion in the official distribution, but derived work must not
21 * be called official GROMACS. Details are found in the README & COPYING
22 * files - if they are missing, get the official version at www.gromacs.org.
24 * To help us fund GROMACS development, we humbly ask that you cite
25 * the papers on the package - you can find them in the top README file.
27 * For more info, check our website at http://www.gromacs.org
30 * GROtesk MACabre and Sinister
32 static char *SRCID_levenmar_c
= "$Id$";
36 #include "types/simple.h"
38 static void nrerror(char error_text
[], bool bExit
)
40 fprintf(stderr
,"Numerical Recipes run-time error...\n");
41 fprintf(stderr
,"%s\n",error_text
);
43 fprintf(stderr
,"...now exiting to system...\n");
48 /* dont use the keyword vector - it will clash with the
49 * altivec extensions used for powerpc processors.
52 static real
*rvector(int nl
,int nh
)
56 v
=(real
*)malloc((unsigned) (nh
-nl
+1)*sizeof(real
));
57 if (!v
) nrerror("allocation failure in rvector()", TRUE
);
61 static int *ivector(int nl
, int nh
)
65 v
=(int *)malloc((unsigned) (nh
-nl
+1)*sizeof(int));
66 if (!v
) nrerror("allocation failure in ivector()", TRUE
);
70 static double *dvector(int nl
, int nh
)
74 v
=(double *)malloc((unsigned) (nh
-nl
+1)*sizeof(double));
75 if (!v
) nrerror("allocation failure in dvector()", TRUE
);
81 static real
**matrix1(int nrl
, int nrh
, int ncl
, int nch
)
86 m
=(real
**) malloc((unsigned) (nrh
-nrl
+1)*sizeof(real
*));
87 if (!m
) nrerror("allocation failure 1 in matrix1()", TRUE
);
90 for(i
=nrl
;i
<=nrh
;i
++) {
91 m
[i
]=(real
*) malloc((unsigned) (nch
-ncl
+1)*sizeof(real
));
92 if (!m
[i
]) nrerror("allocation failure 2 in matrix1()", TRUE
);
98 static double **dmatrix(int nrl
, int nrh
, int ncl
, int nch
)
103 m
=(double **) malloc((unsigned) (nrh
-nrl
+1)*sizeof(double*));
104 if (!m
) nrerror("allocation failure 1 in dmatrix()", TRUE
);
107 for(i
=nrl
;i
<=nrh
;i
++) {
108 m
[i
]=(double *) malloc((unsigned) (nch
-ncl
+1)*sizeof(double));
109 if (!m
[i
]) nrerror("allocation failure 2 in dmatrix()", TRUE
);
115 static int **imatrix1(int nrl
, int nrh
, int ncl
, int nch
)
119 m
=(int **)malloc((unsigned) (nrh
-nrl
+1)*sizeof(int*));
120 if (!m
) nrerror("allocation failure 1 in imatrix1()", TRUE
);
123 for(i
=nrl
;i
<=nrh
;i
++) {
124 m
[i
]=(int *)malloc((unsigned) (nch
-ncl
+1)*sizeof(int));
125 if (!m
[i
]) nrerror("allocation failure 2 in imatrix1()", TRUE
);
133 static real
**submatrix(real
**a
, int oldrl
, int oldrh
, int oldcl
,
134 int newrl
, int newcl
)
139 m
=(real
**) malloc((unsigned) (oldrh
-oldrl
+1)*sizeof(real
*));
140 if (!m
) nrerror("allocation failure in submatrix()", TRUE
);
143 for(i
=oldrl
,j
=newrl
;i
<=oldrh
;i
++,j
++) m
[j
]=a
[i
]+oldcl
-newcl
;
150 static void free_vector(real
*v
, int nl
)
152 free((char*) (v
+nl
));
155 static void free_ivector(int *v
, int nl
)
157 free((char*) (v
+nl
));
160 static void free_dvector(int *v
, int nl
)
162 free((char*) (v
+nl
));
167 static void free_matrix(real
**m
, int nrl
, int nrh
, int ncl
)
171 for(i
=nrh
;i
>=nrl
;i
--) free((char*) (m
[i
]+ncl
));
172 free((char*) (m
+nrl
));
175 static void free_dmatrix(double **m
, int nrl
, int nrh
, int ncl
)
179 for(i
=nrh
;i
>=nrl
;i
--) free((char*) (m
[i
]+ncl
));
180 free((char*) (m
+nrl
));
183 static void free_imatrix(int **m
, int nrl
, int nrh
, int ncl
)
187 for(i
=nrh
;i
>=nrl
;i
--) free((char*) (m
[i
]+ncl
));
188 free((char*) (m
+nrl
));
193 static void free_submatrix(real
**b
, int nrl
)
195 free((char*) (b
+nrl
));
200 static real
**convert_matrix(real
*a
, int nrl
, int nrh
, int ncl
, int nch
)
207 m
= (real
**) malloc((unsigned) (nrow
)*sizeof(real
*));
208 if (!m
) nrerror("allocation failure in convert_matrix()", TRUE
);
210 for(i
=0,j
=nrl
;i
<=nrow
-1;i
++,j
++) m
[j
]=a
+ncol
*i
-ncl
;
216 static void free_convert_matrix(real
**b
, int nrl
)
218 free((char*) (b
+nrl
));
221 #define SWAP(a,b) {real temp=(a);(a)=(b);(b)=temp;}
223 static void dump_mat(int n
,real
**a
)
227 for(i
=1; (i
<=n
); i
++) {
228 for(j
=1; (j
<=n
); j
++)
229 fprintf(stderr
," %10.3f",a
[i
][j
]);
230 fprintf(stderr
,"\n");
234 bool gaussj(real
**a
, int n
, real
**b
, int m
)
236 int *indxc
,*indxr
,*ipiv
;
237 int i
,icol
=0,irow
=0,j
,k
,l
,ll
;
243 for (j
=1;j
<=n
;j
++) ipiv
[j
]=0;
250 if (fabs(a
[j
][k
]) >= big
) {
255 } else if (ipiv
[k
] > 1) {
256 nrerror("GAUSSJ: Singular Matrix-1", FALSE
);
262 for (l
=1;l
<=n
;l
++) SWAP(a
[irow
][l
],a
[icol
][l
])
263 for (l
=1;l
<=m
;l
++) SWAP(b
[irow
][l
],b
[icol
][l
])
267 if (a
[icol
][icol
] == 0.0) {
268 fprintf(stderr
,"irow = %d, icol = %d\n",irow
,icol
);
270 nrerror("GAUSSJ: Singular Matrix-2", FALSE
);
273 pivinv
=1.0/a
[icol
][icol
];
275 for (l
=1;l
<=n
;l
++) a
[icol
][l
] *= pivinv
;
276 for (l
=1;l
<=m
;l
++) b
[icol
][l
] *= pivinv
;
277 for (ll
=1;ll
<=n
;ll
++)
281 for (l
=1;l
<=n
;l
++) a
[ll
][l
] -= a
[icol
][l
]*dum
;
282 for (l
=1;l
<=m
;l
++) b
[ll
][l
] -= b
[icol
][l
]*dum
;
286 if (indxr
[l
] != indxc
[l
])
288 SWAP(a
[k
][indxr
[l
]],a
[k
][indxc
[l
]]);
290 free_ivector(ipiv
,1);
291 free_ivector(indxr
,1);
292 free_ivector(indxc
,1);
300 static void covsrt(real
**covar
, int ma
, int lista
[], int mfit
)
306 for (i
=j
+1;i
<=ma
;i
++) covar
[i
][j
]=0.0;
308 for (j
=i
+1;j
<=mfit
;j
++) {
309 if (lista
[j
] > lista
[i
])
310 covar
[lista
[j
]][lista
[i
]]=covar
[i
][j
];
312 covar
[lista
[i
]][lista
[j
]]=covar
[i
][j
];
315 for (j
=1;j
<=ma
;j
++) {
316 covar
[1][j
]=covar
[j
][j
];
319 covar
[lista
[1]][lista
[1]]=swap
;
320 for (j
=2;j
<=mfit
;j
++) covar
[lista
[j
]][lista
[j
]]=covar
[1][j
];
322 for (i
=1;i
<=j
-1;i
++) covar
[i
][j
]=covar
[j
][i
];
325 #define SWAP(a,b) {swap=(a);(a)=(b);(b)=swap;}
327 static void covsrt_new(real
**covar
,int ma
, int ia
[], int mfit
)
328 /* Expand in storage the covariance matrix covar, so as to take
329 * into account parameters that are being held fixed. (For the
330 * latter, return zero covariances.)
335 for (i
=mfit
+1;i
<=ma
;i
++)
336 for (j
=1;j
<=i
;j
++) covar
[i
][j
]=covar
[j
][i
]=0.0;
338 for (j
=ma
;j
>=1;j
--) {
340 for (i
=1;i
<=ma
;i
++) SWAP(covar
[i
][k
],covar
[i
][j
])
341 for (i
=1;i
<=ma
;i
++) SWAP(covar
[k
][i
],covar
[j
][i
])
348 static void mrqcof(real x
[], real y
[], real sig
[], int ndata
, real a
[],
349 int ma
, int lista
[], int mfit
,
350 real
**alpha
, real beta
[], real
*chisq
,
351 void (*funcs
)(real
,real
*,real
*,real
*))
354 real ymod
,wt
,sig2i
,dy
,*dyda
;
357 for (j
=1;j
<=mfit
;j
++) {
358 for (k
=1;k
<=j
;k
++) alpha
[j
][k
]=0.0;
362 for (i
=1;i
<=ndata
;i
++) {
363 (*funcs
)(x
[i
],a
,&ymod
,dyda
);
364 sig2i
=1.0/(sig
[i
]*sig
[i
]);
366 for (j
=1;j
<=mfit
;j
++) {
367 wt
=dyda
[lista
[j
]]*sig2i
;
369 alpha
[j
][k
] += wt
*dyda
[lista
[k
]];
372 (*chisq
) += dy
*dy
*sig2i
;
374 for (j
=2;j
<=mfit
;j
++)
375 for (k
=1;k
<=j
-1;k
++) alpha
[k
][j
]=alpha
[j
][k
];
380 bool mrqmin(real x
[], real y
[], real sig
[], int ndata
, real a
[],
381 int ma
, int lista
[], int mfit
,
382 real
**covar
, real
**alpha
, real
*chisq
,
383 void (*funcs
)(real
,real
*,real
*,real
*),
387 static real
*da
,*atry
,**oneda
,*beta
,ochisq
;
390 oneda
=matrix1(1,mfit
,1,1);
395 for (j
=1;j
<=ma
;j
++) {
397 for (k
=1;k
<=mfit
;k
++)
398 if (lista
[k
] == j
) ihit
++;
402 nrerror("Bad LISTA permutation in MRQMIN-1", FALSE
);
407 nrerror("Bad LISTA permutation in MRQMIN-2", FALSE
);
411 mrqcof(x
,y
,sig
,ndata
,a
,ma
,lista
,mfit
,alpha
,beta
,chisq
,funcs
);
414 for (j
=1;j
<=mfit
;j
++) {
415 for (k
=1;k
<=mfit
;k
++) covar
[j
][k
]=alpha
[j
][k
];
416 covar
[j
][j
]=alpha
[j
][j
]*(1.0+(*alamda
));
419 if (!gaussj(covar
,mfit
,oneda
,1))
421 for (j
=1;j
<=mfit
;j
++)
423 if (*alamda
== 0.0) {
424 covsrt(covar
,ma
,lista
,mfit
);
428 free_matrix(oneda
,1,mfit
,1);
431 for (j
=1;j
<=ma
;j
++) atry
[j
]=a
[j
];
432 for (j
=1;j
<=mfit
;j
++)
433 atry
[lista
[j
]] = a
[lista
[j
]]+da
[j
];
434 mrqcof(x
,y
,sig
,ndata
,atry
,ma
,lista
,mfit
,covar
,da
,chisq
,funcs
);
435 if (*chisq
< ochisq
) {
438 for (j
=1;j
<=mfit
;j
++) {
439 for (k
=1;k
<=mfit
;k
++) alpha
[j
][k
]=covar
[j
][k
];
441 a
[lista
[j
]]=atry
[lista
[j
]];
451 bool mrqmin_new(real x
[],real y
[],real sig
[],int ndata
,real a
[],
452 int ia
[],int ma
,real
**covar
,real
**alpha
,real
*chisq
,
453 void (*funcs
)(real
, real
[], real
*, real
[]),
455 /* Levenberg-Marquardt method, attempting to reduce the value Chi^2
456 * of a fit between a set of data points x[1..ndata], y[1..ndata]
457 * with individual standard deviations sig[1..ndata], and a nonlinear
458 * function dependent on ma coefficients a[1..ma]. The input array
459 * ia[1..ma] indicates by nonzero entries those components of a that
460 * should be fitted for, and by zero entries those components that
461 * should be held fixed at their input values. The program returns
462 * current best-fit values for the parameters a[1..ma], and
463 * Chi^2 = chisq. The arrays covar[1..ma][1..ma], alpha[1..ma][1..ma]
464 * are used as working space during most iterations. Supply a routine
465 * funcs(x,a,yfit,dyda,ma) that evaluates the fitting function yfit,
466 * and its derivatives dyda[1..ma] with respect to the fitting
467 * parameters a at x. On the first call provide an initial guess for
468 * the parameters a, and set alamda < 0 for initialization (which then
469 * sets alamda=.001). If a step succeeds chisq becomes smaller and
470 * alamda de-creases by a factor of 10. If a step fails alamda grows by
471 * a factor of 10. You must call this routine repeatedly until
472 * convergence is achieved. Then, make one final call with alamda=0,
473 * so that covar[1..ma][1..ma] returns the covariance matrix, and alpha
474 * the curvature matrix.
475 * (Parameters held fixed will return zero covariances.)
478 void covsrt(real
**covar
, int ma
, int ia
[], int mfit
);
479 bool gaussj(real
**a
, int n
, real
**b
,int m
);
480 void mrqcof_new(real x
[], real y
[], real sig
[], int ndata
, real a
[],
481 int ia
[], int ma
, real
**alpha
, real beta
[], real
*chisq
,
482 void (*funcs
)(real
, real
[], real
*, real
[]));
485 static real ochisq
,*atry
,*beta
,*da
,**oneda
;
487 if (*alamda
< 0.0) { /* Initialization. */
491 for (mfit
=0,j
=1;j
<=ma
;j
++)
493 oneda
=matrix1(1,mfit
,1,1);
495 mrqcof_new(x
,y
,sig
,ndata
,a
,ia
,ma
,alpha
,beta
,chisq
,funcs
);
500 for (j
=1;j
<=mfit
;j
++) { /* Alter linearized fitting matrix, by augmenting. */
501 for (k
=1;k
<=mfit
;k
++)
502 covar
[j
][k
]=alpha
[j
][k
]; /* diagonal elements. */
503 covar
[j
][j
]=alpha
[j
][j
]*(1.0+(*alamda
));
506 if (!gaussj(covar
,mfit
,oneda
,1)) /* Matrix solution. */
508 for (j
=1;j
<=mfit
;j
++)
510 if (*alamda
== 0.0) { /* Once converged, evaluate covariance matrix. */
511 covsrt_new(covar
,ma
,ia
,mfit
);
512 free_matrix(oneda
,1,mfit
,1);
518 for (j
=0,l
=1;l
<=ma
;l
++) /* Did the trial succeed? */
519 if (ia
[l
]) atry
[l
]=a
[l
]+da
[++j
];
520 mrqcof_new(x
,y
,sig
,ndata
,atry
,ia
,ma
,covar
,da
,chisq
,funcs
);
521 if (*chisq
< ochisq
) {
522 /* Success, accept the new solution. */
525 for (j
=1;j
<=mfit
;j
++) {
526 for (k
=1;k
<=mfit
;k
++) alpha
[j
][k
]=covar
[j
][k
];
529 for (l
=1;l
<=ma
;l
++) a
[l
]=atry
[l
];
530 } else { /* Failure, increase alamda and return. */
537 void mrqcof_new(real x
[], real y
[], real sig
[], int ndata
, real a
[],
538 int ia
[], int ma
, real
**alpha
, real beta
[], real
*chisq
,
539 void (*funcs
)(real
, real
[], real
*, real
[]))
540 /* Used by mrqmin to evaluate the linearized fitting matrix alpha, and
541 * vector beta as in (15.5.8), and calculate Chi^2.
544 int i
,j
,k
,l
,m
,mfit
=0;
545 real ymod
,wt
,sig2i
,dy
,*dyda
;
550 for (j
=1;j
<=mfit
;j
++) { /* Initialize (symmetric) alpha), beta. */
551 for (k
=1;k
<=j
;k
++) alpha
[j
][k
]=0.0;
555 for (i
=1;i
<=ndata
;i
++) { /* Summation loop over all data. */
556 (*funcs
)(x
[i
],a
,&ymod
,dyda
);
557 sig2i
=1.0/(sig
[i
]*sig
[i
]);
559 for (j
=0,l
=1;l
<=ma
;l
++) {
562 for (j
++,k
=0,m
=1;m
<=l
;m
++)
563 if (ia
[m
]) alpha
[j
][++k
] += wt
*dyda
[m
];
567 *chisq
+= dy
*dy
*sig2i
; /* And find Chi^2. */
569 for (j
=2;j
<=mfit
;j
++) /* Fill in the symmetric side. */
570 for (k
=1;k
<j
;k
++) alpha
[k
][j
]=alpha
[j
][k
];