Fiboacci算法.doc

Fibonacci法若数列{}满足关系： 则称为Fibonacci数列，称为第个Fibonacci数，称相邻两个Fibonacci数之比为Fibonacci分数。 当用斐波那契法以个探索点来缩短某一区间时，区间长度的第一次缩短率为，其后各次分别为。由此，若和是单峰区间中第1个和第2个探索点的话，那么应有比例关系， 从而 ， （3）它们关于确是对称的点。如果要求经过一系列探索点搜索之后，使最后的探索点和最优解之间的距离不超过精度，这就要求最后区间的长度不超过，即 （4）据此，我们应按照预先给定的精度，确定使（4）成立的最小整数作为搜索次数，直到进行到第个探索点时停止。用上述不断缩短函数的单峰区间的办法，来求得问题（2）的近似解，是Kiefer(1953年)提出的，叫做Finbonacci法，具体步骤如下：1° 选取初始数据，确定单峰区间，给出搜索精度，由（4）确定搜索次数。2° ，计算最初两个搜索点，按（3）计算和。3° while if else endend4° 当进行至时， 这就无法借比较函数值和的大小确定最终区间，为此，取 其中为任意小的数。在和这两点中，以函数值较小者为近似极小点，相应的函数值为近似极小值。并得最终区间或。 由上述分析可知，斐波那契法使用对称搜索的方法，逐步缩短所考察的区间，它能以尽量少的函数求值次数，达到预定的某一缩短率。