第三章一维搜索方法采用数学规划法求函数极值点的迭代计算：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整个迭代过程的计算结果列于表整个迭代过程的计算结果列于表。