第三章-一维搜索(线性搜索)课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,机械优化设计,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,机械优化设计,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,机械优化设计,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第三章 一维搜索方法,3.1,概述,3.2,确定初始区间,3.3,缩小区间,3.4,黄金分割法（,0.618,法）,3.5,一维搜索的插值方法,第三章 一维搜索方法3.1 概述,2,第,3,章 一维搜索方法,3.1,概述,3.1.1,一维问题是多维问题的基础,求目标函数,f,(X),的极小点，从理论上说需要求解方程：,其中,那么如何来求,f,(X),的极小点呢？,基本思想,:,这种方法是逐次迭代的方法，在电子计算机上很容易实现，因此它在优化设计中被广泛地采用。,2第3章 一维搜索方法3.1 概述3.1.1 一维问题,3,这个过程称为,一维搜索过程,。,如：,则,当,S,k,方向上的任何一点可以表示为,其中,是步长因子，为实系数，此时,S,k,方向上任何一点的目标函数值,为 ，,它是参数,的一元函数,。那么在沿,S,k,方向求,的极小点，这就是求一元函数,的极小问题，它可表示为：,3这个过程称为一维搜索过程。如：则当Sk方向上的任何一点可以,一维搜索示意图,一维搜索示意图,求多元函数极值点，需要进行一系列的一维搜索。可见,一维搜索是优化搜索方法的基础,。,求解一元函数 的极小点 ，可采用,解析解法,，即利用一元函数的极值条件 求,在用函数 的导数求 时，所用的函数 是仅以步长因子 为变量的一元函数，而不是以设计点 x 为变量的多元函数 。,3.1.2,的确定方法,求多元函数极值点，需要进行一系列的一维搜索。可见一维搜,为了直接利用 的函数式求解最佳步长因子 。,把 或它的简写形式 进行泰勒展开，,取到二阶项，即,将上式对 进行微分并令其等于零，给出,极值点 应满足的条件,从而求得,为了直接利用 的函数式求解最佳步长因子,这里是直接利用函数 而不需要把它化成步长因,子 。的函数 。不过，此时需要计算 点处,梯度 和海赛矩阵,H,。,解析解法的缺点,需要进行求导计算。,对于函数关系复杂、求导困难或无法求导的情况，使用解析法将是非常不便的。,因此，在优化设计中，求解最佳步长因子 主要采用,数值解法,，利用计算机通过反复迭代计算求得最佳步长因子的近似值。,数值解法的基本思路是：首先确定 所在的搜索区间，然后根据区间消去法原理不断缩小此区间，从而获得 的数 值近似解。,这里是直接利用函数 而不需要把它化成步长因,解析法,:, f(X,(k),+ S,(k),),沿,S,(k),方向在,x,(k),点泰勒展开；, 取二次近似：,对,求导，令其为零。, 求得最优步长,解析法: 对求导，令其为零。 求得最优,数值解法,基本思路：,解析解法对于函数关系复杂、求导困难等情况难以实现。在实际优化设计中，数值解法的应用更为有效，且适合计算机的运算特点。,一维搜索也称,直线搜索,。这种方法不仅对于解决一维最优化问题具有实际意义，而且也是求解多维最优化问题的重要支柱。,一维搜索一般分为两大步骤：,(1),确定初始搜索区间,a,，,b,，该区间应是包括一维函数极小点在内的,单谷区间,。,(2),在单谷区间,a,b,内通过缩小区间寻找极小点。,先确定,在的搜索区间，然后根据区间消去法原理不断缩小此区间所，从而获得 的数值近似解。,数值解法基本思路： 解析解法对于函数关系复杂、求导困,1,、确定搜索区间的外推法,在给定区间内仅有一个谷值（或有唯一的极小点）的函数称为,单谷函数,，其区间称为,单谷区间。,函数值：,“,大,小,大,”,图形：,“,高,低,高,”,单谷区间中一定能求得一个极小点。,3.2,确定初始区间,1、确定搜索区间的外推法 在给定区间内仅有一个谷值（或有,从 开始，以初始步长 向前试探。,如果函数值上升，则步长变号，即改变试探方向。,如果函数值下降，则维持原来的试探方向，并将步长加倍。,区间的始点、中间点依次沿试探方向移动一步。,此过程一直进行到函数值再次上升时为止，即可找到搜索区间的终点。,最后得到的三点即为搜索区间的始点、中间三点和终点，形成函数值的“高低高”趋势。,单谷区间,单谷区间,f (x),0,1,3,0,f (x),3,1,说明：,单谷区间内，函数可以有不可微点，也可以是不连续函数；,f (x)0130f (x)31说明：单谷区间内，,外推方法,基本思想：,对 任选一个初始点 及初始步长 ，通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为“高,低,高”形态。,步骤：,1,）选定初始点,a,1,，初始步长,h=h,0,，计算,y,1,=f(a,1,),和,y,2,=f(a,1,+h),2,）比较,y,1,和,y,2,；,a,）如果,y,1,y,2,，向右前进，加大步长,h=2h,0,，转（,3,）向前；,b,）如果,y,1,y,3,，加大步长,h=2h,，,a,1,=a,2,a,2,=a,3,转（,3,）继续探测；,b,）如果,y,2,y3 ，加大步长h=,右图表示沿 的正向试探。每走一步都将区间的始点、中间点沿试探方向移动一步（进行换名）。经过三步最后确定搜索间 ，并且得到区间始点、中间点和终点 所对应的函数值 。,y,1,y,3,y,2,y,2,y,1,a,3,a,2,a,2,a,1,a,1,O,a,a,3,h,0,h,0,2,h,0,图3-2 正向搜索的外推法,右图表示沿 的正向试探。每走一步都将区间的始点、中,右图所表示的情况是：开始是沿 的正方向试探，但由于函数值上升而改变了试探方向，最后得到始点，中间点和终点,及它们的对应函数值,从而形成单谷区间为一维搜索区间 。,y,1,y,2,a,2,a,3,a,1,a,2,a,1,O,a,a,3,2,h,0,h,0,h,0,y,3,y,1,y,2,y,1,y,2,y,3,a,1,a,2,图3-3 反向搜索的外推法,右图所表示的情况是：开始是沿 的正方向试探，但由于,k,h,x,1,x,2,x,3,0,h,0,初始点,初始点,+ h,0,1,2h,0,初始点,初始点,+ h,0,初始点,+3h,0,2,4h,0,初始点,+ h,0,初始点,+3h,0,初始点,+7h,0,3,8h,0,初始点,+3h,0,初始点,+7h,0,初始点,+15h,0,前进搜索步骤表,khx1x2x30h0初始点初始点+ h012h0初始点初始,k,h,x,1,x,2,x,3,0,h,0,初始点,初始点,+,h,0,1,2h,0,初始点,+,h,0,初始点,初始点,-2,h,0,2,4h,0,初始点,初始点,-2,h,0,初始点,-6,h,0,3,8h,0,初始点,-2,h,0,初始点,-6,h,0,初始点,-14,h,0,后退搜索步骤表,khx1x2x30h0初始点初始点+ h012h0初始点+,19,k,h,x,1,y,1,x,2,y,2,x,3,y,3,1,0.1,0.2,0 9,0.1 8.203,0.3 6.681,2,0.4,0.1 8.203,0.3 6.681,0.7 4.429,3,0.8,0.3 6.681,0.7 4.429,1.5 7.125,解：,19khx1 y1x2 y2x3 y,20,k,h,x,1,y,1,x,2,y,2,x,3,y,3,1,0.1,-0.2,1.8 12.096,1.9 14.377,1.9 14.377,1.8 12.096,1.6 8.488,2,-0.4,1.8 12.096,1.6 8.488,1.2 4.584,3,-0.8,1.6 8.488,1.2 4.584,0.4 5.992,运用进退法确定出初始搜索区间,a,b,后，便可采用一维优化方法来求出函数,f(x),在区间内的最优点,x*,。,20khx1 y1x2 y2x,21,2.,程序框图,h=h,0,y,1,=f(x,1,),、,x,2,=x,1,+h,、,y,2,=f(x,2,),给定,x,1,、,h,0,y,1,y,2,y,2,y,3,是,h=2h,x,3,=x,2,+h,、,y,3,=f(x,3,),结束,否,h=-h,x,3,=x,1,y,3,=y,1,a=x,1,、,b=x,3,是,x,1,=x,2,y,1,=y,2,x,2,=x,3,y,2,=y,3,是,a=x,3,、,b=x,1,否,h0,否,初始进退距,前进计算,后退计算,212. 程序框图h=h0y1=f(x1)、x2=x1+h、,，,搜索区间确定之后,，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。,假定在搜索区间 内任取两点,，且,3.3,区间消去方法,， 搜索区间确定之后，采用区间消去法逐步缩,(1),f,（,a,1,）,f,（,b,1,）,则极小点必在区间,a,，,b,1,内,;,第三章-一维搜索(线性搜索)课件,(1),f,（,a,1,）,f,（,b,1,）,则极小点必在区间,1,，,b,内,;,第三章-一维搜索(线性搜索)课件,(1),f,（,a,1,）,f,（,b,1,）,则极小点必在区间,1,，,b,内,;,(3),f,（,a,1,）,=,f,（,b,1,）,则极小点必在区间,1,，,b,1,内,可以总结为两种情况：,若 ， 则取,a,b,1,为缩小后的搜索区间。,若 ，则取,a,1,b,为缩小后的搜索区间。,可以总结为两种情况：,试探法,黄金分割法,插值法,二次插值法,3,一维搜索方法分类,从前面的分析可知，每次缩短区间，只需要在区间内再插入一点并计算其函数值。,而插入点的位置，可以由不同的方法来确定。就形成了不同的一维搜索方法。,一维搜索方法分类,试探法 黄金分割法插值法,3.4,黄金分割法（,0.618,法）,黄金分割法,黄金分割法的搜索过程,3.4 黄金分割法（0.618法）黄金分割法,概述,在实际计算中，最常用的,一维搜索试探方法是黄金分割法,，又称作,0.618,法,。我们可以通过学习黄金分割法来了解一维搜索试探方法的基本思想。,在搜索区间,a,b,内适当插入两点,1,、,2,，并计算其函数值。,1,、,2,将区间分成三段。应用函数的单谷性质，通过函数值大小的比较，删去其中一段，使搜索区间得以缩短。然后再在保留下来的区间上作同样的处置，如此迭代下去，使搜索区间无限缩小，从而得到极小点的数值近似解。,3.4,黄金分割法（,0.618,法）,概述3.4 黄金分割法（0.618法）,黄金分割法是建立在区间消去法原理基础上的试探方法。,适用于,a,b,区间上的任何单谷函数求极小值问题。对函数除要求“单谷”外不作其它要求，甚至可以不连续。因此，这种方法的适应面相当广。,黄金分割法对插入点的要求：,1,）要求插入点,1,、,2,的位置相对于区间,a,b,两端点具有对称性,，即,其中 为待定常数。,1.,黄金分割法,1.黄金分割法,2,）,黄金分割法还要求,在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布,。,即每次缩小所得的新区间长度与缩小前区间长度之比（即：区间收缩率）为定值。,2）黄金分割法还要求在保留下来的区间内再插入一点所形成的区间,设原区间,a,b,长度为,1,如下图所示，保留下来的区间,a,2,长度为 ，区间缩短率为 。为了保持相同的比例分布，新插入点,3,应在 位置上，,1,在原区间的 位置应相当于在保留区间的 位置。故有,取方程正数解，得,设原区间a,b长度为1如下图所示，保留下来的区间,1,、,2,将区间分成三段,黄金分割法要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布 。,两内分点值,:,结论：,所谓黄金分割是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段长度的比值即 。,1、2将区间分成三段 黄金分割法要求在保留下来的区,黄金分割法要求插入两点：,黄金分割法区间消去示意图：,3.4,黄金分割法（,0.618,法）,黄金分割法要求插入两点：黄金分割法区间消去示意图：3.4,2.,黄金分割法的搜索过程,（,1,）,给出初始搜索区间,及收敛精度 ，将 赋以,。,（,2,）,按坐标点计算公式计算 并计算其对应的函数值,3.4,黄金分割法（,0.618,法）,2. 黄金分割法的搜索过程（1）给出初始搜索区间,（,3,）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。,3.4,黄金分割法（,0.618,法）,（3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计,（,4,）检查区间是否缩短到足够小和函数值收敛到足够精度，如果收敛条件满足，则取最后两试验点的平均值作为极小点的数值近似解。如果条件不满足则转向步骤,5,。,（,5,）产生新的插入点：,如,N,0,=0,，则取,（,5,）如果条件满足，则取最后两试验点的平均值作为极小点的数值近似解。,3.4,黄金分割法（,0.618,法）,缩短区间的总次数（迭代次数）,:,（4）检查区间是否缩短到足够小和函数值收敛到足够精度，如果收,黄金分割法程序框图,给定,否,否,是,是,止,也可采用迭代次数是否大于或等于,k,作终止准则。,黄金分割法程序框图给定否否是是止也可采用迭代次数是否大于或等,38,迭代序号,a,b,y,1,比较,y,2,0,-3,0.056,1.944,5,0.115,7.667,1,-3,-1.111,0.056,1.944,-0.987,-0.987,3,-1.832,-1.111,-0.665,0.056,-0.987,-0.987,5,-1.386,-1.111,-0.940,-0.665,例,3-3,：用黄金分割法求 的极小值 ，搜索区间是,解：,38迭代序号aby1比较y20-30.0561.94450.,39,解析解：,39解析解：,例,3-1,用黄金分割法求函数,f,(,x,)=3,x,3,-4,x,+2,的极小点，给定,x,0,=0,h,=1,=0.2,。,解：,1,）确定初始区间,a,1,=,x,0,=0,f,1,=f(a,1,)=,2,a,2,=,x,0,+,h,=0+1=1,f,2,=,f,(,a,2,)=1,由于,f,1,f,2,应加大步长继续向前探测。,a,3,=,x,0,+2,h,=0+2=2,f,3,=,f,(,a,3,)=18,由于,f,2,f,3,可知初始区间已经找到，即,a,b,=,a,1,a,3,=0,2,2,）用黄金分割法缩小区间,第一次缩小区间：,a,1,=0+0.382,(2-0)=0.764,f,1,=0.282,a,2,=0+0.618,(2-0)=1.236,f,2,=2.72,f,1,0.2,例 3-1 用黄金分割法求函数f(x)=3x3-4x+2的极,第二次缩小区间：,令,x,2,=,x,1,=0.764, f2=f1=0.282,x,1,=0+0.382,X,(1.236-0)=0.472, f1=0.317,由于,f1f2,故新区间,a,b=,x,1,b=0.472, 1.236,因为,b-a=1.236-0.472=0.7640.2,应继续缩小区间。,第三次缩小区间：,令,x,1,=,x,2,=0.764, f1=f2=0.282,x,2,=0.472+0.618,X,(1.236-0.472)=0.944, f2=0.747,由于,f10.2,应继续缩小区间。,第二次缩小区间： 第三次缩小区间：,第四次缩小区间：,令,x,2,=,x,1,=0.764, f2=f1=0.282,x,1,=0.472+0.382,X,(0.944-0.472)=0.652, f1=0.223,由于,f10.2,应继续缩小区间。,第五次缩小区间：,令,x,2,=,x,1,=0.652, f2=f1=0.223,x,1,=0.472+0.382,X,(0.764-0.472)=0.584, f1=0.262,由于,f1f2,故新区间,a,b=,x,1,b=0.584, 0.764,因为,b-a=0.764-0.584=0.180.2,停止迭代。,极小点与极小值：,x,*=0.5,X,(0.584+0.764)=0.674, f(,x,*)=0.222,第四次缩小区间：第五次缩小区间：极小点与极小值：,概述,一维搜索问题是在某一确定区间内寻求一元函数的极小点的位置，在某些情况下，如果没有函数表达式，但能够给出若干试验点处的函数值，就可以根据这些点处的函数值，利用,插值法,建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的近似值。这种方法称作,插值法,，又称作,函数逼近法,。,3.5,一维搜索的二次插值法,概述3.5 一维搜索的二次插值法,试探法,（如黄金分割法）与,插值法,的比较：,不同点,：表现在试验点（插入点）位置的确定方法不同。,试探法（如黄金分割法）与插值法的比较：不同点：表现在试验点（,多项式是函数逼近的一种常用工具。,在搜索区间内可以利用若干试验点处的函数值来构造低次多项式，用它作为函数的近似表达式，并用这个多项式的极小点作为原函数极小点的近似。,常用的插值多项式为,二次多项式。,牛顿法（切线法）,利用一点的函数值、一阶导数值和二阶导数值来构造二次函数。,二次插值法（抛物线法）,利用三个点的函数值形成一个抛物线来构造二次函数。,多项式是函数逼近的一种常用工具。,1,、牛顿法（切线法）,对于一维搜索函数 ，假定已经给出极小点的一个较好的近似点 ，在 点附近用一个二次函数 来逼近函数,。,然后以该二次函数 的极小点作为 极小点的一个新的近似点 。根据极值必要条件：,1、牛顿法（切线法） 对于一维搜索函数,牛顿法的几何解释：,在上图中，在 处用一抛物线 代替曲线 ，相当于用一斜线 代替 。这样各个近似点是通过对 作切线求得与 轴的交点找到，故牛顿法又称为切线法。,牛顿法的几何解释：在上图中，在 处用一抛物线,牛顿法的计算步骤：,1,）给定初始点,，控制误差,，并令,2,）计算,3,）求,4,）若,，则求得近似解 ，,停止计算，否则作,5,）。,5,）令,转,2,）。,牛顿法的计算步骤：1）给定初始点 ，控制误差 ，并令 2）计,例题：,给定,，试用,牛顿法求其极小点 。,解：,1,）给定初始点,，控制误差,2,）,3,）,4,）,例题： 给定 ，试用牛顿法求其极小点 。 解：1）给定初,重复上边的过程，进行迭代，直到,为止。可得到计算结果如下表,:,表,3-2,牛顿法的搜索过程,k,0,1,2,3,4,值,a,k,3,5.16667,4.33474,4.0396,4.00066,f(a,k,),-52,153.35183,32.30199,3.38299,0.00551,f(a,k,),-24,184.33332,109.44586,86.86992,84.04720,a,k+1,5.16667,4.33474,4.03960,4.00066,4.00059,重复上边的过程，进行迭代，直到 为止。可得到计算结果如下表:,优点：收敛速度快。,缺点：每一点都要进行二阶导数，工作量大；,当用数值微分代替二阶导数，由于舍入误差会影响迭代速度；,要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点。,牛顿法的特点：,优点：收敛速度快。缺点：每一点都要进行二阶导数，工作量大；,、二次插值法（抛物线法）,基本思想：,二次插值的基本思想是利用目标函数在不同,3,点的函数值构成一个与原函数,f,(,x,),相近似的二次多项式,p,(,x,),，以函数,p,(,x,),的极值点,x,p,(,即,p ,(,x*,p,)=0,的根,),作为目标函数,f,(,x,),的近似极值点。,、二次插值法（抛物线法）基本思想：二次插值的基本思想是利用,（,1,）二次插值多项式的构成及其极值点,设 在单谷区间中的三点,的相应函数值,，则可以做出,如下的二次插值多项式：,（1）二次插值多项式的构成及其极值点设,多项式,的极值点可从极值的必要条件求得,，即,，,为了确定这个极值点，只需计算出系数,a,1,和,a,2,。其方法法是利用a,0、,a,1、,a,2,的联立方程组中相邻两个方程消去,a,0,，从而得到关于a,1、,a,2,的方程组,多项式 的极值点可从极值的必要条件求得，即 ， 为了确定这,解得,所以,解得,如果令,则,这样就得到了,f,(,),极小点,*,的近似解,p,。,）如果区间长度,足够小，则由,便得出我们所要求的近似极小点,如果令则这样就得到了f() 极小点*的近似解p。 ）,2,）如果不满足，必须缩小区间,，根据区间消取法,原理不断缩小区间。,根据区间消去法原理，需要已知区间内两点的函数值。其中点,2,的函数值,y,2,=f（,2,）,已知，另外一点可取,p,点并计算其函数值y,p,=f（,p,）。,当 y,2,y,p,时取,1,，,p,为缩短后的搜索区间（如右图）。,当y,2,y,p,时取,2,，,3,为缩短后的搜索区间。,2）如果不满足，必须缩小区间 ，根据区间消取法原理不断缩小区,二,次,插,值,法,程,序,框,图,二,例1：,用二次插值法求,上的极小点。,1,2,1,4,4.5,2,4.5,4.705120,3,5,5,y,1,-0.756802,-0.977590,y,2,-0.977590,-0.999974,y,3,-0.958924,-0.958924,p,4.705120,4.710594,y,p,-0.999974,-0.999998,二次插值法计算过程示例,例1： 用二次插值法求 上的极小点。 12144.52,例,2,用二次插值法求函数,f,(,x,)=3,x,3,-4,x,+2的极小点，给定,x,0,=0,=0.2,。,2,）用二次插值法逼近极小点,相邻三点的函数值,:,x,1,=0,x,2,=1,x,3,=2;,f,1,=2,f,2,=1,f,3,=18.,代入公式：,x,p,*,0.555, f,p,=0.292,解,:,1,）确定初始区间,初始区间,a,b,=0, 2,中间点,x,2,=1,f,(,x,2,)=1,。,例 2 用二次插值法求函数f(x)=3x3-4x+2的极小点,由于,f,p,f,2,x,p,*,0.2,应继续迭代。,在新区间，相邻三点的函数值,:,x,1,=0,x,2,=0.555,x,3,=1;,f,1,=2,f,2,=0.292,f,3,=1,代入,x,p,*,公式计算得：,x,p,*,0.607, f,p,=0.243,由于,f,p,x,2,新区间,a,b,=,x,2,b,=0.555, 1,|,x,2,-,x,p,*,|=|0.555-0.607|=0.0520.2,迭代终止。,x,p,*,0.607, f*=0.243,由于fpf2, xp * x2, 新区间a, b,例 3 用二次插值法求 的极值点。初始搜索区间 ， 。,解：取,x,2,点为区间,x,1,x,3,的中点 ， 计算,x,1,x,2,x,3,3点处的函数值,f,1,=19，,f,2,=-96.9375，,f,3,=124。可见函数值满足“高低高”形态。,以,x,1,x,2,x,3,为插值点构造二次曲线。,求第一次近似的二次曲线,p,(,x,),的极小值点，由公式得：,比较函数值可知,例 3 用二次插值法求,这种情况应消除左边区段 。然后用 作为,x,1,x,2,x,3,新,3,点,重新构造二次曲线,p,(,x,),，如此反复计算，直到 为止。,整个迭代过程的计算结果列于表。,这种情况应消除左边区段 。然后用,第三章-一维搜索(线性搜索)课件,插值法和试探法的比较,试探法,中试验点位置是由某种给定的规律确定的，它不考虑函数值的分布。例如，黄金分割法是按等比例,0.618,缩短率确定的。,插值法,中，试验点位置是按函数值近似分布的极小点确定的。,试探法,仅仅利用了试验点函数值大小的比较，而,插值法,还要利用函数值本身或者其导数信息。,试探法,仅对试验点函数值的大小进行比较，而函数值本身的特性没有得到充分利用，这样即使对一些简单的函数，例如二次函数，也不得不象一般函数那样进行同样多的函数值计算。,插值法,是利用函数在已知试验点的值（或导数值）来确定新试验点的位置。当函数具有比较好的解析性质时（例如连续可微性），,插值法,比,试探法,效果更好。,插值法和试探法的比较,复习,初始区间的确定方法,黄金分割算法,二次差值的计算,复习 初始区间的确定方法,