Package minfx :: Package line_search :: Module interpolate
[hide private]
[frames] | no frames]

Source Code for Module minfx.line_search.interpolate

  1  ############################################################################### 
  2  #                                                                             # 
  3  # Copyright (C) 2003-2013 Edward d'Auvergne                                   # 
  4  #                                                                             # 
  5  # This file is part of the minfx optimisation library,                        # 
  6  # https://sourceforge.net/projects/minfx                                      # 
  7  #                                                                             # 
  8  # This program is free software: you can redistribute it and/or modify        # 
  9  # it under the terms of the GNU General Public License as published by        # 
 10  # the Free Software Foundation, either version 3 of the License, or           # 
 11  # (at your option) any later version.                                         # 
 12  #                                                                             # 
 13  # This program is distributed in the hope that it will be useful,             # 
 14  # but WITHOUT ANY WARRANTY; without even the implied warranty of              # 
 15  # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               # 
 16  # GNU General Public License for more details.                                # 
 17  #                                                                             # 
 18  # You should have received a copy of the GNU General Public License           # 
 19  # along with this program.  If not, see <http://www.gnu.org/licenses/>.       # 
 20  #                                                                             # 
 21  ############################################################################### 
 22   
 23  # Module docstring. 
 24  """Quadratic and cubic interpolation method. 
 25   
 26  This file is part of the U{minfx optimisation library<https://sourceforge.net/projects/minfx>}. 
 27  """ 
 28   
 29  # Python module imports. 
 30  from math import sqrt 
 31   
 32   
33 -def cubic_int(a, b, fa, fb, ga, gb):
34 """Cubic interpolation using f(a), f(b), g(a), and g(b). 35 36 Equations 37 ========= 38 39 The equations used are:: 40 41 f(a) = a'a**3 + b'a**2 + c'a + d' 42 f(b) = a'b**3 + b'b**2 + c'b + d' 43 g(a) = 3a'a**2 + 2b'a + c' 44 g(b) = 3a'b**2 + 2b'b + c' 45 46 47 Interpolation 48 ============= 49 50 The extrema are the roots of the quadratic equation:: 51 52 3a'*alpha**2 + 2b'*alpha + c' = 0 53 54 The cubic interpolant is given by the formula:: 55 56 g(b) + beta2 - beta1 57 ac = b - (b - a) . --------------------- 58 g(b) - g(a) + 2*beta2 59 60 where:: 61 62 f(a) - f(b) 63 beta1 = g(a) + g(b) - 3 . ----------- 64 a - b 65 66 if a < b: 67 68 beta2 = sqrt(beta1**2 - g(a).g(b)) 69 70 else: 71 72 beta2 = -sqrt(beta1**2 - g(a).g(b)) 73 """ 74 75 76 beta1 = ga + gb - 3.0*(fa - fb)/(a - b) 77 if a < b: 78 beta2 = sqrt(beta1**2 - ga*gb) 79 else: 80 beta2 = -sqrt(beta1**2 - ga*gb) 81 82 denom = gb - ga + 2.0*beta2 83 if denom == 0.0: 84 return -1e99 85 else: 86 return b - (b - a)*(gb + beta2 - beta1)/denom
87 88
89 -def cubic_ext(a, b, fa, fb, ga, gb, full_output=0):
90 """Cubic Extrapolation using f(a), f(b), g(a), and g(b). 91 92 Extrapolation 93 ============= 94 95 The extrema are the roots of the quadratic equation:: 96 97 3a'*alpha**2 + 2b'*alpha + c' = 0 98 99 The cubic extrapolant is given by the formula:: 100 101 g(b) + beta2 - beta1 102 ac = b - (b - a) . --------------------- 103 g(b) - g(a) + 2*beta2 104 105 where:: 106 107 f(a) - f(b) 108 beta1 = g(a) + g(b) - 3 . ----------- 109 a - b 110 111 if a < b: 112 113 beta2 = sqrt(max(0.0, beta1**2 - g(a).g(b))) 114 115 else: 116 117 beta2 = -sqrt(max(0.0, beta1**2 - g(a).g(b))) 118 """ 119 120 121 beta1 = ga + gb - 3.0*(fa - fb)/(a - b) 122 if a < b: 123 beta2 = sqrt(max(0.0, beta1**2 - ga*gb)) 124 else: 125 beta2 = -sqrt(max(0.0, beta1**2 - ga*gb)) 126 127 denom = gb - ga + 2.0*beta2 128 if denom == 0.0: 129 alpha = -1e99 130 else: 131 alpha = b - (b - a)*(gb + beta2 - beta1)/denom 132 133 if full_output: 134 return alpha, beta1, beta2 135 else: 136 return alpha
137 138
139 -def quadratic_fafbga(a, b, fa, fb, ga):
140 """Quadratic interpolation using f(a), f(b), and g(a). 141 142 The extremum of the quadratic is given by:: 143 144 1 g(a) 145 aq = a + - . ------------------------- 146 2 f(a) - f(b) - (a - b)g(a) 147 """ 148 149 denom = fa - fb - (a - b)*ga 150 if denom == 0.0: 151 return 1e99 152 else: 153 return a + 0.5 * ga / denom
154 155
156 -def quadratic_gagb(a, b, ga, gb):
157 """Quadratic interpolation using g(a) and g(b). 158 159 The extremum of the quadratic is given by:: 160 161 bg(a) - ag(b) 162 aq = ------------- 163 g(a) - g(b) 164 """ 165 166 denom = ga - gb 167 if denom == 0.0: 168 return 1e99 169 else: 170 return (b*ga - a*gb) / denom
171