GRASS GIS 8 Programmer's Manual  8.5.0dev(2024)-9af255a3cc
brent.c
Go to the documentation of this file.
1 /* min/brent.c
2  *
3  * Copyright (C) 1996, 1997, 1998, 1999, 2000 Brian Gough
4  *
5  * Taken from 'GSL - The GNU Scientific Library':
6  * "One dimensional Minimization"
7  * http://sources.redhat.com/gsl/
8  * modified by Stefano Menegon 2004
9  *
10  * This program is free software; you can redistribute it and/or modify
11  * it under the terms of the GNU General Public License as published by
12  * the Free Software Foundation; either version 2 of the License, or (at
13  * your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful, but
16  * WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18  * General Public License for more details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with this program; if not, write to the Free Software
22  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
23  */
24 
25 #include <stdlib.h>
26 #include <stdio.h>
27 #include <math.h>
28 #include <float.h>
29 
30 #define GSL_SQRT_DBL_EPSILON 1.e-4
31 #define GSL_DBL_EPSILON 1.e-8
32 
33 /*
34  #define SAFE_FUNC_CALL(f, x, yp) \
35  do { \
36  *yp = GSL_FN_EVAL(f,x); \
37  if (!finite(*yp)) \
38  fprintf(stderr,"function not continuous\n");\
39  } while (0)
40  */
41 
42 typedef struct {
43  double d, e, v, w;
44  double f_v, f_w;
45 } brent_state_t;
46 
47 static int brent(void *vstate, double (*f)(double), double *x_minimum,
48  double *f_minimum, double *x_lower, double *f_lower,
49  double *x_upper, double *f_upper)
50 {
51  brent_state_t *state = (brent_state_t *)vstate;
52 
53  const double x_left = *x_lower;
54  const double x_right = *x_upper;
55 
56  const double z = *x_minimum;
57  double d = state->e;
58  double e = state->d;
59  double u, f_u;
60  const double v = state->v;
61  const double w = state->w;
62  const double f_v = state->f_v;
63  const double f_w = state->f_w;
64  const double f_z = *f_minimum;
65 
66  const double golden = 0.3819660; /* golden = (3 - sqrt(5))/2 */
67 
68  const double w_lower = (z - x_left);
69  const double w_upper = (x_right - z);
70 
71  const double tolerance = GSL_SQRT_DBL_EPSILON * fabs(z);
72 
73  double p = 0, q = 0, r = 0;
74 
75  const double midpoint = 0.5 * (x_left + x_right);
76 
77  if (fabs(e) > tolerance) {
78  /* fit parabola */
79 
80  r = (z - w) * (f_z - f_v);
81  q = (z - v) * (f_z - f_w);
82  p = (z - v) * q - (z - w) * r;
83  q = 2 * (q - r);
84 
85  if (q > 0) {
86  p = -p;
87  }
88  else {
89  q = -q;
90  }
91 
92  r = e;
93  e = d;
94  }
95 
96  if (fabs(p) < fabs(0.5 * q * r) && p < q * w_lower && p < q * w_upper) {
97  double t2 = 2 * tolerance;
98 
99  d = p / q;
100  u = z + d;
101 
102  if ((u - x_left) < t2 || (x_right - z) < t2) {
103  d = (z < midpoint) ? tolerance : -tolerance;
104  }
105  }
106  else {
107  e = (z < midpoint) ? x_right - z : -(z - x_left);
108  d = golden * e;
109  }
110 
111  if (fabs(d) >= tolerance) {
112  u = z + d;
113  }
114  else {
115  u = z + ((d > 0) ? tolerance : -tolerance);
116  }
117 
118  state->e = e;
119  state->d = d;
120 
121  /* SAFE_FUNC_CALL(f, u, &f_u); */
122  f_u = (*f)(u);
123 
124  if (f_u > f_z) {
125  if (u < z) {
126  *x_lower = u;
127  *f_lower = f_u;
128  return 0;
129  }
130  else {
131  *x_upper = u;
132  *f_upper = f_u;
133  return 0;
134  }
135  }
136  else if (f_u < f_z) {
137  if (u < z) {
138  *x_upper = z;
139  *f_upper = f_z;
140  }
141  else {
142  *x_lower = z;
143  *f_lower = f_z;
144  }
145 
146  state->v = w;
147  state->f_v = f_w;
148  state->w = z;
149  state->f_w = f_z;
150  *x_minimum = u;
151  *f_minimum = f_u;
152  return 0;
153  }
154  else if (f_u <= f_w || w == z) {
155  state->v = w;
156  state->f_v = f_w;
157  state->w = u;
158  state->f_w = f_u;
159  return 0;
160  }
161  else if (f_u <= f_v || v == z || v == w) {
162  state->v = u;
163  state->f_v = f_u;
164  return 0;
165  }
166  else {
167  return -1;
168  }
169 }
170 
171 /* Code modified by Stefano Menegon 1st of February 2004 */
172 
173 double brent_iterate(double (*f)(double), double x_lower, double x_upper,
174  int maxiter)
175 {
176  int i;
177  double x_minimum = (x_upper + x_lower) / 2.;
178  double f_minimum;
179  double f_lower;
180  double f_upper;
181 
182  /* stato iterazione */
183  brent_state_t itstate;
184  const double golden = 0.3819660; /* golden = (3 - sqrt(5))/2 */
185  double v = x_lower + golden * (x_upper - x_lower);
186  double w = v;
187  double f_vw;
188 
189  f_lower = (*f)(x_lower);
190  f_upper = (*f)(x_upper);
191  f_minimum = (*f)(x_minimum);
192 
193  itstate.v = v;
194  itstate.w = w;
195 
196  itstate.d = 0.;
197  itstate.e = 0.;
198 
199  /* SAFE_FUNC_CALL (f, v, &f_vw); */
200 
201  f_vw = (*f)(v);
202 
203  itstate.f_v = f_vw;
204  itstate.f_w = f_vw;
205 
206  for (i = 0; i < maxiter; i++) {
207  brent(&itstate, f, &x_minimum, &f_minimum, &x_lower, &f_lower, &x_upper,
208  &f_upper);
209  if (fabs(f_upper - f_lower) < GSL_DBL_EPSILON * fabs(f_minimum)) {
210  return x_minimum;
211  }
212  }
213 
214  return x_minimum;
215 }
#define GSL_SQRT_DBL_EPSILON
Definition: brent.c:30
#define GSL_DBL_EPSILON
Definition: brent.c:31
double brent_iterate(double(*f)(double), double x_lower, double x_upper, int maxiter)
Definition: brent.c:173
struct state state
Definition: parser.c:103
double r
Definition: r_raster.c:39