Geant4  10.02.p01
G4PolynomialSolver.icc
Go to the documentation of this file.
1 //
2 // ********************************************************************
3 // * License and Disclaimer *
4 // * *
5 // * The Geant4 software is copyright of the Copyright Holders of *
6 // * the Geant4 Collaboration. It is provided under the terms and *
7 // * conditions of the Geant4 Software License, included in the file *
8 // * LICENSE and available at http://cern.ch/geant4/license . These *
9 // * include a list of copyright holders. *
10 // * *
11 // * Neither the authors of this software system, nor their employing *
12 // * institutes,nor the agencies providing financial support for this *
13 // * work make any representation or warranty, express or implied, *
14 // * regarding this software system or assume any liability for its *
15 // * use. Please see the license in the file LICENSE and URL above *
16 // * for the full disclaimer and the limitation of liability. *
17 // * *
18 // * This code implementation is the result of the scientific and *
19 // * technical work of the GEANT4 collaboration. *
20 // * By using, copying, modifying or distributing the software (or *
21 // * any work based on the software) you agree to acknowledge its *
22 // * use in resulting scientific publications, and indicate your *
23 // * acceptance of all terms of the Geant4 Software license. *
24 // ********************************************************************
25 //
26 //
27 // $Id: G4PolynomialSolver.icc 67970 2013-03-13 10:10:06Z gcosmo $
28 //
29 // class G4PolynomialSolver
30 //
31 // 19.12.00 E.Medernach, First implementation
32 //
33 
34 #define POLEPSILON 1e-12
35 #define POLINFINITY 9.0E99
36 #define ITERATION 12 // 20 But 8 is really enough for Newton with a good guess
37 
38 template <class T, class F>
39 G4PolynomialSolver<T,F>::G4PolynomialSolver (T* typeF, F func, F deriv,
40  G4double precision)
41 {
42  Precision = precision ;
43  FunctionClass = typeF ;
44  Function = func ;
45  Derivative = deriv ;
46 }
47 
48 template <class T, class F>
49 G4PolynomialSolver<T,F>::~G4PolynomialSolver ()
50 {
51 }
52 
53 template <class T, class F>
54 G4double G4PolynomialSolver<T,F>::solve(G4double IntervalMin,
55  G4double IntervalMax)
56 {
57  return Newton(IntervalMin,IntervalMax);
58 }
59 
60 
61 /* If we want to be general this could work for any
62  polynomial of order more that 4 if we find the (ORDER + 1)
63  control points
64 */
65 #define NBBEZIER 5
66 
67 template <class T, class F>
68 G4int
69 G4PolynomialSolver<T,F>::BezierClipping(/*T* typeF,F func,F deriv,*/
70  G4double *IntervalMin,
71  G4double *IntervalMax)
72 {
73  /** BezierClipping is a clipping interval Newton method **/
74  /** It works by clipping the area where the polynomial is **/
75 
76  G4double P[NBBEZIER][2],D[2];
77  G4double NewMin,NewMax;
78 
79  G4int IntervalIsVoid = 1;
80 
81  /*** Calculating Control Points ***/
82  /* We see the polynomial as a Bezier curve for some control points to find */
83 
84  /*
85  For 5 control points (polynomial of degree 4) this is:
86 
87  0 p0 = F((*IntervalMin))
88  1/4 p1 = F((*IntervalMin)) + ((*IntervalMax) - (*IntervalMin))/4
89  * F'((*IntervalMin))
90  2/4 p2 = 1/6 * (16*F(((*IntervalMax) + (*IntervalMin))/2)
91  - (p0 + 4*p1 + 4*p3 + p4))
92  3/4 p3 = F((*IntervalMax)) - ((*IntervalMax) - (*IntervalMin))/4
93  * F'((*IntervalMax))
94  1 p4 = F((*IntervalMax))
95  */
96 
97  /* x,y,z,dx,dy,dz are constant during searching */
98 
99  D[0] = (FunctionClass->*Derivative)(*IntervalMin);
100 
101  P[0][0] = (*IntervalMin);
102  P[0][1] = (FunctionClass->*Function)(*IntervalMin);
103 
104 
105  if (std::fabs(P[0][1]) < Precision) {
106  return 1;
107  }
108 
109  if (((*IntervalMax) - (*IntervalMin)) < POLEPSILON) {
110  return 1;
111  }
112 
113  P[1][0] = (*IntervalMin) + ((*IntervalMax) - (*IntervalMin))/4;
114  P[1][1] = P[0][1] + (((*IntervalMax) - (*IntervalMin))/4.0) * D[0];
115 
116  D[1] = (FunctionClass->*Derivative)(*IntervalMax);
117 
118  P[4][0] = (*IntervalMax);
119  P[4][1] = (FunctionClass->*Function)(*IntervalMax);
120 
121  P[3][0] = (*IntervalMax) - ((*IntervalMax) - (*IntervalMin))/4;
122  P[3][1] = P[4][1] - ((*IntervalMax) - (*IntervalMin))/4 * D[1];
123 
124  P[2][0] = ((*IntervalMax) + (*IntervalMin))/2;
125  P[2][1] = (16*(FunctionClass->*Function)(((*IntervalMax)+(*IntervalMin))/2)
126  - (P[0][1] + 4*P[1][1] + 4*P[3][1] + P[4][1]))/6 ;
127 
128  {
129  G4double Intersection ;
130  G4int i,j;
131 
132  NewMin = (*IntervalMax) ;
133  NewMax = (*IntervalMin) ;
134 
135  for (i=0;i<5;i++)
136  for (j=i+1;j<5;j++)
137  {
138  /* there is an intersection only if each have different signs */
139  if (((P[j][1] > -Precision) && (P[i][1] < Precision)) ||
140  ((P[j][1] < Precision) && (P[i][1] > -Precision))) {
141  IntervalIsVoid = 0;
142  Intersection = P[j][0] - P[j][1]*((P[i][0] - P[j][0])/
143  (P[i][1] - P[j][1]));
144  if (Intersection < NewMin) {
145  NewMin = Intersection;
146  }
147  if (Intersection > NewMax) {
148  NewMax = Intersection;
149  }
150  }
151  }
152 
153 
154  if (IntervalIsVoid != 1) {
155  (*IntervalMax) = NewMax;
156  (*IntervalMin) = NewMin;
157  }
158  }
159 
160  if (IntervalIsVoid == 1) {
161  return -1;
162  }
163 
164  return 0;
165 }
166 
167 template <class T, class F>
168 G4double G4PolynomialSolver<T,F>::Newton (G4double IntervalMin,
169  G4double IntervalMax)
170 {
171  /* So now we have a good guess and an interval where
172  if there are an intersection the root must be */
173 
174  G4double Value = 0;
175  G4double Gradient = 0;
176  G4double Lambda ;
177 
178  G4int i=0;
179  G4int j=0;
180 
181 
182  /* Reduce interval before applying Newton Method */
183  {
184  G4int NewtonIsSafe ;
185 
186  while ((NewtonIsSafe = BezierClipping(&IntervalMin,&IntervalMax)) == 0) ;
187 
188  if (NewtonIsSafe == -1) {
189  return POLINFINITY;
190  }
191  }
192 
193  Lambda = IntervalMin;
194  Value = (FunctionClass->*Function)(Lambda);
195 
196 
197  // while ((std::fabs(Value) > Precision)) {
198  while (j != -1) {
199 
200  Value = (FunctionClass->*Function)(Lambda);
201 
202  Gradient = (FunctionClass->*Derivative)(Lambda);
203 
204  Lambda = Lambda - Value/Gradient ;
205 
206  if (std::fabs(Value) <= Precision) {
207  j ++;
208  if (j == 2) {
209  j = -1;
210  }
211  } else {
212  i ++;
213 
214  if (i > ITERATION)
215  return POLINFINITY;
216  }
217  }
218  return Lambda ;
219 }