Fibonacci法Fibonacci法.ppt

斐波那契法和二次插值法 小组成员：王娜 王慧红 郭茜茜 解悦 曹文彦 苏鹏 4.1 Fibonacci法 这种方法与0.618法类似，也是用于单峰函数， 在计算过程中，也是第1次迭代需要计算两个迭代点， 以后每次迭代只需新算一点，另一点取自上次迭代。 Fibonacci法与0.618法的主要区别在于:探索区 间长度的缩短率不是采用黄金分割数，而是采用所 谓的Fibonacci数,计算函数值的次数n也是已知的。 前节内容：在逐次缩短区间时， 为第 k 次迭代的区间缩短率，对于 不外乎两种情形：或者 为常数，这就是0.618法；或者 不为常数，这就是本节要讲的Fibonacci法。 从而可知不论哪种情形都是将原区间长度 变成新区间长度 (2)如果新的区间为 ，我们将取两个插入点为 我们自然希望会有下面情况之一发生： 因为如果发生一种，我们就又得到每迭代一次只计算一个 函数值的算法.下面用直接验证来解决这个问题. 刚好与 一致，这就说明了保留的一点确实与新的插入点 之一重合，新的区间长度为 此时我们一共迭代了2次. * 应用领域： （1）可以用斐波那契数列的寻优方法来计算交流电机驱动 系统的效率，该方法的突出特点是与损耗模型无关，并能 使系统快速达到效率最大工作点. （2）从运筹学的斐波那契法来论述波浪理论，也可以从斐 波那契法的最优分划点来掌握波浪理论中的最佳投资. （3）插值法是现代数值计算的重要工具,是一种求解一元函 数极小点问题最优解的可行高效的方法,它的算法与连续平 均法和精确线性有哪些信誉好的足球投注网站计算精度高，收敛速度快. （4）二次插值在科技和生活应用中有重要作用，比如理论 进行信号处理的方法中,可以大大提高处理精度并节省数据 存储空间;求常规项目的内部收益率该方法具有超线性收敛 速度. Fibonacci数： 数列 满足条件： 即 则称 为Fibonacci数列 k 0 1 2 3 4 5 6 1 1 2 3 4 8 13 Fibonacci法的推导过程： (1)与黄金分割法一样,设初始区间 上有唯一的极小值 点，规定一共算n次函数值，取试探点 ， 并设 ?若 最小值点在 ?若 最小值点在 区间长度为 区间长度为 时，并在 的情形下，不影响我们的计算。 注意： ?若 则有 注意:此时有 在 内，由 的公式知道 刚好与 一致. ?若 则 注意：此时有 在 内.由 的公式知道 (3)按这样的办法取点，我们计算第K-1次迭代时，区间将变 成 保留的一点是 或 ，区间长度应是 并且两式中一定成立一个 此时我们有Fibonacci法在迭代过程中计算试点的公式： (4)在进行第K次迭代前，取试探点 , ? 时，令 ? 时，令 从上述两种情况可看出不论属于哪种情形，迭代后的区间长 度迭代前的区间长度之比均为 利用上述比值，可以计算出经n-1次迭代(k=n-1)所得到的区 间长度 所以，只要给定初始区间长度 及精度要求(最终区间长 度)L，就可以求出计算函数值的次数n(不包括初始区间端点 函数值的计算)，令 即 由此可确定出计算函数值的次数n. 注意： 由于第1次迭代计算两个试探点，以后每次计算一个，这样 经过n-1次迭代就计算完n个试探点.但是，在第n-1次迭代中 并没有选择新的试探点，根据试探点的公式我们必有 而 和 中的一个是取自n-2次迭代之后，这时已确定 出 ，在 的右边或左边取一点，令 其中辨别常数 Fibonacci法计算步骤如下： (1)给定初始区间 和最终长度L。求计算函数值的次数 n,使 ，辨别常数 计算试探点 和 ， 计算函