三章节一维搜索方法ppt课件

1、第三章一维搜索方法1kkkkxxa d采用数学规划法求函数极值点的迭代计算：K+1次迭代的搜索方向搜索的最佳步长因子当搜索方向 给定，求最佳步长kakd就是求一元函数的极值。1kkkkkf xf xa da称为一维搜索。 是优化搜索方法的基础。求解一元函数 的极小点a*a，可用解析法。 12TTf xadf xadf xadG ad上式求的极值，即求导数为零。 212TTf xdf xd Gd *0TTdf xd Gd那么 *TTdfxd Gd 从上式看，需要求导进行计算，对于函数关系复杂的，解析法十分不便。数值法的基本思路：确定 的搜索区间，在不断缩小区间，最终获得近似值。*第二节 搜索区间

2、的确定和区间消去法原理一、确定搜索区间的外推法图3-2 正向搜索的外推法图3-3 反向搜索的外推法三、区间消去法原理)a 11f af b 11)b f af b 11)c f af b为了避免多计算函数值，将第三种情况合并到前两种情况中。)a 11f af b 11)b f af b三、一维搜索方法的分类从前面的分析可知，每次缩短区间，只需要在区间内在插入一点并计算其函数值。而插入点的位置，可以由不同的方法来确定。就形成了不同的一维搜索方法。一维搜索方法分类试探法插值法黄金分割法二次插值法第三节一维搜索的试探法最常用的一维搜索试探法是黄金分割法，又称0.618法。要求插入点a1、a2的位置相

3、对于区间a,b两端点具有对称性。1abba2aaba除对称要求外，黄金分割法还要求在保留下来的区间再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。212210 0.618所谓的“黄金分割是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段的比值，即1: 1第四节一维搜索的插值方法假定要在某一区间内寻找函数的极小点的位置，虽然没有函数表达式，但能够给出若干试验点处的函数值。我们可以根据这些点处的函数值，利用插值的方法建立函数的近似表达式，进而求处函数的极小点，作为原来函数的极小点的近似值。这种方法称作插值法，也称函数逼近法。一、牛顿法切线法） 2000001

4、2ffff yf一维搜索函数，假定一给出极小点的一个较好的近似点0，因为一个连续可微的函数在极小点附近与一个二次函数很接近，因而，在 点附近用一个二次函数 迫近。0 10 求二次函数 的极小点作为 f极小点的新近似点1即0000ff0100ff依次继续下去，可得牛顿法迭代公式：1kkkkff0,1,2,.k 牛顿法的几何解释：牛顿法的计算步骤：给定初始点 ，控制误差 ，并令k=0。01计算kfkf2求1kkkkff3)假设1kkaa则求得近似解*1kaa，停止计算，否则作4。4令1kk转1。优点：收敛速度快。缺点：每一点都要进行二阶导数，工作量大；要求初始点离极小点不太远，否则有可能使极小化发

5、散或收敛到非极小点。二、二次插值抛物线法）利用123 yf a在单谷区间中 的函数值123fff，作出如下的二次插值多项式 2012Paaa它应满足条件210112111Paaayf（1）220122222Paaayf230132333Paaayf从极值的必要条件求得1220ppPaa12/2paa （2）（3）要求出系数 和 ，联立方程组1）、（2）、（3）。1a2a2212322323a aaaaayy2211221212aaaaaayy2222222313121231122331aayaayaayaaaaaaa2313121232122331aayaayaayaaaaaaa 222222231312123122313121231/22paa