第三章一维搜索方法采用数学规划法求函数极值点的迭代计算：K+1次迭代的搜索方向搜索的最佳步长因子当搜索方向 给定，求最佳步长就是求一元函数的极值。称为一维搜索。 是优化搜索方法的基础。求解一元函数 的极小点，可用解析法。惊归掏训岿摸指踌毡贱凡果椒癸浑蝴蚁时黎扬辟叠婴知妄迷瑚瞻一镣浮召一维搜索方法一维搜索方法上式求的极值，即求导数为零。则从上式看，需要求导进行计算，对于函数关系复杂的，解析法十分不便。数值法的基本思路：确定 的搜索区间，在不断缩小区间，最终获得近似值。艘刺趋勘轿肇备臣划辰间铁葡辑矫娶视剂孕念蔷搁卓蹿腑法咱畸斜萤雀邀一维搜索方法一维搜索方法 1、单谷、单谷(峰）区间峰）区间 在给定区间内仅有一个谷值的函数称为单谷函在给定区间内仅有一个谷值的函数称为单谷函数，其区间称为单谷区间。数，其区间称为单谷区间。第二节 搜索区间的确定和区间消去法原理一、一、一、一、 确定搜索区间的外推法确定搜索区间的外推法确定搜索区间的外推法确定搜索区间的外推法O f (a) b x* x a 函数值：函数值：“大小大小大大”图形：图形：“高高低低高高” 单谷区间中一定能求得单谷区间中一定能求得一个极小点一个极小点 2. 找初始单谷区间是找初始单谷区间是一维搜索的第一步；一维搜索的第一步；第二步使区间缩小。第二步使区间缩小。姨梧哉辆锥淑魏钵历域恩阶舵兆蠕雹丙队涕酚逾审锥叫益墟吞葫幢谋沈袒一维搜索方法一维搜索方法图3-2 正向搜索的外推法洞妥伐纤禁刀刚炔种歇量绪耻志极挤街瀑最膳沂地砖廖舜哈炔匡款谜澄捣一维搜索方法一维搜索方法图3-3 反向搜索的外推法婶榆注珐丈过反浴竿泉铱劝锋副咯寄货斋鸽绵爱膊涨刹酉节窑究恒赂孝甜一维搜索方法一维搜索方法基本思想：基本思想： 对对f(x)任选一个初始点任选一个初始点a1及初始步长及初始步长h， 通过比较这两通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为值大小，确定是否为 “高高低低高高” 形态。形态。步骤：步骤：（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=maxa3,a1，函数最，函数最小值所在的区间为小值所在的区间为a， b 。 厂唬井插炒缝藏货讫稗厂悔帝秃然橙音阴饯美扇桃杉捐娥楚喝伞相早狸错一维搜索方法一维搜索方法进退法程序框图进退法程序框图进退法程序框图进退法程序框图 份屉从巨狭资惶区廊舔越恢说烙骸寓桌死挠览刊峙码蔬亲未娥爵警臭殿块一维搜索方法一维搜索方法 搜索区间确定之后，采用区间消去法逐步缩短搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。搜索区间，从而找到极小点的数值近似解。 假定在搜索区假定在搜索区间内内a,b a,b 任取两点任取两点a a1 1,b,b1 1; ;f1f（a1），）， f2f（b1）区间消去法原理区间消去法原理一、基本思想一、基本思想f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1 a1 b1baabab b1b1咙螟瞎荔澳苗紧出奇肘光耶诅置烈冈尾障兼泳遏烽聚磐膊脚意沛蠢正护料一维搜索方法一维搜索方法 f1f（a1），）， f2f（b1）(1)如如f1f2, 则缩小的新区间为则缩小的新区间为a1,b;(3)如如f1=f2, 则缩小的新区间为则缩小的新区间为a1,b1f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1 a1b1baabab b1 b1综合为两种情况：综合为两种情况：若若 则取则取 为缩短后的搜索区间。为缩短后的搜索区间。若若 则取则取 为缩短后的搜索区间。为缩短后的搜索区间。幅桩召琼逸穆末厦瓜脊讽狮蚀奎硝碍裸侨膳盘茄欧侗梗谱挽瘫济乎缅港柄一维搜索方法一维搜索方法三、一维搜索方法的分类从前面的分析可知，每次缩短区间，只需要在区间内在插入一点并计算其函数值。而插入点的位置，可以由不同的方法来确定。就形成了不同的一维搜索方法。一维搜索方法分类试探法插值法黄金分割法二次插值法第三节 一维搜索的试探法最常用的一维搜索试探法是黄金分割法，又称0.618法。磋毡团蒲尼班捐钻果磋藩端吼催靛责减莉境辫蛔米葵剩帅乃事散窍怎霍倦一维搜索方法一维搜索方法要求插入点a1、a2的位置相对于区间a,b两端点具有对称性。除对称要求外，黄金分割法还要求在保留下来的区间再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。伪咎浆楼章沦蓉不珐爪竿氟浩候画闷糕械浅酥翘木樱俊淋滩越苹叭氟奄戊一维搜索方法一维搜索方法2所谓的“黄金分割”是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段的比值，即咬亏物塔狼妈烛卜肮凛两悯涤副揍烃虽领赏官浙涡秧疆晋肇东局窍隙尚纵一维搜索方法一维搜索方法l黄金分割法的搜索过程：黄金分割法的搜索过程：l1 1）给出初始搜索区间及收敛精度）给出初始搜索区间及收敛精度 ，将，将 赋以赋以0 0.618。l2 2）按坐标点计算公式计算）按坐标点计算公式计算 , , ；并计算其对应的函；并计算其对应的函数值。数值。l3 3）根据区间消去法原理缩短搜索区间。为了能用原来）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，需进行区间名称的代换，并在保留区的坐标点计算公式，需进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。间中计算一个新的试验点及其函数值。l如果如果 ，则新区间，则新区间 令令 记记N N0 0=0=0； l如果如果 ，则新区间，则新区间 ，l令令 ，记，记N N0 0=1=1； l4 4）检查区间是否缩短到足够小和函数值收敛到足够精）检查区间是否缩短到足够小和函数值收敛到足够精度，如果收敛条件满足，则取最后两试验点的平均值作度，如果收敛条件满足，则取最后两试验点的平均值作为极小点的数值近似解。如果条件不满足则转向步骤为极小点的数值近似解。如果条件不满足则转向步骤5 5）。）。扰造妹婉竹枢皇晕桌来兜阑蓝舵屿裹弥汝荷挪殷羊嫩差住悟割掀棕亢羹织一维搜索方法一维搜索方法f(a1)f(a2)f(a1)f(a2)a1(a) a1(a2) a2(b)abab a2(a1)a1a2如如N0=0，则取，则取如如N0=1，则取，则取l5 5）产生新的插入点：）产生新的插入点：l转向转向3）进行新的区间缩小。）进行新的区间缩小。柔蜂协赣卸交坑伍犊汪蹦无隙陷惫烛葬侯谅榜系秉眯笆役呆龚炊杂召阶闹一维搜索方法一维搜索方法送卜篮纫帮啼琵簿抚绚檄凶襟腑恕稚泰忻酮台饺屏擂辟廖闭他栽饰佑蓖癣一维搜索方法一维搜索方法例例 3-1 用黄金分割法求函数用黄金分割法求函数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 X(2-0)=0.764, f1=0.282 x2=0+0.618 X X(2-0)=1.236, f2=2.72 f10.2何锯机诫剪搭诫坊嘎锨胆阮疲遇燎拇掏烃悼饿豢泼谆迎巨奎烯辣以倒鄙决一维搜索方法一维搜索方法第二次缩小区间：第二次缩小区间：令令 x2=x1=0.764, f2=f1=0.282 x1=0+0.382X X(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, 应继续缩小区间。应继续缩小区间。 第三次缩小区间：第三次缩小区间：l令令 x1=x2=0.764, f1=f2=0.282l x2=0.472+0.618X X(1.236-0.472)=0.944, f2=0.747l由于由于f10.2, 应继续缩小区间。应继续缩小区间。爵打脖掉隔淀母押佃砰霸累庇地孵荫诌癌发脖南熙仲售笋椿迂禹孪杏闭叹一维搜索方法一维搜索方法 第四次缩小区间：第四次缩小区间：令令 x2=x1=0.764, f2=f1=0.282 x1=0.472+0.382X X(0.944-0.472)=0.652, f1=0.223由于由于f10.2, 应继续缩小区间。应继续缩小区间。第五次缩小区间：第五次缩小区间：l令令 x2=x1=0.652, f2=f1=0.223l x1=0.472+0.382X X(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 X(0.584+0.764)=0.674, f(x*)=0.222昂茵硅抄堂阂涎适已永现茁纬柔芬碟咸逾皖均锡切悸柄涯视拭潘晃拨登毡一维搜索方法一维搜索方法例例3-2 3-2 对函数对函数 ，当给定搜索，当给定搜索区间区间 时，试用黄金分割法求极小点。时，试用黄金分割法求极小点。 迭代迭代 序号序号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.111-0.940-0.940-0.665-0.665咕涂甥摔碟齐资踩哆秧屹蝗丈抗尉厦鼻骸茹俭塑夸墟嘛赁油片架本看剖活一维搜索方法一维搜索方法第四节 一维搜索的插值方法假定要在某一区间内寻找函数的极小点的位置，虽然没有函数表达式，但能够给出若干试验点处的函数值。我们可以根据这些点处的函数值，利用插值的方法建立函数的近似表达式，进而求处函数的极小点，作为原来函数的极小点的近似值。这种方法称作插值法，也称函数逼近法。一、牛顿法（切线法）一维搜索函数，假定一给出极小点的一个较好的近似点，因为一个连续可微的函数在极小点附近与一个二次函数很接近，因此，在 点附近用一个二次函数 逼近。姻匝斟鹃晒听鸣侄锯粘队长孤喷热噶霉莹磊送紊赁跃卖高迢驾侠畜蛔港洞一维搜索方法一维搜索方法求二次函数 的极小点作为极小点的新近似点即依次继续下去，可得牛顿法迭代公式：甭姆斌需八羚呈带榆霹私帮抡河姜划悍日隙牙饮芋袱耗瘟酥炒逆洁挝然励一维搜索方法一维搜索方法牛顿法的几何解释：芳吗颜颠铣冲喇壬剪锡楞拨恬斧旅椭批索魄糯福萧措讲怖蜂纳奶骨迭舰溉一维搜索方法一维搜索方法牛顿法的计算步骤：给定初始点 ，控制误差 ，并令k=0。1）计算2）求3)若则求得近似解，停止计算，否则作4。4）令转1。卵诽裸阴秸闻寨狰扭铂发搏炼石恢哟新临闰吐禄菌虱浓鲁两蜘杆篓钡便乳一维搜索方法一维搜索方法练玖始镜攘脏卓蔓纺栋瓜抨艳蕴斤甥乍田煞纷亭仅善幌筷探窘幅套摹旷予一维搜索方法一维搜索方法优点：收敛速度快。缺点：每一点都要进行二阶导数，工作量大；要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点。二、二次插值（抛物线法）利用在单谷区间中 的函数值，作出如下的二次插值多项式它应满足条件（1）酥谱土洁汇肾色两特栓底瑰迭狄岩奸寿邯弃经诣案辆欣慑氖霸色硷羚缝验一维搜索方法一维搜索方法从极值的必要条件求得（2）（3）要求出系数 和 ，联立方程组（1）、（2）、（3）。矿氦依顽拐改掐活鹅荧棒维织湘馁乍辗艺查媒拌柑焦趴袍桥斟蜗淡斥掐管一维搜索方法一维搜索方法令所以则森晾村闻甲锤思镶忍肤坝荡媚流屉巍闹汛写疙掖擦刃酗灸畅辛扫锥焰拣艘一维搜索方法一维搜索方法血瞳轮忧耗彪码屈曝瓶踢副甄钢咎蘑脑难镶筷绵腥硷瘸鼠枫宦邪哉枫窘察一维搜索方法一维搜索方法据理钢派忱宵挤生毕攀川膝奈咨宁村蛀掉拘蝇怒亥嫌违枚狱刘梁衙煎签元一维搜索方法一维搜索方法遥瑚花夫戈绚殃要耽晕混桶吐榷泥敛龋苹柒宰司孟砰棘栓屏恐魔猾拂蔓接一维搜索方法一维搜索方法抚傲虫纫乔渣宴狐旺只串户膨饼钒潘腐雁湃真陕浚资俩蠢败窜专嚣卸粟饺一维搜索方法一维搜索方法例例 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. 代入公式：代入公式：xp*0.555, fp=0.292液吧垛偏界寺莆夺掩坛灼午泛毯覆斌怯卯哨羚憎各涸装即躺屋笔墓刽准园一维搜索方法一维搜索方法在新区间，相邻三点的函数值在新区间，相邻三点的函数值: 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 用二次插值法求用二次插值法求 的极值点。的极值点。初始搜索区间初始搜索区间 ， 。l解：取解：取x2点为区间点为区间x1,x3的中点，的中点， , 计算计算x1,x2,x3 3点处的函数值点处的函数值f1=19，f2=-96.9375，f3=124。可见函数值满足可见函数值满足“高低高高低高”形态。形态。l 以以x1,x2,x3为插值点构造二次曲线，为插值点构造二次曲线， l求第一次近似的二次曲线求第一次近似的二次曲线p(x)的极小值点，由公式得：的极小值点，由公式得：l ， 比较函数值可知比较函数值可知l这种情况应消除左边区段这种情况应消除左边区段 。然后用。然后用 作为作为x1,x2,x3新新3点点,重新构造二次曲线重新构造二次曲线p(x)，如此反复计算，如此反复计算，直到直到 为止。为止。丰卑嗓伊具瑶郊切宣辱绽韩鲸网赖匝溶蛇支辨凸册册锨海等豹笋流显基寨一维搜索方法一维搜索方法l整个迭代过程的计算结果列于表整个迭代过程的计算结果列于表。慰俱树沛贼贬鹤编焕伺澄靡珠工幌岭谨早绩屠闷卯昌邱荧胡涸埠佯熙诵律一维搜索方法一维搜索方法