《一维搜索方法.ppt》由会员分享，可在线阅读，更多相关《一维搜索方法.ppt（36页珍藏版）》请在三一办公上搜索。
1、第三章一维搜索方法,采用数学规划法求函数极值点的迭代计算：,K+1次迭代的搜索方向,搜索的最佳步长因子,称为一维搜索。,是优化搜索方法的基础。,求解一元函数 的极小点,，可用解析法。,上式求的极值，即求导数为零。,则,从上式看，需要求导进行计算，对于函数关系复杂的，解析法十分不便。,数值法的基本思路：确定 的搜索区间，在不断缩小区间，最终获得近似值。,1、单谷(峰）区间 在给定区间内仅有一个谷值的函数称为单谷函数，其区间称为单谷区间。,第二节 搜索区间的确定和区间消去法原理,一、确定搜索区间的外推法,函数值：“大小大”图形：“高低高”,单谷区间中一定能求得一个极小点,2.找初始单谷区间是一维搜
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）如y1y2,向左后退；h h0，将a1与a2，y1与y2的 值互换。转（3）向后探测；（c）如y1y2，极小点在a1和a1h之间。,(3）产生新的探测点a3a1h，y3f(a3);(4)比较
3、函数值 y2与y3：（b）如y2y3,加大步长 h2 h，a1=a2,a2=a3,转（3）继续探测。（a）如y2y3,则初始区间得到：a=mina1,a3，b=maxa3,a1，函数最小值所在的区间为a，b。,进退法程序框图,搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。假定在搜索区间内a,b 任取两点a1,b1;,f1f（a1），f2f（b1）,区间消去法原理,一、基本思想,f1f（a1），f2f（b1）(1)如f1f2,则缩小的新区间为a1,b;(3)如f1=f2,则缩小的新区间为a1,b1,综合为两种情况：若 则取 为缩短后的搜索区间。若 则取 为缩短后的
4、搜索区间。,三、一维搜索方法的分类,从前面的分析可知，每次缩短区间，只需要在区间内在插入一点并计算其函数值。,而插入点的位置，可以由不同的方法来确定。就形成了不同的一维搜索方法。,第三节 一维搜索的试探法,最常用的一维搜索试探法是黄金分割法，又称0.618法。,要求插入点a1、a2的位置相对于区间a,b两端点具有对称性。,除对称要求外，黄金分割法还要求在保留下来的区间再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布。,2,所谓的“黄金分割”是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段的比值，即,黄金分割法的搜索过程：1）给出初始搜索区间及收敛精度，将
5、 赋以0.618。,2）按坐标点计算公式计算,；并计算其对应的函数值。,3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，需进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。如果，则新区间 令 记N0=0；如果，则新区间，令，记N0=1；,4）检查区间是否缩短到足够小和函数值收敛到足够精度，如果收敛条件满足，则取最后两试验点的平均值作为极小点的数值近似解。如果条件不满足则转向步骤5）。,如N0=0，则取,如N0=1，则取,5）产生新的插入点：,转向3）进行新的区间缩小。,例 3-1 用黄金分割法求函数f(x)=3x3-4x+2的极小点，给定 x0=0,h=1,=0
6、.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,2,2）用黄金分割法缩小区间 第一次缩小区间：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,第二次缩小区间：令 x2=x1=0.764,f2=f1=0.282 x1=0+0.382X(1.236-0)=0.472,f1=0.317由于f1f
7、2,故新区间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由于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
8、(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,停止迭代。,极小点与极小值：x*=0.5X(0.584+0.764)=0.674,f(x*)=0.222,例3-2 对函数，当给定搜索区间 时，试用黄金分割法求极小点。,第四节 一维搜索的插值方法,假定要在某一区间内寻找函数的极小点的位置，虽然没有函数表达式，但能够给出若干试验点处的函数值。,我们可以根据这些点处的函数值，利用插值的方法建立函数的近似表达式，进而求处函数的极小点，作为原来函数的极小点的近似值。这种方法称作插值
9、法，也称函数逼近法。,一、牛顿法（切线法）,函数很接近，因此，在 点附近用一个二次函数 逼近。,即,依次继续下去，可得牛顿法迭代公式：,牛顿法的几何解释：,牛顿法的计算步骤：,给定初始点，控制误差，并令k=0。,1）计算,2）求,优点：收敛速度快。,缺点：每一点都要进行二阶导数，工作量大；,要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点。,二、二次插值（抛物线法）,，作出如下的二次插值多项式,它应满足条件,（1）,从极值的必要条件求得,（2）,（3）,要求出系数 和，联立方程组（1）、（2）、（3）。,令,所以,则,例 33 用二次插值法求函数f(x)=3x3-4x+2的极小
10、点，给定 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,由于fp0.2,应继续迭代。,例 3-4 用二次插值法求 的极值点。初始搜索区间，。,解：取x2点为区间x1,x3的中点，,计算x1,x2,x3 3点处的函数值f1=19，f2=-96.9375，f3=124。可见函数值满足“高低高”形态。,以x1,x2,x3为插值点构造二次曲线，求第一次近似的二次曲线p(x)的极小值点，由公式得：，比较函数值可知,这种情况应消除左边区段。然后用 作为x1,x2,x3新3点,重新构造二次曲线p(x)，如此反复计算，直到 为止。,整个迭代过程的计算结果列于表。,
