搜索算法结构教学课件

《搜索算法结构教学课件》由会员分享，可在线阅读，更多相关《搜索算法结构教学课件（66页珍藏版）》请在金锄头文库上搜索。

1、3.1 3.1 3.1 3.1 搜索算法结构搜索算法结构搜索算法结构搜索算法结构一、下降算法模型一、下降算法模型 考虑（考虑（NP） 常用一种线性搜索的方式来求解：迭代中从常用一种线性搜索的方式来求解：迭代中从一点出发沿一点出发沿下降可行方向下降可行方向找一个新的、性找一个新的、性质有改善的点。质有改善的点。迭代计算：其中 为第 次迭代的搜索方向， 为沿 搜索的最佳步长因子（通常也称作最佳步长）。min f(x) s.t. xS第三章第三章 常用的一维搜索方法常用的一维搜索方法脸卓彦误驾茁竣冤栏览绞肆怎郑例锈湃俩蛀瑰吟赶睦咀棚烽狂楚妮砾捂美搜索算法结构教学课件搜索算法结构教学课件可行方向：设可

2、行方向：设 S，dRn,d0,若存在若存在 ，使，使 ，称，称d 为为 点的点的可行方向。可行方向。同时满足上述两个性质的方向称同时满足上述两个性质的方向称下降可行方向下降可行方向。下降方向下降方向 ： 设设 S，d Rn,d0,若存在若存在 ，使，使 ，称，称d 为为 在在 点的下降方向。点的下降方向。谢腰琼词搬律勾炎排谜膝监绞抢偶汁馏识闷颁顽吴窟谓橡烂棍抨职森龟藻搜索算法结构教学课件搜索算法结构教学课件l模型算法模型算法线性搜索求线性搜索求 ，新点新点使使x(k+1)S初始初始x(1) S, k =1对对x(k)点选择下降点选择下降可行方向可行方向d(k)是否满足停机条件？是否满足停机条件

3、？停停k=k+1yesno531汤桌袍抄块靴慧贿嘶赔淤右紧豪万铭眩爪是伪位姿承美育满勾耀撂稗剧垦搜索算法结构教学课件搜索算法结构教学课件二、二、收敛性收敛性概念概念： 考虑（考虑（NP）设迭代算法产生点列设迭代算法产生点列x(k) S.1. 理想的收敛性：设理想的收敛性：设x*S是是g.opt(全局最优解全局最优解).当当x* x(k) 或或 x(k) x*， k，满足满足 时，称算法收敛到最优解时，称算法收敛到最优解 x*。 min f(x) s.t. xS霍泛傻赘琶肇绕令盔凌烙梯厄却开孝油烦嫉宿撞馏还氓俺荷价寸氛酬汝尤搜索算法结构教学课件搜索算法结构教学课件 由于非线性规划问题的复杂性，实

4、用中建立下列收由于非线性规划问题的复杂性，实用中建立下列收敛性概念敛性概念 ：2. 实用收敛性：定义解集实用收敛性：定义解集 S* = x | x 具有某种性质具有某种性质 例：例：S*=x|x-g.opt S*=x|x-l.opt S*=x| f(x)=0 S*=x|f(x) (为给定的实数阈值为给定的实数阈值)碰睡父谋闺蔚达诀恐凡雅袒舅扮钓泊肌济评验栓费阳闪繁坤轻瓢非乡归部搜索算法结构教学课件搜索算法结构教学课件2.实用收敛性（续）实用收敛性（续）收敛性：设解集收敛性：设解集S* ，x(k)为算法产生的点为算法产生的点列。下列情况之一成立时，称算法收敛：列。下列情况之一成立时，称算法收敛：

5、 1 x(k) S*; 2x(k) S*， k，x(k)的任意极限点的任意极限点x* S* 。 全局收敛全局收敛：对任意初始点：对任意初始点x(1),算法均收敛。算法均收敛。 局部收敛局部收敛：当：当x(1) 充分接近解充分接近解x*时，算法收敛。时，算法收敛。有限步终止有限步终止驼垣摹兢颓拈烦廖朽弃摹溶涟懂农碰彬霞紫巡新疾缝筑准照釜绣蘸寺汛幂搜索算法结构教学课件搜索算法结构教学课件三、收敛速度三、收敛速度 设算法产生点列设算法产生点列x(k) 收敛到解收敛到解x*，且，且x(k)x*, k，关于算法的收敛速度，有关于算法的收敛速度，有1.线性收敛：线性收敛： 当当k充分大时成立。充分大时成立

6、。2.超线性收敛：超线性收敛： 3.二阶收敛：二阶收敛： 0，是是 使当使当k充分大时有充分大时有淤涂喇募涯弹松论钒斗饵跳播姐淹聚亦贾草秋熊田诌毖笑哆备悯皂耗徐旅搜索算法结构教学课件搜索算法结构教学课件三、收敛速度（续）三、收敛速度（续）定理：设算法点列定理：设算法点列x(k)超线性收敛于超线性收敛于x*,且且x(k)x*， k，那么那么证明：证明：只需注意只需注意| |x(k+1) x* | -| x(k) x* | | |x(k+1) x(k) | |x(k+1) x* | +| x(k) x* | ，除以，除以| x(k) x* | 并令并令k，利用超线性收敛定义可得结果。利用超线性收敛

7、定义可得结果。该结论导出算法的停止条件可用：该结论导出算法的停止条件可用：靶唬大圃抢烈后峙邦雨坚芹非矢境薄仿刑俊岿内炽喧桑殷军赃崩辙唁附放搜索算法结构教学课件搜索算法结构教学课件四、二次终结性四、二次终结性一个算法用于解正定二次函数的无约束极小一个算法用于解正定二次函数的无约束极小时，有限步迭代可达最优解，则称该算法具时，有限步迭代可达最优解，则称该算法具有有二次终结性二次终结性。际锦参阿六汇润蟹屋课薛逞继配夺统泪烂如置伊劈坷挺奄种遭品卷琴旨宴搜索算法结构教学课件搜索算法结构教学课件禽敌芋老侍灌询沛匪虫沫驼台谴锯咕鸯杖惋雍旦拟村洁奔某沤妓灾享淮蝶搜索算法结构教学课件搜索算法结构教学课件问题描述

8、：问题描述：问题描述：问题描述：已知并且求出了处的可行下降方向从出发， 沿方向求如下目标函数的最优解，或者选取使得：常用的一维搜索算法常用的一维搜索算法常用的一维搜索算法常用的一维搜索算法骑沙毡檬千耗瞩鞭澈型萍峡戌坷瘤辉糕谷厨腰电邵捅胸拢碑铸殴笨坎袭班搜索算法结构教学课件搜索算法结构教学课件设其最优解为（叫精确步长因子），所以线性搜索是求解一元函数的最优化问题（也叫一维最优化问题或一般地，一维优化问题可描述为：于是得到一个新点：一维搜索）。或解箱逗授前榴届时禽针仪耶欠尔胯妻俘望癣罢责麦酞射闰体糊毁修调炽诡乳搜索算法结构教学课件搜索算法结构教学课件一般地，线性搜索算法分成两个阶段：第一阶段确定包

9、含理想的步长因子（或问题最优解）的搜索区间；第二阶段采用某种分割技术或插值方法缩小这个区间。拭测阶赡尧铸廖鞘拘鳖莱水挡萤碌溶葫梁术女大垂娠篙睫藉详咎树飘擞赞搜索算法结构教学课件搜索算法结构教学课件 搜索区间的确定搜索区间的确定 黄金分割法黄金分割法(0.618法法) 二次插值法二次插值法 Newton法法要点：要点：单峰函数的消去性质、进退算法基本思想、黄金分割单峰函数的消去性质、进退算法基本思想、黄金分割法基本思想、重新开始、二次插值法要求、极小化框架、法基本思想、重新开始、二次插值法要求、极小化框架、Newton法基本思想、方法比较。法基本思想、方法比较。我们主要介绍如下一些搜索方法：我们

10、主要介绍如下一些搜索方法：揽涛笨咸拄桃成镁指戊音淹屈孺九轮痔铱存渠音熙诧慷婪肥潍涎梅鸳庭醋搜索算法结构教学课件搜索算法结构教学课件学习的重要性：学习的重要性：1、工程实践中有时需要直接使用；工程实践中有时需要直接使用；2、多变量最优化的基础，迭代中经常要用到。多变量最优化的基础，迭代中经常要用到。方法分类：方法分类：1、直接法：、直接法：迭代过程中只需要计算函数值；迭代过程中只需要计算函数值；2、微分法：、微分法：迭代过程中还需要计算目标函数的导数；迭代过程中还需要计算目标函数的导数；怜欺潜付书正爹梨敲极涪旭世羊蜒侯媳脉鸿史丙晓俄坑寻寐威可姐址嚼凯搜索算法结构教学课件搜索算法结构教学课件f(x

11、)xab3.2 搜索区间的确定搜索区间的确定 常用的一维直接法有常用的一维直接法有消去法消去法和和近似法近似法两类。它们都是从两类。它们都是从某个初始搜索区间出发，利用某个初始搜索区间出发，利用单峰函数的消去性质单峰函数的消去性质，逐步缩，逐步缩小搜索区间，直到满足精度要求为止。小搜索区间，直到满足精度要求为止。3.2.1 单峰函数单峰函数 连续单峰函数连续单峰函数f(x)xab不连续单峰函数不连续单峰函数f(x)xab离散单峰函数离散单峰函数f(x)xa b非单峰函数非单峰函数定义：定义：如果函数如果函数f(x)在区间在区间a,b上只有一个极值点上只有一个极值点, 则称则称f(x)为为 a,

12、 b上的单峰函数。上的单峰函数。 毛氟眯嘛台撤鬼笋战边宾酬悉浦腥遭戚忙仁笨宿奢原芬暴护诲匙扒端睁奔搜索算法结构教学课件搜索算法结构教学课件单峰函数具有一个重要的消去性质单峰函数具有一个重要的消去性质定理：定理：设设f(x)是区间是区间a,b上的一个单峰函数，上的一个单峰函数，x*a,b是其极小是其极小点，点， x1 和和x2是是a, b上的任意两点，且上的任意两点，且ax1 x2b，那么比较，那么比较f(x1)与与f(x2)的值后，可得出如下结论：的值后，可得出如下结论：f(x)xab(I) 消去消去a, x1 x*x1x2f(x)xab(II) 消去消去x2, bx*x2x1(II) (II

13、) 若若f(x1) f(x2), x*a,x2在单峰函数的区间内，计算两个点的函数值，比较大小后，就在单峰函数的区间内，计算两个点的函数值，比较大小后，就能把搜索区间缩小。在已缩小的区间内，仍含有一个函数值，能把搜索区间缩小。在已缩小的区间内，仍含有一个函数值，若再计算另一点的函数值，比较后就可进一步缩小搜索区间若再计算另一点的函数值，比较后就可进一步缩小搜索区间 .（I） 若若f(x1)f(x2)，x*x1,b赌首价剐轰峙核疫绚陪刁鲤坯背回侩嚷糜纶盖殃献毋贾畔弱揪都诛逼钎皋搜索算法结构教学课件搜索算法结构教学课件3.2.2 进退算法进退算法 (或称成功或称成功-失败失败法法)如何确定包含极小

14、点在内的初始区间如何确定包含极小点在内的初始区间 ?（一）（一）基本思想：基本思想：由单峰函数的性质可知，函数值在极小点左边严格下降，在右由单峰函数的性质可知，函数值在极小点左边严格下降，在右边严格上升。边严格上升。f(x)xabx*x0x1x2从某个初始点出发，沿函数值下降的方向前进，直至发现函数从某个初始点出发，沿函数值下降的方向前进，直至发现函数值上升为止。值上升为止。由由两边高，中间低的三点两边高，中间低的三点，可确定极小点所在的初始区间。，可确定极小点所在的初始区间。疾析掷傅鞋伊筹筹翘孰淄谰繁栖穷鸯片褐涨瘸黄哺骂腑统犀可祟嗡屉沃绳搜索算法结构教学课件搜索算法结构教学课件（二）（二）算

15、法算法1、选定初始点选定初始点a 和步长和步长h;f(x) x2、计算并比较计算并比较f(a)和和f(a+h)；有前进；有前进(1)和后退和后退(2)两种情况：两种情况：(1) 前进运算：若前进运算：若f(a) f(a+h), (2) 后退运算：若后退运算：若f(a) f(a+h), a a+h 则步长加倍，计算则步长加倍，计算f(a+3h)。若。若f(a+h) f(a+3h)， 令令 a1=a, a2=a+3h, 停止运算；否则将步长加倍，并重复上述运算。停止运算；否则将步长加倍，并重复上述运算。a+3hf(x) xaa+ha+7ha1b1a-ha-3ha-7ha1b1 则将步长改为则将步长

16、改为h。计算。计算f(ah), 若若f(ah) f(a)， 令令 a1=ah, a2=a+h, 停止运算；否则将步长加倍，继续后退。停止运算；否则将步长加倍，继续后退。仅仅找区间！若进一步找仅仅找区间！若进一步找最小点，参阅最小点，参阅P44!沪宵且硬姨淖帘衣浊幽般拉辽邢隧龄唯峙倍频稼壶元控锹辛斯自瘦暖膛氓搜索算法结构教学课件搜索算法结构教学课件(三三) 几点说明几点说明缺点：效率低；缺点：效率低；优点：可以求搜索区间；优点：可以求搜索区间；注意：注意：h 选择要适当，选择要适当，初始步长不能选得太小初始步长不能选得太小； 布叹堵餐领疾蒂坍宵贺骆蓬厩剧趋难踊踌县猜议欠程遥痪橱株嚼腕珠捉右搜索算

17、法结构教学课件搜索算法结构教学课件3.3 区间消去法黄金分割法区间消去法黄金分割法 消去法的思想：消去法的思想：反复使用单峰函数的消去性质，不断缩小包含极小点的反复使用单峰函数的消去性质，不断缩小包含极小点的搜索区间，直到满足精度为止。搜索区间，直到满足精度为止。 消去法的优点：消去法的优点：只需计算函数值，通用性强。只需计算函数值，通用性强。 消去法的设计原则：消去法的设计原则：（1）迭代公式简单；（）迭代公式简单；（2）消去效率高；）消去效率高；（3）对称：）对称： x1 a = b-x2 ；（4）保持缩减比：）保持缩减比：=(保留的区间长度保留的区间长度原区间长度原区间长度) 不变。（使

18、每次保留下来的节点，不变。（使每次保留下来的节点， x1或或 x2 ，在下一次的，在下一次的比较中成为一个相应比例位置的节点比较中成为一个相应比例位置的节点 ）。）。 （一）（一）黄金分割黄金分割 xabL LL ( (1 1) )L L取 “ ”，=0.61803398874189 彪新竿兼余睬挛咐贝岳专毕衬推饲明创迎互楷抱隆钢蛋脸葱茂冰卫吼枉蓖搜索算法结构教学课件搜索算法结构教学课件（二）（二）黄金分割法的基本思想黄金分割法的基本思想 黄金分割重要的黄金分割重要的消去性质消去性质: x2abL LL ( (1 1) )L Lx1 LL ( (1 1) )L L设设x1 ，x2 为为a, b

19、 中对称的两个黄金分割点，中对称的两个黄金分割点，x1为为a,x2的的黄金分割点黄金分割点x2为为x1,b的黄金分的黄金分割点割点 在在进进行行区区间间消消去去时时，不不管管是是消消去去a, x1，还还是是消消去去x2，b，留留下下来来的的区区间间中中还还含含一一个个黄黄金金分分割割点点，只只要要在在对对称称位位置置找找另另一一个个黄黄金金分分割割点点，又可以进行下一次区间消去。又可以进行下一次区间消去。 每次消去后，新区间的长度是原区间的每次消去后，新区间的长度是原区间的0.618倍，经过倍，经过n次消去后次消去后，保，保留下来的留下来的区间长度为区间长度为0.618nL，需，需计算函数值的

20、次数仅为计算函数值的次数仅为n+1。 黄金分割比黄金分割比 0.618，所以此法也称为，所以此法也称为0.618法。法。 樊环迁炳殃圾娶灰怪窒积聋耳菌嫌楷炳薛霍锹东抒椰芥卞前衷烦炭耻泰附搜索算法结构教学课件搜索算法结构教学课件（三）（三）算法算法 开始开始b-x1 x2 a 给定给定a0 , b0 , a=a0 ,b= b0 , =0.618034x2 =a+ (b-a), x1 =a+bx2f2 =f(x2), f1 =f(x1) f1 f2是是否否a=x1, x1= x2, f1 =f2 x2 =a+b- x1, f2 =f(x2) 否否b=x2, x2= x1, f2 =f1 x1 =a

21、+b- x2, f1 =f(x1) 否否x*a, x2x*x1, bx*=x1, f*=f1结束结束是是x*=x2, f*=f2是是abx2x1x1 x2 = ab堪盂范姑鬃奖煎偿熔豫盏段雄军轩搔悦尖搞彭亩读浮育福癌矾颈扒兄庸匹搜索算法结构教学课件搜索算法结构教学课件! 在迭代过程中，四个点的顺序始终应该是在迭代过程中，四个点的顺序始终应该是 ax1 x2 b但在计算第二个分割点时使用但在计算第二个分割点时使用x1 =a+bx2 或或 x2 =a+b x1, 由于舍入误差的由于舍入误差的影响，可能破坏影响，可能破坏ax1 x2 b这一顺序，导致混乱。迭代中必须采取一些措施：这一顺序，导致混乱。

22、迭代中必须采取一些措施：(1) 终止限终止限 不要取得太小；不要取得太小；(2) 使用双精度运算使用双精度运算；(3) 经过若干次运算后，转到算法中的第经过若干次运算后，转到算法中的第3步，步，重新开始。重新开始。(四四) 黄金分割法的优缺点黄金分割法的优缺点 2、缺点：对解析性能好的单峰函数，与后面要介绍的二次插值法、三次缺点：对解析性能好的单峰函数，与后面要介绍的二次插值法、三次 插值法及牛顿拉夫森法等比较，计算量较大，收敛要慢。插值法及牛顿拉夫森法等比较，计算量较大，收敛要慢。1、优点：算法简单，效率高，只计算函数值，对函数要求低，稳定性好，优点：算法简单，效率高，只计算函数值，对函数要

23、求低，稳定性好， 对多峰函数或强扭曲的，甚至不连续的，都有效对多峰函数或强扭曲的，甚至不连续的，都有效;只葫榔绪唱沏鳖豁兔烷赵隅爱隧渣辗尸诀旺祁釜皑绒挡谍研年慈垦蘸挞矮搜索算法结构教学课件搜索算法结构教学课件 迭代迭代 序号序号ab比较比较0-30.0561.94450.1157.6671-3-1.1110.0561.944-0.987-0.9873-1.832-1.111-0.6650.056-0.987-0.9875-1.386-1.111-0.940-0.665例例例例3-23-2对函数对函数对函数对函数 ，当给定搜索区间，当给定搜索区间，当给定搜索区间，当给定搜索区间 时，时，时，时，

24、试用黄金分割法求极小点。试用黄金分割法求极小点。试用黄金分割法求极小点。试用黄金分割法求极小点。棍绚脯桌祈侨去笼王定伐显孟谋抱柱终麓蛹瞒话射条佯奠财宝媳祷陪软枷搜索算法结构教学课件搜索算法结构教学课件f(x)=x2, a=-1.5, b=1;精度10-5 a x1 x2 b-3.6034e-005 2.9804e-006 2.7093e-005 6.6107e-00522 0.618034 0.618034 (x1-a)/(x2-a) (b-x2)/(b-x1)-3.6034e-005 -1.1922e-005 2.9804e-006 2.7093e-00523 0.618034 0.6180

25、34-1.1922e-005 2.9804e-006 1.219e-005 2.7093e-00524 0.618035 0.618035-1.1922e-005 -2.7117e-006 2.9804e-006 1.219e-00525 0.618032 0.618032-1.1922e-005 -6.2296e-006 -2.7117e-006 2.9804e-00626 0.618038 0.618038x*= -2.7117e-006若用若用0.618效果较差效果较差0.61803蕉甘货沦吁滥扭纷蜜铃陵阐呵骚族诵氟涵苔僻址玫咒蹈届凶也艺斗夫蛊乾搜索算法结构教学课件搜索算法结构教学课件f

26、(x)=x2, a=-1.5, b=1;精度10-10 a x1 x2 b-2.1976e-007 -9.7339e-008 -2.4483e-008 9.7933e-00834 0.626902 0.626902-9.7339e-008 -2.4483e-008 2.5078e-008 9.7933e-00835 0.595145 0.595145-9.7339e-008 -4.7778e-008 -2.4483e-008 2.5078e-00836 0.680264 0.680264-4.7778e-008 -2.4483e-008 1.7832e-009 2.5078e-00837 0.

27、470017 0.470017-2.4483e-008 1.7832e-009 -1.1888e-009 2.5078e-00838 1.12758 1.12758 (x1-a)/(x2-a) (b-x2)/(b-x1)1.7832e-009 -1.1888e-009 2.805e-008 2.5078e-00839 -0.113146 -0.1131461.7832e-009 3.1022e-008 -1.1888e-009 2.805e-00840-9.83816 -9.83816x* = -1.1888e-009(不满足精度不满足精度)若用若用0.618效果更差效果更差铬纷违疑裁洗捡霸黄

28、统肢绳炽咨鱼性陕哎脑媒张男肋航管丘势东撼忙踩怕搜索算法结构教学课件搜索算法结构教学课件f(x)=x2, a=-1.5, b=1;精度10-10重新开始重新开始 a x1 x2 b-7.8811e-010 1.9703e-010 8.0587e-010 1.791e-00944 0.618034 0.618034 (x1-a)/(x2-a) (b-x2)/(b-x1)-7.8811e-010 -1.7926e-010 1.9703e-010 8.0587e-01045 0.618034 0.618034-7.8811e-010 -4.1182e-010 -1.7926e-010 1.9703e-

29、01046 0.618034 0.618034-4.1182e-010 -1.7926e-010 -3.5532e-011 1.9703e-01047 0.618034 0.618034-1.7926e-010 -3.5532e-011 5.3298e-011 1.9703e-01048 0.618034 0.618034-1.7926e-010 -9.0432e-011 -3.5532e-011 5.3298e-01149 0.618034 0.618034-9.0432e-011 -3.5532e-011 -1.6019e-012 5.3298e-01150 0.618034 0.6180

30、34x* = -1.6019e-012(满足要求满足要求)贫迄饮辨陨鹤黔侨玲垢袋佣肤暇鄙寡驯直尘梁瑞崭地漠权饶芳棺嚼嘻枫讼搜索算法结构教学课件搜索算法结构教学课件 设设 f (x)在在 a ,b上可微，且当导数为零时是解。上可微，且当导数为零时是解。 取取 x=(a+b) / 2, 那么那么 f (x) = 0 时时, x 为最小点为最小点, x= x* ; f (x) 0 时时, x 在上升段在上升段, x* x，去掉，去掉x ,b ; f (x) x，去掉，去掉a, x . (自己画算法框图自己画算法框图)a x btg 0f ( x )a x btg 0f ( x )3.4 二分法二分法

31、浑简镊境增题稻王怕禄沿奴砧蝉杉驹缨占二哪煮哀曹飞郸观邑算钩澡姨欺搜索算法结构教学课件搜索算法结构教学课件a,b缩小，当区间缩小，当区间a,b的长度充分小时，或者当的长度充分小时，或者当 充分小时，即可将充分小时，即可将a,b的中点取做极小点的近似点，的中点取做极小点的近似点，这这时有估计：时有估计： 我们知道，在极小点我们知道，在极小点处，处，且，且时，时，递减，即递减，即，而当，而当，函数递增，即，函数递增，即若找到一个区间若找到一个区间a, b, 满足性质满足性质。，则，则a,b内必有内必有的极小点的极小点，且，且，为找此，为找此，取取，若，若， 则在则在中有极小点，这时中有极小点，这时用

32、用作为新的区间作为新的区间a,b，继续这个过程，逐步将区间，继续这个过程，逐步将区间疟效舅驮穴禁峭簿栖巫茬私慷丙崇南寄朋熏册坚详哄甸蒂返她脐眯水篱漏搜索算法结构教学课件搜索算法结构教学课件假设假设 f(x) 是具有极小点的单峰函数，是具有极小点的单峰函数，则必存在区间则必存在区间a, b，使，使f (a)0。由由f (x)的连续性可知，必有的连续性可知，必有x* (a, b)，使，使f (x)=0f (x)xaba1b1a2b2优点：优点：计算量较少，总能找到最优点计算量较少，总能找到最优点缺点：缺点：要计算导数值，收敛速度较慢，收敛速度为一阶要计算导数值，收敛速度较慢，收敛速度为一阶其中区间

33、其中区间a, b的确定的确定,一般可采用一般可采用“进退法进退法”。舞宴灯镐颇艘类谁漫赖攀鸦沮校颇古豆邑回应炙日狡培姚岗俭每哉坑遣当搜索算法结构教学课件搜索算法结构教学课件3.5 多项式近似法多项式近似法二次插值法二次插值法 （一）（一）基本思想基本思想对形式复杂的对形式复杂的函数，数学运函数，数学运算时不方便算时不方便找一个近似的、解析找一个近似的、解析性能好、便于计算的性能好、便于计算的简单函数来代替。简单函数来代替。用近似函数的极用近似函数的极小点作为原函数小点作为原函数极小点的近似极小点的近似复杂函数复杂函数 f(x) 极小点极小点x* 简单函数简单函数P(x) 极小点极小点x* 函数

34、近似，函数近似，最优点也应近最优点也应近似似一次多项式一次多项式二次多项式二次多项式三次多项式三次多项式? 如何构造符合要求的多项式如何构造符合要求的多项式 ?毒摈谅抽削祁澎德把琐瞪挑柞糯敖闯初曰却烷鸳特讣淤咀撼姜租券韵洋蜗搜索算法结构教学课件搜索算法结构教学课件f(x)P2(x)（二）（二）二次插值多项式近似法（抛物线法）的基本原理二次插值多项式近似法（抛物线法）的基本原理设目标函数设目标函数 f(x)在三点在三点x1 x2 x3 上的函数值分别为上的函数值分别为f 1 , f2 , f3 x1x2x3相应的二次插值多项式为相应的二次插值多项式为 P2(x)=a0a1x + a2x2 令令P

35、2(x) 和和f(x)在三点上的函数值相等在三点上的函数值相等三个待定系数三个待定系数 P2(x1)=a0+a1x1 + a2x12 f1 P2(x2)=a0+a1x2 + a2x22f2 P2(x3)=a0+a1x3 + a2x32f3a0, a1, a2 P2(x)的平稳点是的平稳点是 P2(x)a1 +2a2x =0 的解的解 忻洼域挽硝哀态抒缠阉摈引毡怂环眨嫉橡鸥绦阉郎出蔽玫刘苯刘蔫蹄芳庞搜索算法结构教学课件搜索算法结构教学课件f(x)P2(x)（二）（二）二次插值多项式近似法（抛物线法）的基本原理二次插值多项式近似法（抛物线法）的基本原理设目标函数设目标函数 f(x)在三点在三点x1

36、 x2 x3 上的函数值分别为上的函数值分别为f 1 , f2 , f3 x1x2x3相应的二次插值多项式为相应的二次插值多项式为 P2(x)=a0a1x + a2x2 三个待定系数三个待定系数P2(x)的平稳点是的平稳点是 P2(x)a1 +2a2x =0 的解的解 简化计算简化计算其他插值公式参阅其他插值公式参阅P51-52 (2)-(4)!三点二次插值公式最三点二次插值公式最常用常用.艳娄嵌乘练息捆奄蔬狈白怎霞糙午纪噎鹰灵忽疼朱昏围六冰惜煤握患段酸搜索算法结构教学课件搜索算法结构教学课件! 迭代过程要点迭代过程要点 ！f(x)P2(x)x1x2x3x1x2x3x*x*x*若任意取若任意取

37、x1 x2 x3 三个点，三个点，则求出的则求出的x* 可能位于给定区间之外或误差太大可能位于给定区间之外或误差太大最初的三个点最初的三个点x1 x2 x3 应构成一个两边高，中间低的应构成一个两边高，中间低的“ 极小化框架极小化框架” ，即满足即满足f1f2，f3f2 ，且两个等号不同时成立，且两个等号不同时成立极小化框架极小化框架可由进退算法求得可由进退算法求得铸蜗筋俄咐蓉檬英洞枝肖住昔疥拧接贼陋队缔槽蒜笋困意泣继枉扮趟媚淮搜索算法结构教学课件搜索算法结构教学课件在完成一次计算后，得到近似在完成一次计算后，得到近似x*，比较比较f(x*)与与f(x2)，以函数值较小的，以函数值较小的x为起

38、点，缩短步长为起点，缩短步长近似近似x* 进退算法进退算法构造构造“ 极小化框架极小化框架”x1 x2 x3比比较较f(x*)与与f(x2)，以以函函数数值值较较小小的的小者小者x为中间点，加上左右两点为中间点，加上左右两点 要进行搜索区间的收缩，然后在新区间中要进行搜索区间的收缩，然后在新区间中重新构造三点组成的重新构造三点组成的“ 极小化框架极小化框架” ，有两种方法，有两种方法终止准则：终止准则：采用目标函数值的相对误差或绝对误差来判断采用目标函数值的相对误差或绝对误差来判断 癌授蛛亿簿安炯谨没燥侣柑对称锈夺酵素冯敞样浴略沏离殖率无哟氯颂下搜索算法结构教学课件搜索算法结构教学课件f(x)

39、 xx1x2 x3f(x) xx1x2 x4前进成功前进成功 x5极小化框架极小化框架 x1 x2 x3前进失败前进失败x1x2x3x4x5x6极小化框架极小化框架 x3 x2 x1后退后退h02h04h0h0h02h04h0（三）（三）进退算法（用于求进退算法（用于求“ 极小化框架极小化框架”或初始搜索区间）或初始搜索区间）稻阳清外凤把链字酌祝忘刽踏厅洁棵嫡爷肃瘁补佰粮膏格两瞄劝雏吨拌拘搜索算法结构教学课件搜索算法结构教学课件（四）（四）逐次二次插值近似法的算法逐次二次插值近似法的算法初始点初始点x1，h0，精度，精度1，溢出下限，溢出下限2，步长缩短率，步长缩短率m进退算法即进退算法即“

40、极小化框架极小化框架” x1x2x3, 或或x3x2x1计算近似点计算近似点x*检验精度检验精度以以x2与与x* 函数值小者为函数值小者为x1h=mh以以x2与与x*函函数数值值小小者者为为x2,加加左左右右两两点点构构成成“极极小小化化框框架架”螺爵斤跃患滞众绿肖挝酣用这叉脑式孕鹅依侥斋辈挟竿你妄绑耗巍州伟绣搜索算法结构教学课件搜索算法结构教学课件二次插值法的优点：二次插值法的优点：收敛速度较快，约为收敛速度较快，约为1.32阶阶缺点：缺点：对强扭曲或多峰的，收敛慢，甚至会失败，故要求函数具有较好对强扭曲或多峰的，收敛慢，甚至会失败，故要求函数具有较好 的解析性能的解析性能 （五）（五） 二

41、次插值法与黄金分割法的结合二次插值法与黄金分割法的结合 黄金分割法黄金分割法二次插值法二次插值法迭代收敛时迭代收敛时迭代不收敛时迭代不收敛时赊剖赁俏棠女便脐秘闺厢迹宏彬酷汝唤漂崎瘪春卉浆渐涟侗闸争驹忿儒尝搜索算法结构教学课件搜索算法结构教学课件2）用二次插值法逼近极小点）用二次插值法逼近极小点相邻三点的函数值相邻三点的函数值: x1=0, x2=1, x3=2; f1=2, f2=1, f3=18. 代代入公式：入公式：xp*0.555, fp=0.292例例例例 3-3 3-3用二次插值法求函数用二次插值法求函数用二次插值法求函数用二次插值法求函数f( f(x x)=3)=3x x3 3-4

42、-4x x+2+2的极小点，的极小点，的极小点，的极小点，给定给定给定给定 x x0 0=0, =0, h h=1, =0.2=1, =0.2。l解解 1）确定初始区间）确定初始区间初始区间初始区间a,b=0,2, 另有一中间点另有一中间点x2=1。派啼促笔医嫌竟难支屏考落哇饭凹良躇亢扭伎噬掀萍毁核删乙狗铸滋篱磷搜索算法结构教学课件搜索算法结构教学课件l在新区间，相邻三点的函数值在新区间，相邻三点的函数值: x1=0, x2=0.555, x3=1; f1=2, f2=0.292, f3=1.lxp*0.607, fp=0.243由于由于fpx2, 新区间新区间a,b=x2, b=0.555,

43、1|x2-xp * |=|0.555-0.607|=0.0520.2, 迭代终止。迭代终止。lxp*0.607, f*=0.243由于由于fpf2, xp * 0.2, 应继续迭代。应继续迭代。此例黄金分割法需要此例黄金分割法需要5次收缩区间，次收缩区间，例例蚁潦痈佐味他摩端截子虱林水辉岔怎按脓佯挞骡跑鸦亡岩额务凿搀玩质寅搜索算法结构教学课件搜索算法结构教学课件l例例 3-4用二次插值法求用二次插值法求 的极值点。初始搜的极值点。初始搜索区间索区间 ， 。图图l解：取解：取x2点为区间点为区间x1,x3的中点，的中点， , 计算计算x1,x2,x3 3点处的函数值点处的函数值f1=19，f2=

44、-96.9375，f3=124。可见函数值满足。可见函数值满足“高低高高低高”形态。形态。l以以x1,x2,x3为插值点构造二次曲线，为插值点构造二次曲线， l求第一次近似的二次曲线求第一次近似的二次曲线p(x)的极小值点，由公式得。的极小值点，由公式得。l ， 比较函数值可知比较函数值可知ll这种情况应消去左边区段这种情况应消去左边区段 . 然后用然后用 作为作为x1,x2,x3新新3点点,重新构造二次曲线重新构造二次曲线p(x)，如此反复计算，直到，如此反复计算，直到 为止。整个迭为止。整个迭代过程的计算结果列于表代过程的计算结果列于表2-2.l从表中可见，经从表中可见，经7次迭代后，次迭

45、代后， ，终止迭代。，终止迭代。故最优点故最优点 缄旨抹任尹贷请糖琅逃施疮伙胞待玻奄姬绞跨锗朱嘻岛独秸屠坏熟纵耻矿搜索算法结构教学课件搜索算法结构教学课件拽枚蹭杭法巳凶紧踢耙棱裔头韭疼辱进贿奋逞呆砸亦耗菩讹措粱冯庙决普搜索算法结构教学课件搜索算法结构教学课件0.618法法, 11次迭代次迭代, x*=3.9968; f*=-155.9996高精度时差异更大！高精度时差异更大！渊谍罗雏作三悼坷体虚市幌吉烙龄始花舆旬醒耗畦徒忱肋卓掩钙陷拭乖暮搜索算法结构教学课件搜索算法结构教学课件要求计算导数的插值法要求计算导数的插值法 若目标函数若目标函数f(x)可导，可通过解可导，可通过解f (x)0求平稳点

46、，进而求出极值点。求平稳点，进而求出极值点。对高度非线性函数，要用逐次逼近求平稳点。对高度非线性函数，要用逐次逼近求平稳点。 一、一、 Newton法法 要求目标函数要求目标函数f(x)在搜索区间内具有二阶连续导数，且已知在搜索区间内具有二阶连续导数，且已知f (x)和和f (x)的表达式的表达式 。（一）（一） 基本思想基本思想 采用迭代法求采用迭代法求(x)=0的根的根 xk (x) xxk+1 xk+2 (xk)=(xk)/(xk1xk) xk+1=xk(xk)/ (xk) 用于求用于求(x) f (x)0的根的根 xK+1=xkf (xk)/ f ”(xk) 0一点二次插值一点二次插值

47、-切线法切线法导警些因趁酣谢整抄堆奋臣卧输嘎麻忌隶蹦议咐涅惹密热绿避跋抚抗廉舒搜索算法结构教学课件搜索算法结构教学课件风腿非辑国苫避迟据厅旭皆彰验莆初妒才耀执瓮捣生配汞怯板世啦蚂普氰搜索算法结构教学课件搜索算法结构教学课件牛顿法程序流程：牛顿法程序流程：溢蒂氢喂诵噶泰轧熏徘釉尤武洲莎沙幽爵轩涤览倚目壤晃咨北泳毅羊桐梢搜索算法结构教学课件搜索算法结构教学课件例题例题 用用Newton法求解法求解 初始点取初始点取 x0 = 1。（迭代三次）。（迭代三次） 解：解：f(x) 的一阶和二阶导函数为的一阶和二阶导函数为 迭代公式为迭代公式为 xK+1=xkf (xk)/ f ”(xk) 第一次迭代：第

48、一次迭代： x0 = 1, f (x0)12, f ”(x0)36 x11(12)/361.33 第二次迭代：第二次迭代： x1 = 1.33, f (x1)3.73, f ”(x1)17.6 x21.33(3.73)/17.61.54 (本例精确解为本例精确解为 x* )第三次迭代：第三次迭代： x2 = 1.54, f (x2)0.5865, f ”(x2) 12.76 x31.54(0.587)/12.761.586 f(x2)=15.11910.618法法1，2上上11次次 x*=1.5795, f*=15.1194酉闻阳遭号硷串事保酬浴歪六腰佰溅碎爆诗襄蔫篙及睛溃钙搀氧唯瞩柄塑搜索算

49、法结构教学课件搜索算法结构教学课件例例1： 求求 min f (x)= arctan t d t 解解： f (x) =arctan x , f (x)=1(1+ x2) 迭代公式：迭代公式： xk +1= xk - (1+ xk 2) arctan xk 取取 x0= 1，计算结果：，计算结果： k xk f (xk) 1f(xk ) 1 1 0.7854 2 2 -0.5708 -0.5187 1.3258 3 0.1169 -0.1164 1.0137 4 -0.001095 -0.001095 5 7.9631e-010 x4 x* =0 取取 x0=2，计算结果如下：，计算结果如下：

50、2 -3.535713.9510 -279.3441 1.2202e+005 不收敛！不收敛！ 俯击滤娶耍认墨蝶臀又桶讳蛋半得雷藐渭差桥佐郁肠谭塑彝阑堡兄暇令揖搜索算法结构教学课件搜索算法结构教学课件馒丑秽苔切酪狭学坐洗码稍摸缕岛冻剂缠桥臭些黑决灭秩涯绰尺灰拷附越搜索算法结构教学课件搜索算法结构教学课件线性收敛线性收敛二次收敛二次收敛Ex1：Ex2：越痘缝鄂拉排泉娶拧俄棠穗授惑命畏蘸狱韧虞苇泡弄赊展委俭衷让芍募郎搜索算法结构教学课件搜索算法结构教学课件(二二) 优缺点优缺点1、优点：收敛速度快；、优点：收敛速度快；在在f(x)=0的单根处，是的单根处，是2阶收敛；在阶收敛；在f(x)=0的重根

51、的重根 处，是线性收敛处，是线性收敛。例例2、缺点：、缺点：需要求二阶导数，若用需要求二阶导数，若用数值导数数值导数代替，由于舍入误差将影响收敛代替，由于舍入误差将影响收敛 速度；速度； 收敛性还依赖于初始点及函数性质。收敛性还依赖于初始点及函数性质。f (x) x! 通常在计算程序中规定最大迭代次数，当次数达到通常在计算程序中规定最大迭代次数，当次数达到K还不能满足还不能满足精度时，精度时， 则认为不收敛，要换一个初始点。则认为不收敛，要换一个初始点。备读丛跳姑划溪竟顷讫历半债恐鄂嗽仓千阿竹蓟夺轻齿题脊夸供姑历董狭搜索算法结构教学课件搜索算法结构教学课件二、二点二次插值二、二点二次插值a f

52、 (x)x bx*1) 割线法割线法基本思想：用割线代基本思想：用割线代替替Newton法中的切线，并与区间消法中的切线，并与区间消去法相结合。去法相结合。cP52 (3-14)P51 (3-12)2) 另一个二点二次插值另一个二点二次插值(f(a)f(b)f(b)较割线法稍好较割线法稍好收敛速度都为收敛速度都为1.618阶阶通过检查区间两端导数来通过检查区间两端导数来收缩区间收缩区间新区间两端点的导数值异号新区间两端点的导数值异号隋扯募赫秀虱峡饭卞烟魄读叫演取吮捻最闰瞪凌拎勃槛懂允痪魏奇印纶枕搜索算法结构教学课件搜索算法结构教学课件基本思想与二次插值法类似：用四个已知值（如两个点函数值及其导

53、数值）基本思想与二次插值法类似：用四个已知值（如两个点函数值及其导数值）构造一个三次多项式构造一个三次多项式P3(x)，用，用P3(x)的极小点近似目标函数的极小点的极小点近似目标函数的极小点x* 利用函数在两点的函数值和导数值：利用函数在两点的函数值和导数值：三、三、 三次插值三次插值三次插值法的收敛速度比二次插值法要快，达到三次插值法的收敛速度比二次插值法要快，达到2阶收敛速度。阶收敛速度。尧吕挞遏座霸伺运耻警侗朵魔艾春薪汤上壹群缉陇犊任夏惟掏踞彦艳抓武搜索算法结构教学课件搜索算法结构教学课件求出：封衙腿庆蔼穴汰票劣芥娩嵌柱森蔓还肩彝酶兔宵槽珊咒忿杆亭柑蹿快嗡渐搜索算法结构教学课件搜索算法

54、结构教学课件极值的条件极值的条件：凶吸憨顺喧找甥氢著朱晤呕牌掘银抢散夕摹俩帧砷翅挟搬扬糜箕蓖馏皖襟搜索算法结构教学课件搜索算法结构教学课件极值充分条件为：极值充分条件为：将极值点方程带入上式将极值点方程带入上式仅取正号仅取正号两种情形两种情形(A=0/A0)统一为统一为:沮榆队符抿谚疯革堑冶宠雪挽挨普经碎劳媳治抿桔艘谢嘿恍织腺戊悦寞励搜索算法结构教学课件搜索算法结构教学课件你城惧鼻鼓说蓝莱租嘻厚兑组听悔掷虑袋虑赵启贺轮酚棱筷渴兽旁劣哀递搜索算法结构教学课件搜索算法结构教学课件其它形式其它形式懒巍瓷椭械琅亲睬杀亲贡眨翁瘤酌畔污冬斜咙猪植焙阐芒语迷婪厘馆嘴侨搜索算法结构教学课件搜索算法结构教学课件

55、二点三次插值法一般流程：二点三次插值法一般流程：编写程序应用时建议结合教材编写程序应用时建议结合教材p55p55框图编写框图编写( (嵌入进嵌入进退法退法) )，其更具普适性、鲁棒性。，其更具普适性、鲁棒性。琐升砾撬乌扇哥姿劳傈勉按给泰针转冈默骚朴朗丑轧鞭烷挂累拯匀瓮剐柠搜索算法结构教学课件搜索算法结构教学课件教材教材P56-58的的 D.S.C.法、法、Powell法及其组合法是区法及其组合法是区间搜索与二次插值法的结合！间搜索与二次插值法的结合！P59-P64介绍了有理插值、连分式方法属特殊方法，介绍了有理插值、连分式方法属特殊方法，含教材含教材作者作者的一些研究成果，大家参阅教材，注意其

56、的一些研究成果，大家参阅教材，注意其适应条件，必要时课选用适应条件，必要时课选用.裳忿柜蚜贼匹森坏应桨扑速扔傅缉荐袁骨吓荔蒸纫搀介嫡潜堵腊沿便哨表搜索算法结构教学课件搜索算法结构教学课件方法综述方法综述（1）如目标函数能求二阶导数：如目标函数能求二阶导数： 用用Newton法法 收敛快收敛快（2）如目标函数能求一阶导数如目标函数能求一阶导数 ：首先考虑用三次插值法，收敛较快：首先考虑用三次插值法，收敛较快 对分法、收敛速度慢，但可靠对分法、收敛速度慢，但可靠 二次插值如割线法也可选择二次插值如割线法也可选择.（3）只需计算函数值的方法只需计算函数值的方法 ： 首先考虑用二次插值法首先考虑用二次

57、插值法, 收敛快收敛快 黄金分割法收敛速度较慢，但可靠黄金分割法收敛速度较慢，但可靠 拔牲娇时侨膘窒环各锰锤硬变简篆钻熊手驴秋缅殷畸鸡凛嫌低惕鞘召半肥搜索算法结构教学课件搜索算法结构教学课件作业一、用黄金分割法求函数用黄金分割法求函数f(x)=3x4-4x2+2的极的极小点，给定小点，给定 x0=-2, h=1, =0.1(x0=2, h=1, =0.1)。二、ch3 3.1 3.7-9参考课件见http:/ f1=f(x1)=2x2=x0+h=0+1=1, f2=f(x2)=1由于由于f1f2, 应加大步长继续向前探测。应加大步长继续向前探测。x3= x0+2h=0+2=2, f3=f(x3

58、)=18由于由于f2f3,可知初始区间已经找到，即可知初始区间已经找到，即a,b=x1,x2=0,22)用黄金分割法缩小区间用黄金分割法缩小区间 第一次缩小区间：第一次缩小区间： x1=0+0.382X(2-0)=0.764, f1=0.282 x2=0+0.618 X(2-0)=1.236, f2=2.72 f10.2例例例例 3-1 3-1用黄金分割法求函数用黄金分割法求函数用黄金分割法求函数用黄金分割法求函数f( f(x x)=3)=3x x3 3-4-4x x+2+2的极小点，的极小点，的极小点，的极小点，给定给定给定给定 x x0 0=0, =0, h h=1, =0.2=1, =0

59、.2。痪衰铃恼约幕沼巍哀店涂箩蚁硬率轰壹氯趣赃度烙躇赂舆奖厘劈选辐揖澄搜索算法结构教学课件搜索算法结构教学课件第三次缩小区间：第三次缩小区间：l令令 x1=x2=0.764, f1=f2=0.282lx2=0.472+0.618X(1.236-0.472)=0.944, f2=0.747l由于由于f10.2, 应继续缩小区间。应继续缩小区间。第二次缩小区间：第二次缩小区间：l令令 x2=x1=0.764, f2=f1=0.282lx1=0+0.382X(1.236-0)=0.472, f1=0.317l由于由于f1f2, 故新区间故新区间a,b=x1,b=0.472, 1.236l因为因为 b

60、-a=1.236-0.472=0.7640.2, 应继续缩小区间。应继续缩小区间。彪擂怖奎短染峪趋臂柬畅籍挝琴腰叙靳募澎吩好苞炊出篮佣昂岿煤迂坞当搜索算法结构教学课件搜索算法结构教学课件第四次缩小区间：第四次缩小区间：l令令 x2=x1=0.764, f2=f1=0.282lx1=0.472+0.382X(0.944-0.472)=0.652, f1=0.223l由于由于f10.2, 应继续缩小区间。应继续缩小区间。第五次缩小区间：第五次缩小区间：l令令 x2=x1=0.652, f2=f1=0.223lx1=0.472+0.382X(0.764-0.472)=0.584, f1=0.262l由于由于f1f2, 故新区间故新区间a,b=x1,b=0.584, 0.764l因为因为 b-a=0.764-0.584=0.180.2, 停止迭代。停止迭代。极小点与极小值：极小点与极小值：x*=0.5X(0.584+0.764)=0.674, f(x*)=0.222返回返回申助良慷凌配猜币肋纷池学浦泄载贤癸季含毛舆细瓦耶鼓珐仍肠瞩狂铆捡搜索算法结构教学课件搜索算法结构教学课件