Fibonacci法

斐波那契法和二次插值法小组成员：王娜王慧红郭茜茜解悦曹文彦苏鹏应用领域：（1）可以用斐波那契数列的寻优方法来计算交流电机驱动系统的效率，该方法的突出特点是与损耗模型无关，并能使系统快速达到效率最大工作点.（2）从运筹学的斐波那契法来论述波浪理论，也可以从斐波那契法的最优分划点来掌握波浪理论中的最佳投资.（3）插值法是现代数值计算的重要工具,是一种求解一元函数极小点问题最优解的可行高效的方法,它的算法与连续平均法和精确线性搜索计算精度高，收敛速度快.（4）二次插值在科技和生活应用中有重要作用，比如理论进行信号处理的方法中,可以大大提高处理精度并节省数据存储空间;求常规项目的内部收益率该方法具有超线性收敛速度.4.1Fibonacci法这种方法与0.618法类似，也是用于单峰函数，在计算过程中，也是第1次迭代需要计算两个迭代点，以后每次迭代只需新算一点，另一点取自上次迭代。Fibonacci法与0.618法的主要区别在于:探索区间长度的缩短率不是采用黄金分割数，而是采用所谓的Fibonacci数,计算函数值的次数n也是已知的。前节内容：在逐次缩短区间时，为第k次迭代的区间缩短率，对于不外乎两种情形：或者为常数，这就是0.618法；或者不为常数，这就是本节要讲的Fibonacci法。)10(11kkkkkabab)2,1(kkkFibonacci数：数列满足条件：即则称为Fibonacci数列k}{kF1110)2(;1)1(kkkFFFFF}{kFk012345611234813kFFibonacci法的推导过程：(1)与黄金分割法一样,设初始区间上有唯一的极小值点，规定一共算n次函数值，取试探点，并设若最小值点在若最小值点在区间长度为区间长度为],[11ba1111'111121)()(aabFFxaabFFxnnnn'1'111)()(fxffxf'11ff],['11xa)(1111'1abFFaxnn'11ff],[11bx)()()(1112112111111abFFFFFabFFababxbnnnnnnn'11xx'11ff时，并在'11ff的情形下，不影响我们的计算。注意：1x'1x1a1b从而可知不论哪种情形都是将原区间长度变成新区间长度(2)如果新的区间为，我们将取两个插入点为我们自然希望会有下面情况之一发生：因为如果发生一种，我们就又得到每迭代一次只计算一个函数值的算法.下面用直接验证来解决这个问题.)(11ab)(111abFFnn],[22ba22212'222232)()(aabFFxaabFFxnnnn''''12121212,,,.xxxxxxxx若则有注意:此时有在内，由的公式知道刚好与一致.若则注意：此时有在内.由的公式知道'11,ffnnFFabaxbaa1111'1212)(,22xx、121111122222))(()(nnnnnnFFabFFaFFabax)()(1121111211abFFaabFFFFannnnnn1x1x],[22ba1x11ff12112112),(bbabFFaxann22xx、],[22ba2x'2x2a2b刚好与一致，这就说明了保留的一点确实与新的插入点之一重合，新的区间长度为此时我们一共迭代了2次.)()()()())(()()(1111231111321111211311121112113222abFFaFFFabaFFFFFababFFaFFaabFFbabFFaFFabannnnnnnnnnnnnnnnnnnn2x1x)()(1122212222'2abFFabFFxbaxnnnn(3)按这样的办法取点，我们计算第K-1次迭代时，区间将变成保留的一点是或，区间长度应是并且两式中一定成立一个此时我们有Fibonacci法在迭代过程中计算试点的公式：],,[kkba1kx'1kx)(11abFFnknkkkkxxxx'1'1,)()(1'11kkknknkkkkknknkkabFFaxabFFax12,1nk(4)在进行第K次迭代前，取试探点,时，令时，令],[,'kkkkbaxx'kkxx)()('kkxfxf'11,kkkkxbaa)()(11'11kkknknkkkknknkkkkkabFFaabFFaaxab)()('kkxfxf)()(1])([1111111kkknknkkknknkkkknknkkkkkabFFabFFaabFFbxbabkkkkbbxa11,从上述两种情况可看出不论属于哪种情形，迭代后的区间长度迭代前的区间长度之比均为利用上述比值，可以计算出经n-1次迭代(k=n-1)所得到的区间长度所以，只要给定初始区间长度及精度要求(最终区间长度)L，就可以求出计算函数值的次数n(不包括初始区间端点函数值的计算)，令即1knknFF)(1)()(1111132211121abFabFFFFFFabFFabnnnnnnn11abLabnnLabFn)(111由此可确定出计算函数值的次数n.注意：由于第1次迭代计算两个试探点，以后每次计算一个，这样经过n-1次迭代就计算完n个试探点.但是，在第n-1次迭代中并没有选择新的试探点，根据试探点的公式我们必有而和中的一个是取自n-2次迭代之后，这时已确定出，在的右边或左边取一点，令其中辨别常数)(2111'11nnnnbaxx1kx'1kx'11nnxx1nx1'1,nnnnxxxx0Fibonacci法计算步骤如下：(1)给定初始区间和最终长度L。求计算函数值的次数n,使，辨别常数计算试探点和，计算函数值和(2)若则转步骤(3);若,则转步骤(4)(3)令，计算试点若则转步骤(6);否则，计算函数值转步骤(5)(4)令，计算试点若则转步骤(6);否则，计算函数值转步骤(5)],[11baLabFn/)(1101x'1x)(1xf)('1xf)()('kkxfxf)()('kkxfxf'111,,kkkkkkxxbbxa)(1111'1kkknknkkabFFax2nk)('1kxfkkkkkkxxxbaa'1'11,,1kx)(11211kkknknkkabFFax2nk)(1kxf(5)置转至步骤(2)(6)令计算和若则令若则令停止计算，极小点含于1:kk1'1,nnnnxxxx)(nxf)('nxf)()('nnxfxf1,nnnnbbxa)()('nnxfxfnnnnxbaa,1],[nnba例：用Fibonacci法解下列问题：初始区间，精度解：判别常数由于,所以n=6,12)(min2xxxf]1,1[],[11ba16.0L01.05.1211LabFn123456-1-0.23077-0.230770.076920.076920.23077110.538460.538460.384610.38461-0.230770.230770.076920.230770.230770.230770.230770.538460.230770.384610.230770.24077-0.66272-1.12426-1.06509-1.12426-1.12426-1.12426-1.12426-0.95858-1.12426-1.08876-1.12426-1.12483kakbkx'kx)(kxf)('kxf1)区间2)区间3)区间4)此时k=n-2=6-2=4,由步骤(4)知道所以区间，且5)由步骤(6)知道所以极小点)()('11xfxf'12xx],[],[1122bxba)()('22xfxf2'3xx],[],['2233xaba)()('33xfxf'34xx],[],[3344bxba)()('44xfxf],[],['4455xaba'4545,xbaa255'55baxx)()('55xfxf665655'656,,01.0,xbaaxxxxx]38461.0,23077.0[],[66bax