《第三章一维搜索方法.ppt》由会员分享，可在线阅读，更多相关《第三章一维搜索方法.ppt（23页珍藏版）》请在三一文库上搜索。
1、第三章一维搜索方法,采用数学规划法求函数极值点的迭代计算：,K+1次迭代的搜索方向,搜索的最佳步长因子,称为一维搜索。,是优化搜索方法的基础。,求解一元函数 的极小点,，可用解析法。,上式求的极值，即求导数为零。,则,从上式看，需要求导进行计算，对于函数关系复杂的， 解析法十分不便。,数值法的基本思路：确定 的搜索区间，在不断缩小 区间，最终获得近似值。,第二节 搜索区间的确定和区间消去法原理,一、确定搜索区间的外推法,图3-2 正向搜索的外推法,图3-3 反向搜索的外推法,三、区间消去法原理,为了避免多计算函数值，将第三种情况合并到前两种 情况中。,三、一维搜索方法的分类,从前面的分析可知，
2、每次缩短区间，只需要在区间内在插入一 点并计算其函数值。,而插入点的位置，可以由不同的方法来确定。就形成了不同的一维搜索方法。,第三节一维搜索的试探法,最常用的一维搜索试探法是黄金分割法，又称0.618法。,要求插入点a1、a2的位置相对于区间a,b两端点具有对称性。,除对称要求外，黄金分割法还要求在保留下来的区间再插入一点 所形成的区间新三段，与原来区间的三段具有相同的比例分布。,2,所谓的“黄金分割”是指将一线段分成两段的方法，使整段长 与较长段的长度比值等于较长段与较短段的比值，即,第四节一维搜索的插值方法,假定要在某一区间内寻找函数的极小点的位置，虽然没有函数 表达式，但能够给出若干试
3、验点处的函数值。,我们可以根据这些点处的函数值，利用插值的方法建立函数的近似表达式，进而求处函数的极小点，作为原来函数的极小点的近似值。这种方法称作插值法，也称函数逼近法。,一、牛顿法（切线法）,函数很接近，因此，在 点附近用一个二次函数 逼近。,即,依次继续下去，可得牛顿法迭代公式：,牛顿法的几何解释：,牛顿法的计算步骤：,给定初始点 ，控制误差 ，并令k=0。,1）计算,2）求,优点：收敛速度快。,缺点：每一点都要进行二阶导数，工作量大；,要求初始点离极小点不太远，否则有可能使极小化 发散或收敛到非极小点。,二、二次插值（抛物线法）,，作出如下的二次插值多项式,它应满足条件,（1）,从极值的必要条件求得,（2）,（3）,要求出系数 和 ，联立方程组（1）、（2）、（3）。,令,所以,则,