下面我们考虑任给一个f(x)的单峰区间g2b 如果给定试点的个数n,如何使最后确定的包含 最优值的区间尽量的小。 另外一种思维方式为,按什么方式取点 求n次函数值之后,可最多将多长的原始区间 长度缩小为1.设L为试点个数为n,最终区间 长度为1时,原始区间[,的最大可能长度
下面我们考虑任给一个 另外一种思维方式为， f (x) 的单峰区间 a,b, 如果给定试点的个数 n , 如何使最后确定的包含 最优值的区间尽量的小。 按什么方式取点， 求 n 次函数值之后， 可最多将多长的原始区间 长度缩小为 1. 设 Ln 为试点个数为 n , 最终区间 长度为 1 时，原始区间 a,b 的最大可能长度
设最初两个试点为x1和x2 若极小点在叵,x]内,至多还有n-2个试点, 则x1-a≤L 若极小点在区,b内,包括x2在内可以有n-1 个试点,则b-x1≤Ln1 因此,Ln≤Ln1+ln2, 如果我们采取合适的技巧,可以使得 Ln=Ln1+L-2,另外,显然,D=L1=1
设最初两个试点为 1 x 和 , 2 x 若极小点在 1 a, x 内，至多还有 n − 2 个试点， 则 , 1 − Ln−2 x a 若极小点在 x ,b 1 内，包括 2 x 在内可以有 n −1 个试点，则 , − 1 Ln−1 b x 因此， , Ln Ln−1 + Ln−2 如果我们采取合适的技巧，可以使得： , Ln = Ln−1 + Ln−2 另外，显然， 1. L0 = L1 =
从而L满足差分方程: Lo=L=l 此为 fibonacci数列,一般写为 Fn=Fn1+F2(n≥2) F=F=1
从而 Ln 满足差分方程： ( ) = = = − + − 1 2 0 1 1 2 L L L L L n n n n 此为Fibonacci数列，一般写为： ( ) = = = − + − 1 2 0 1 1 2 F F F F F n n n n
若原始区间为ab要求最终区间长度≤ 则F≥ b-a 由此可确定n,区间缩短之后与 之前的比依次为:Fn1F=232 n确定之后,最初两个试点分别为 F x1=a+-2 F =a+ x1x2关于b对称
若原始区间为 a,b, 要求最终区间长度 , 则 , b a Fn − 由此可确定 n , 区间缩短之后与 之前的比依次为： 2 1 , 3 2 , 5 3 , , , 1 1 2 − − − n n n n F F F F n 确定之后，最初两个试点分别为： ( ) (b a) F F b a x a F F x a n n n n = + − = + − − −1 2 2 1 1 2 x , x 关于 a,b 对称
上述过程完成了依次迭代,新区间仍记为[a,b] 若已经进行了i-1次迭代,第讠次迭代时,还有 n-i+1个试点(包括已经计算过的函数值的一个 x1=a+ a x,=a+ 注意:(1)最后的两个试点的选取方式: b-a)/2,x2=x1+0 (2)若在一定的误差范围内f(x)=f(x2) 则认为x在[x1,x]内
上述过程完成了依次迭代，新区间仍记为 i −1 a,b 若已经进行了 次迭代，第 i 次迭代时，还有 n −i +1 个试点（包括已经计算过的函数值的一个） ( ) (b a) F F b a x a F F x a n i n i n i n i = + − = + − − + − − + − − 1 2 1 1 1 注意： （２）若在一定的误差范围内， ( ) ( ), 1 2 f x = f x 则认为 * x 在 1 2 x , x 内 （１）最后的两个试点的选取方式： x = (b−a)/ 2, x = x +0.1(b−a) 1 2 1