法与Fibonacci法.pptVIP

Fibonacci方法评价 Fibonacci方法评价 * * 0.618法与Fibonacci法 单谷函数(Unimodal Function)---定义 0.618法与Fibonacci法 单谷函数-----性质 注：通过计算区间 内两个不同点的函数值，就可以 确定一个包含极小点的子区间. 0.618法与Fibonacci法 单谷函数-----性质 0.618法与Fibonacci法 (3) (1) ; (2) 数; 问题的提出 0.618法与Fibonacci法 通过选取试探点使包含极小点的区间不断缩短， 值均接近极小值。 直到区间长度小到一定程度，此时区间上各点的函数 0.618法(黄金分割法)--- Golden Section Search 思路 下面推导黄金分割法的计算公式. 0.618法与Fibonacci法 0.618法(黄金分割法) 计算公式 0.618法与Fibonacci法 0.618法(黄金分割法) 计算公式 缩短率 0.618法(黄金分割法) 情 每次迭代区间长 度的缩短率相同 1 计算公式 0.618法与Fibonacci法 0.618法(黄金分割法) 注： 缩短率 恰为黄金分割数，即它满足 几何意义：黄金分割数 对应的点在单位长区间 [ 0,1]中的位置相当于其对称点 在区间[0， ]中的位置(如图6.2.2所示) 注 计算公式 0.618法与Fibonacci法 0.618法(黄金分割法) 算法步骤 0.618. = Step3 若 则 停； 否则 转Step４. 例 用黄金分割法求函数 在区间 上的极小点。 要求最终区间长度不大于 原始区间长度的0.08倍． 解 函数 在区间 上为单谷函数，且 0.618法与Fibonacci法 0.618法(黄金分割法) 举例 第一次迭代 缩短后区间为 第二次迭代 缩短后区间为 0.618法与Fibonacci法 0.618法(黄金分割法) 举例 是 1.757 1.751 0.580 0.528 ６ 否 1.751 1.753 0.528 0.443 ５ 否 1.777 1.751 0.665 0.528 ４ 否 1.751 1.788 0.528 0.305 ３ 否 1.901 1.751 0.888 0.528 ２ 否 1.751 2.059 0.528 -0.056 １ 否 2.695 1.751 1.472 0.528 ０ 迭代 次数 0.618法与Fibonacci法 Fibonacci法 当事先给定有哪些信誉好的足球投注网站算法的迭代次数N时，问按何种规则选取试探点可以使给定的有哪些信誉好的足球投注网站区间长度最快地缩短? 思路 问题的提出 由0.618法的推导过程知：在一般有哪些信誉好的足球投注网站算法的迭代过程中，缩短率满足 且 0.618法与Fibonacci法 Fibonacci法 待解决的问题转化 为优化问题： 思路 可以证明，此优化问题的最优解为 其中 FN-k 为Fibonacci数，即 0.618法与Fibonacci法 Fibonacci法 Fibonacci 法迭代公式 = 0.618法与Fibonacci法 Fibonacci法 注意事项 (1) 迭代次数n-1的确定 若原始区间为 要求最终区间长度 则 可确定n-1. (2) 第n-1次迭代中两个试点的选取方式 Fibonacci法 算法步骤 + Fibonacci法 算法步骤 0.618法与Fibonacci法 例 用Fibonacci法求函数 在区间 上的极小点。 要求最终区间长度不大于 原始区间长度的0.08倍． 解： 函数 在区间 上为下单峰函数， 由 可知 应取６ 0.618法与Fibonacci法 Fibonacci法 举例 第一次迭代： 缩短后区间为 0.618法与Fibonacci法 Fibonacci法 举例 第二次迭代： 缩短后区间为 0.618法与Fibonacci法 Fibonacci法 举例 第三次迭代： 缩短后区间为 第四次迭代： 缩短后区间为 0.618法与Fibonacci法 Fibonacci法 举例 第五次迭代： 0.618法与Fibonacci法 Fibonacci法 举例 缩短后区间为[0.231, 0.5386]. Fibonacci法的优点 效率最高，有限个试点的情况下，可将最优点所在的区间缩小到最小． 0.618法与Fibonacci法