《维搜索方法》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 从上式看，需求求导进展计算，对于函数关系复杂的，解析法非常不便。数值法的根本思绪：确定 的搜索区间，在不断减少区间，最终获得近似值。* 1、单谷、

2、单谷(峰区间峰区间 在给定区间内仅有一个谷值的函数称为单谷函在给定区间内仅有一个谷值的函数称为单谷函数，其区间称为单谷区间。数，其区间称为单谷区间。第二节 搜索区间确实定和区间消去法原理O f (a) b x* x a 函数值：函数值：“大小大大小大图形：图形：“高高低低高高 单谷区间中一定能求得单谷区间中一定能求得一个极小点一个极小点 2. 找初始单谷区间是找初始单谷区间是一维搜索的第一步；一维搜索的第一步；第二步使区间减少。第二步使区间减少。图3-2 正向搜索的外推法图3-3 反向搜索的外推法根本思想：根本思想： 对对f(x)任选一个初始点任选一个初始点a1及初始步长及初始步长h， 经过比

3、较这两经过比较这两点函数值的大小，确定第三点位置，比较这三点的函数点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定能否为值大小，确定能否为 “高高低低高高 形状。形状。步骤：步骤：1选定初始点选定初始点a, 初始步长初始步长hh0，计算，计算 y1f(a1)， y2f(a1h)。2比较比较y1和和y2。 a如如y1y2, 向右前进；加大步长向右前进；加大步长 h2 h ，转，转3向前；向前； b如如y1y3, 加大步长加大步长 h2 h ，a1=a2, a2=a3,转转3继续探测。继续探测。 a如如y2y3, 那么初始区间得到：那么初始区间得到： a=mina1,a3， b=max

4、a3,a1，函数最，函数最小值所在的区间为小值所在的区间为a， b 。 搜索区间确定之后，采用区间消去法逐渐缩短搜索区间确定之后，采用区间消去法逐渐缩短搜索区间，从而找到极小点的数值近似解。搜索区间，从而找到极小点的数值近似解。 假定在搜索区间内假定在搜索区间内a,b a,b 任取两点任取两点a1,b1;a1,b1;f1fa1， f2fb1区间消去法原理区间消去法原理一、根本思想一、根本思想f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1 a1 b1baabab b1b1 f1fa1， f2fb1 (1)如如f1f2, 那么减少的新区间为那么减少的新区间为a1,b; (3)

5、如如f1=f2, 那么减少的新区间为那么减少的新区间为a1,b1f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1 a1b1baabab b1 b1综合为两种情况：综合为两种情况：假设假设 那么取那么取 为缩短后的搜索区为缩短后的搜索区间。间。假设假设 那么取那么取 为缩短后的搜索区为缩短后的搜索区间。间。11( )( )f af b1 ,a b11()()f af b1 , a b三、一维搜索方法的分类从前面的分析可知，每次缩短区间，只需求在区间内在插入一点并计算其函数值。而插入点的位置，可以由不同的方法来确定。就构成了不同的一维搜索方法。一维搜索方法分类试探法插值法黄金分

6、割法二次插值法第三节 一维搜索的试探法最常用的一维搜索试探法是黄金分割法，又称0.618法。要求插入点a1、a2的位置相对于区间a,b两端点具有对称性。1abba2aaba除对称要求外，黄金分割法还要求在保管下来的区间再插入一点所构成的区间新三段，与原来区间的三段具有一样的比例分布。212210 0.618所谓的“黄金分割是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段的比值，即1: 1l黄金分割法的搜索过程：黄金分割法的搜索过程：l1 1给出初始搜索区间及收敛精度给出初始搜索区间及收敛精度 ，将，将 赋以赋以0.6180.618。l2 2按坐标点计算公式计算按坐标点计

7、算公式计算 , , ；并计算其对应的函；并计算其对应的函数值。数值。12l3 3根据区间消去法原理缩短搜索区间。为了能用原来根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，需进展区间称号的代换，并在保管区的坐标点计算公式，需进展区间称号的代换，并在保管区间中计算一个新的实验点及其函数值。间中计算一个新的实验点及其函数值。l假设假设 ，那么新区间，那么新区间 l 令令 记记N0=0N0=0； l假设假设 ，那么新区间，那么新区间 ，l令令 ，记，记N0=1N0=1； 12ff2 ,a12ff1 , a b22121,bff11212,affl4 4检查区间能否缩短到足够小和函数值收

8、敛到足够精检查区间能否缩短到足够小和函数值收敛到足够精度，假设收敛条件满足，那么取最后两实验点的平均值度，假设收敛条件满足，那么取最后两实验点的平均值作为极小点的数值近似解。假设条件不满足那么转向步作为极小点的数值近似解。假设条件不满足那么转向步骤骤5 5。1110.382(),()abaff2220.618(),()abafff(a1)f(a2)f(a1)f(a2)a1(a) a1(a2) a2(b)abab a2(a1)a1a2如如N0=0N0=0，那么取，那么取如如N0=1，那么取，那么取l5 5产生新的插入点：产生新的插入点：l转向转向3进展新的区间减少。进展新的区间减少。例例 3-1

9、 用黄金分割法求函数用黄金分割法求函数f(x)=3x3-4x+2的极小点，的极小点，给定给定 x0=0, h=1, =0.2。解：解：1确定初始区间确定初始区间x1=x0=0, f1=f(x1)=2x2=x0+h=0+1=1, f2=f(x2)=1由于由于f1f2, 应加大步长继续向前探测。应加大步长继续向前探测。x3= x0+2h=0+2=2, f3=f(x3)=18由于由于f2f3,可知初始区间曾经找到，即可知初始区间曾经找到，即a,b=x1,x2=0,22用黄金分割法减少区间用黄金分割法减少区间 第一次减少区间：第一次减少区间： x1=0+0.382X(2-0)=0.764, f1=0.

10、282 x2=0+0.618 X(2-0)=1.236, f2=2.72 f10.2第二次减少区间：第二次减少区间：令令 x2=x1=0.764, f2=f1=0.282 x1=0+0.382X(1.236-0)=0.472, f1=0.317由于由于f1f2, 故新区间故新区间a,b=x1,b=0.472, 1.236由于由于 b-a=1.236-0.472=0.7640.2, 应继续减少区间。应继续减少区间。 第三次减少区间：第三次减少区间：令令 x1=x2=0.764, f1=f2=0.282 x2=0.472+0.618X(1.236-0.472)=0.944, f2=0.747由于由

11、于f10.2, 应继续减少区间。应继续减少区间。 第四次减少区间：第四次减少区间：令令 x2=x1=0.764, f2=f1=0.282 x1=0.472+0.382X(0.944-0.472)=0.652, f1=0.223由于由于f10.2, 应继续减少区间。应继续减少区间。第五次减少区间：第五次减少区间：令令 x2=x1=0.652, f2=f1=0.223 x1=0.472+0.382X(0.764-0.472)=0.584, f1=0.262由于由于f1f2, 故新区间故新区间a,b=x1,b=0.584, 0.764由于由于 b-a=0.764-0.584=0.180.2, 停顿迭

12、代。停顿迭代。极小点与极小值：极小点与极小值：x*=0.5X(0.584+0.764)=0.674, f(x*)=0.2222( )2f35 211f2f 迭代 序号ab比较0 0-3-30.0560.0561.9441.9445 50.1150.115 7.6677.6671 1-3-3-1.111-1.1110.0560.0561.9441.944-0.987-0.987-0.987-0.9873 3-1.832-1.832-1.111-1.111-0.665-0.6650.0560.056-0.987-0.987-0.987-0.9875 5-1.386-1.386-1.111-1.11

13、1-0.940-0.940-0.665-0.66511()( 1.3860.665)1.025522ab 第四节 一维搜索的插值方法假定要在某一区间内寻觅函数的极小点的位置，虽然没有函数表达式，但可以给出假设干实验点处的函数值。我们可以根据这些点处的函数值，利用插值的方法建立函数的近似表达式，进而求处函数的极小点，作为原来函数的极小点的近似值。这种方法称作插值法，也称函数逼近法。一、牛顿法切线法 20000012ffff yf一维搜索函数，假定一给出极小点的一个较好的近似点0，由于一个延续可微的函数在极小点附近与一个二次函数很接近，因此，在 点附近用一个二次函数 逼近。0 10 求二次函数 的

14、极小点作为 f极小点的新近似点1即0000ff0100ff依次继续下去，可得牛顿法迭代公式：1kkkkff0,1,2,.k 牛顿法的几何解释：牛顿法的计算步骤：给定初始点 ，控制误差 ，并令k=0。01计算kfkf2求1kkkkff3)假设1kkaa那么求得近似解*1kaa，停顿计算，否那么作4。4令1kk转1。优点：收敛速度快。缺陷：每一点都要进展二阶导数，任务量大；要求初始点离极小点不太远，否那么有能够使极小化发散或收敛到非极小点。二、二次插值抛物线法利用123 yf a在单谷区间中 的函数值123fff，作出如下的二次插值多项式 2012Paaa它应满足条件210112111Paaayf

15、1220122222Paaayf230132333Paaayf从极值的必要条件求得1220ppPaa12/2paa 23要求出系数 和 ，联立方程组1、2、3。1a2a2212322323a aaaaayy2211221212aaaaaayy2222222313121231122331aayaayaayaaaaaaa2313121232122331aayaayaayaaaaaaa 222222231312123122313121231/22paayaayaayaaaayaayaay 31131yycaa21121223yycaacaa113212pcaaac令所以那么2()0paa h2()0

16、paa h例例 33 用二次插值法求函数用二次插值法求函数f(x)=3x3-4x+2的极小点，的极小点，给定给定 x0=0, =0.2。 解解 1确定初始区间确定初始区间 初始区间初始区间a,b=0,2, 中间点中间点x2=1。2用二次插值法逼近极小点用二次插值法逼近极小点相邻三点的函数值相邻三点的函数值: x1=0, x2=1, x3=2; f1=2, f2=1, f3=18. 代入公式：代入公式：222222*2313121232313121231 ()()()2 ()()()pxxfxxfxxfxxxfxxfxxfxp*0.555, fp=0.292 在新区间，相邻三点的函数值在新区间，

17、相邻三点的函数值: x1=0, x2=0.555, x3=1; f1=2, f2=0.292, f3=1. xp*0.607, fp=0.243 由于由于fpx2, 新区间新区间a,b=x2, b=0.555,1 |x2-xp * |=|0.555-0.607|=0.0520.2, 迭代终止。迭代终止。 xp*0.607, f*=0.243由于由于fpf2, xp * 0.2, 应继续迭代。应继续迭代。l例例 3-4 用二次插值法求用二次插值法求 的极值点。的极值点。初始搜索区间初始搜索区间 ， 。432( )46164f xxxxx13 1 6x x 0.05l解：取解：取x2点为区间点为区

18、间x1,x3的中点，的中点， , 计算计算x1,x2,x3 3点处的函数值点处的函数值f1=19，f2=-96.9375，f3=124。可见函数值满足可见函数值满足“高低高形状。高低高形状。2130.5 ()2.5xxxl 以以x1,x2,x3为插值点构造二次曲线，为插值点构造二次曲线， l求第一次近似的二次曲线求第一次近似的二次曲线p(x)的极小值点，由公式得：的极小值点，由公式得：l ， 比较函数值可知比较函数值可知1.9545px*2()65.4648()96.9375pf xf x l这种情况应消除左边区段这种情况应消除左边区段 。然后用。然后用 作为作为x1,x2,x3新新3点点,重新构造二次曲线重新构造二次曲线p(x)，如此反复计算，如此反复计算，直到直到 为止。为止。*1 ,px x*23,pxx x*2pxx20.03780.05pxx2()155.6850()155.8969pf xf x 3.9501pxx表2-2 二次插值法