斐波那契法论文

1、1方法原理介绍及最优性证明1.1斐波纳契法对于一维搜索，斐波那契数列法曾作为一种算法而呈现它在计算过程中的最优性， 卜面我先介绍一下此算法。假定f(x)在区间a,b上是单峰函数，即f(x)在a,b上只有一个极值点X*，若它是极小点， 则f(x)在X*左边严格单减，而f(x)在X*右边严格单增。如果我们打算通过某种取点方式只计 算n次函数值，就将f(x)在a,b上的近似极小点求出来(严格地讲是把极小点存在的区间长 度缩到最小)，那么我们可以按照下面的办法即斐波那契(数列)法:取x1 = a + (b a)，x1 = a + (ba)，计算 f(x1 )和 f(Xp TOC o 1-5 h z n

2、n若 f(X)Mf(Xp，则置a1= a，b1=X；若 f(x1) /(X；)，则置a1=我们在新区间忸内上仿上面办法插入点a】 +%L(b a )，x = + 1 121Fn11121( a1)，重复上面的做法可得a2,b2，如此做下去。我有必要指出以下三点： (1)每迭代一次新区间的长度为原来区间长的写(k =1,2.n 1)Fnk+1比如第一次迭代，注意到x1a = FF1-(ba)，b x = b-E (b a) + a =21 L F ， F(bFa) = (bna)结论便是显然的了，对于后面的计算，道理同上。(2)每迭代一步，区间缩小后保留的点，在下步迭代中还可使用。在第二步迭代中

3、，必有下面四种情况之一发生乂1 = x2，x1 = x2，x1 = X2，x1 =文2 容易验证：当f(x1) y(x1)时，x2=x1。这说明保留的点与新 插入的点之一重合，即在第二步迭代中只需计算3个点的值。类似的，第n-1步迭代只需计算n个点的函数值，而且容易算出，这是区间an-1，bn-1gm% =WTJ (b a) = J (bF2Fna)=工(b a)Fnan2)，1 =an2 +(bn2*2)F2(3)进行n-1步迭代时，x = a+ E (bn1 n2F2 n2这样xn1 = xn1 = 1 (an2 + bn2 )，这时无法比较函数值f(xn1 )与f(xn1 )来确定最后的

4、区 间an-1，bn-1。为此取Xn_i = ；（an-2 +bn-2），其中6是一个很小的正数，这样就可以比较f（x J X = x+6n-1n-1n-1与f（Xp的值以确定最后的区间an-1，bn-1，取.（an-j + bn-j）为近似极小点，相应的函数 值为近似极小值。1.2斐波那契法最优性证明对于单峰函数来讲，它是最优的。设Ln为某区间的长度：它使按某种取点方式求n 次函数值后，在可能遇到的各种情况下，总能把新区间（又称搜索区间）的长度缩为1，最 优取点方式应保证使Ln最大。设Lk的上确界为uk（k=1,2，n）。显然，uk就是计算第k次函数值总能把搜索区间 缩短到1的最大区间长度，

5、由于要计算两次函数值后才能缩短区间，故=%=1。今估计对应于计算n次函数值的上界un.设最初的两个试探点为X和x2（x1 x2），则余下来还可以计算n-2次函数值。极小点可能位于区间a，X，也可能位于区间X，b。当极小点位于a，x1时，我们必 须借助于在其中计算n-2次函数值，把该区间缩短为1，故应有x1 - a un_2。当极小点位于X，b上时，除了可再计算n-2次函数值外，还能利用其中已计算的一点 x2处的函数值，所以总共可以利用（n-2）+1=n-1次函数值，故应有b-XjMUnT于是我们有、= b-a Un-2 +Un-1，故 Un = Un-2 +Un-1由斐波那契数列取点法及上面的

6、推算，知该算法经n次函数求值解保证把搜索区间缩为 原来的工，从而它是最优的。Fn我们有必要说明一点，以上所谓的斐波那契法最优性的证明，是指取点方式为两个试探 点的情况下，斐波那契法是最优的。1.3黄金分割法斐波那契法可以衍生到黄金分割法，为什么这么说呢，如果我们用斐波那契法以n lim = 0.6180339874189848,于是，我们不妨以不变的区间缩短率0.618代替斐波那契 nT8 Fn个试点来缩短某一区间时，缩短率分别为厂，F，?。我们知道，当n 8时，法每次不同的缩短率，就得到黄金分割法，也称0.618法，它可以看成斐波那契法的近似， 实现起来较容易。下面我给出一个直观的说明：为了

7、方便起见，我们把区间长度（试验范围）视为1，即区间0，1。如下图所示为比较结果，我们至少要取两点c, C1,计算函数值后，可能去掉区间0, C或c1,1，因去掉的区间希望是相等的，这样下一次比0CC1较时可少算一点的函数值，故应适合关系式c=1- c此即说c，c1是两个对称点。若计算比较后去掉（勺1，留下0，cj，而点c应为0，cj中位置与c1在0，1中所处位置的点，即它们的比应相等，即：1：上=%:。与c2=c又由c=1- c 从而有c2 + C-1 = 0。解得 =气-1（只取正根）。1.4算例分析例：用多种一维搜索方法（如斐波那契法、黄金分割法、二次插值法、二分法）求函数f（x）=X4

8、- 4x3 - 6x2 - 16x + 4在区间-1，6上的极小点，并要求误差不超过10-3。解：用斐波那契法的程序见附录1迭代次数为20次，极小点x=3.9996。用黄金分割法的程序见附录2迭代次数为21次，极小点x=3.9966。用二次插值法的程序见附录5迭代次数为15次，极小点x=3.9981。用二分法的程序见附录6迭代次数为13次，极小点x=4.0001。下面我们换个角度再来看一下此问题，我们固定迭代次数，比较各个方法的误差，得到如下 图1所示图像。在上图中，横坐标代表迭代次数，纵坐标代表误差。从上往下看，第一条线表示用黄金 分割法的情形，第二条线表示用斐波那契法的情形，第三条线表示用二次插值法的情形，第 四条线表示用二分法的情形。我们从图中也可以看出，对于每一步插入两个试探点的情况，斐波那契法略好于黄金分 割法，至于二分法，因其每一步只插入一个试探点，收敛速度或2)n，其图像也是位于以上 所有图像的最下端，故它优于其他三种方法。1.5优缺点一维搜