一维搜索(线性搜索)课件

第三章第三章 一维搜索方法一维搜索方法3.1 概述概述3.2 确定初始区间确定初始区间3.3 缩小区间缩小区间3.4 黄金分割法（黄金分割法（0.618法）法）3.5 一维搜索的插值方法一维搜索的插值方法2第3章 一维搜索方法3.1 概述3.1.1 一维问题是多维问题的基础 求目标函数 f(X)的极小点，从理论上说需要求解方程：其中那么如何来求 f(X)的极小点呢？基本思想:这种方法是逐次迭代的方法，在电子计算机上很容易实现，这种方法是逐次迭代的方法，在电子计算机上很容易实现，因此它在优化设计中被广泛地采用。因此它在优化设计中被广泛地采用。3这个过程称为一维搜索过程。如：如：则则当当Sk方向上的任何一点可以表示为其中是步长因子，为实系数，此时 Sk 方向上任何一点的目标函数值为 ，它是参数的一元函数。那么在沿 Sk 方向求的极小点，这就是求一元函数 的极小问题，它可表示为：一维搜索示意图一维搜索示意图 求多元函数极值点，需要进行一系列的一维搜索。可见求多元函数极值点，需要进行一系列的一维搜索。可见一一维搜索是优化搜索方法的基础维搜索是优化搜索方法的基础。求解一元函数求解一元函数 的极小点的极小点 ，可采用，可采用解析解法解析解法，即利用一元函数的极值条件即利用一元函数的极值条件 求求n在用函数在用函数 的导数求的导数求 时，所用的函数时，所用的函数 是仅以步长因子是仅以步长因子 为变量的一元函数，而不是以为变量的一元函数，而不是以设计点设计点 x x 为变量的多元函数为变量的多元函数 。3.1.2 的确定方法的确定方法为了直接利用为了直接利用 的函数式求解最佳步长因子的函数式求解最佳步长因子 。把把 或它的简写形式或它的简写形式 进行泰勒展开，进行泰勒展开，取到二阶项，即取到二阶项，即 将上式对将上式对 进行微分并令其等于零，给出进行微分并令其等于零，给出 极值点极值点 应满足的条件应满足的条件 从而求得从而求得这里是直接利用函数这里是直接利用函数 而不需要把它化成步长因而不需要把它化成步长因子子 。的函数。的函数 。不过，此时需要计算。不过，此时需要计算 点处点处梯度梯度 和海赛矩阵和海赛矩阵 H H 。n解析解法的缺点解析解法的缺点需要进行求导计算。需要进行求导计算。o对于函数关系复杂、求导困难或无法求导的情况，使用对于函数关系复杂、求导困难或无法求导的情况，使用解析法将是非常不便的。解析法将是非常不便的。因此，在优化设计中，求解最佳步长因子因此，在优化设计中，求解最佳步长因子 主要采用主要采用数数值解法值解法，利用计算机通过反复迭代计算求得最佳步长因子，利用计算机通过反复迭代计算求得最佳步长因子的近似值。的近似值。n数值解法的基本思路是：首先确定数值解法的基本思路是：首先确定 所在的搜索区间，所在的搜索区间，然后根据区间消去法原理不断缩小此区间，从而获得然后根据区间消去法原理不断缩小此区间，从而获得 的数的数 值近似解。值近似解。解析法解析法:f(X f(X(k)(k)+S+S(k)(k)沿沿S S(k)(k)方向在方向在x x(k)(k)点泰勒展开；点泰勒展开；取二次近似：取二次近似：对对求导，令其为零。求导，令其为零。求得最优步长求得最优步长数值解法数值解法基本思路：基本思路：解析解法对于函数关系复杂、求导困难等情况难以解析解法对于函数关系复杂、求导困难等情况难以实现。在实际优化设计中，数值解法的应用更为有效，实现。在实际优化设计中，数值解法的应用更为有效，且适合计算机的运算特点。且适合计算机的运算特点。一维搜索也称一维搜索也称直线搜索直线搜索。这种方法不仅对于解决。这种方法不仅对于解决一维最优化问题具有实际意义，而且也是求解多维最优一维最优化问题具有实际意义，而且也是求解多维最优化问题的重要支柱。化问题的重要支柱。一维搜索一般分为两大步骤：一维搜索一般分为两大步骤：(1)(1)确定初始搜索区间确定初始搜索区间aa，bb，该区间应是包括一维函数，该区间应是包括一维函数极小点在内的极小点在内的单谷区间单谷区间。(2)(2)在单谷区间在单谷区间a,ba,b内通过缩小区间寻找极小点。内通过缩小区间寻找极小点。先确定先确定 在的搜索区间，然后根据区间消去法原理在的搜索区间，然后根据区间消去法原理不断缩小此区间所，从而获得不断缩小此区间所，从而获得 的数值近似解。的数值近似解。1、确定搜索区间的外推法 在给定区间内仅有一个谷值（或有唯一的极小点）的函数称为单谷函数，其区间称为单谷区间。函数值：“大小大”图形：“高低高”单谷区间中一定能求得一个极小点。3.2 确定初始区间确定初始区间o从从 开始，以初始步长开始，以初始步长 向前试探。向前试探。n如果函数值上升，则步长变号，即改变试探方向。如果函数值上升，则步长变号，即改变试探方向。n如果函数值下降，则维持原来的试探方向，并将步长加倍。如果函数值下降，则维持原来的试探方向，并将步长加倍。n区间的始点、中间点依次沿试探方向移动一步。区间的始点、中间点依次沿试探方向移动一步。n此过程一直进行到函数值再次上升时为止，即可找到搜索此过程一直进行到函数值再次上升时为止，即可找到搜索区间的终点。区间的终点。n最后得到的三点即为搜索区间的始点、中间三点和终点，最后得到的三点即为搜索区间的始点、中间三点和终点，形成函数值的形成函数值的“高低高高低高”趋势。趋势。单谷区间单谷区间f(x)0130f(x)31说明：单谷区间内，函数可以有不可微点，也可以是不连续函数；外推方法基本思想：基本思想：对对 任选一个初始点任选一个初始点 及初始步长及初始步长 ，通过比较这两点函数值的大小，确定第三点位置，比较这通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为三点的函数值大小，确定是否为“高高低低高高”形态。形态。步骤：步骤：1 1）选定初始点）选定初始点a a1 1，初始步长，初始步长h=hh=h0 0，计算，计算y y1 1=f(a=f(a1 1)和和y y2 2=f(a=f(a1 1+h)+h)2 2）比较）比较y y1 1和和y y2 2；a a）如果）如果y y1 1yy2 2，向右前进，加大步长，向右前进，加大步长h=2hh=2h0 0，转（，转（3 3）向前；）向前；b b）如果）如果y y1 1yyy3 3 ，加大步长，加大步长h=2hh=2h，a a1 1=a=a2 2,a,a2 2=a=a3 3,转（转（3 3）继）继续探测；续探测；b b）如果）如果y y2 2y0h0否否初始进退距初始进退距前进计算后退计算，搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找到极小点的数值近似解。假定在搜索区间 内任取两点 ，且 3.3 区间消去方法区间消去方法(1)(1)f f（a a1 1）f f（b b1 1）,则极小点必在区间则极小点必在区间aa，b b1 1 内内;(1)(1)f f（a a1 1）f f（b b1 1）,则极小点必在区间则极小点必在区间 1 1，bb内内;(1)(1)f f（a a1 1）f f（b b1 1）,则极小点必在区间则极小点必在区间 1 1，bb内内;(3)(3)f f（a a1 1）=f f（b b1 1）,则极小点必在区间则极小点必在区间 1 1，b b1 1 内内可以总结为两种情况：若 ，则取a,b1为缩小后的搜索区间。若 ，则取a1,b为缩小后的搜索区间。试探法 黄金分割法插值法 二次插值法3 一维搜索方法分类 从前面的分析可知，每次缩短区间，只需要在区间内再插入一点并计算其函数值。而插入点的位置，可以由不同的方法来确定。就形成了不同的一维搜索方法。一维搜索方法分类3.4 黄金分割法（0.618法）1.黄金分割法2.黄金分割法的搜索过程 概述概述n在实际计算中，最常用的在实际计算中，最常用的一维搜索试探方法是黄金分割法一维搜索试探方法是黄金分割法，又称作又称作0.6180.618法法。我们可以通过学习黄金分割法来了解一。我们可以通过学习黄金分割法来了解一维搜索试探方法的基本思想。维搜索试探方法的基本思想。n在搜索区间在搜索区间 a,ba,b内适当插入两点内适当插入两点1 1、2 2，并计算其函，并计算其函数值。数值。1 1、2 2将区间分成三段。应用函数的单谷性质，将区间分成三段。应用函数的单谷性质，通过函数值大小的比较，删去其中一段，使搜索区间得以通过函数值大小的比较，删去其中一段，使搜索区间得以缩短。然后再在保留下来的区间上作同样的处置，如此迭缩短。然后再在保留下来的区间上作同样的处置，如此迭代下去，使搜索区间无限缩小，从而得到极小点的数值近代下去，使搜索区间无限缩小，从而得到极小点的数值近似解。似解。3.4 黄金分割法（0.618法）黄金分割法是建立在区间消去法原理基础上的试探方法。黄金分割法是建立在区间消去法原理基础上的试探方法。o适用于适用于a,ba,b区间上的任何单谷函数求极小值问题。对区间上的任何单谷函数求极小值问题。对函数除要求函数除要求“单谷单谷”外不作其它要求，甚至可以不连续。外不作其它要求，甚至可以不连续。因此，这种方法的适应面相当广。因此，这种方法的适应面相当广。n黄金分割法对插入点的要求：黄金分割法对插入点的要求：1 1）要求插入点）要求插入点1 1、2 2 的位置相对于区间的位置相对于区间a,ba,b两端两端点具有对称性点具有对称性，即，即 其中其中 为待定常数。为待定常数。1.黄金分割法黄金分割法2 2）黄金分割法还要求黄金分割法还要求在保留下来的区间内再插入一点所形在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分成的区间新三段，与原来区间的三段具有相同的比例分布布。即每次缩小所得的新区间长度与缩小前区间长度之即每次缩小所得的新区间长度与缩小前区间长度之比（即：区间收缩率）为定值。比（即：区间收缩率）为定值。o设原区间设原区间a,ba,b长度为长度为1 1如下图所示，保留下来的区间如下图所示，保留下来的区间 a,a,2 2 长度为长度为 ，区间缩短率为，区间缩短率为 。为了保持相。为了保持相同的比例分布，新插入点同的比例分布，新插入点 3 3应在应在 位置位置上，上，1 1 在原区间的在原区间的 位置应相当于在保留区位置应相当于在保留区间的间的 位置。故有位置。故有 取方程正数解，得取方程正数解，得1、2将区间分成三段将区间分成三段 黄金分割法要求在黄金分割法要求在黄金分割法要求在黄金分割法要求在保留下来的区间内再保留下来的区间内再保留下来的区间内再保留下来的区间内再插入一点所形成的区插入一点所形成的区插入一点所形成的区插入一点所形成的区间新三段，与原来区间新三段，与原来区间新三段，与原来区间新三段，与原来区间的三段具有相同的间的三段具有相同的间的三段具有相同的间的三段具有相同的比例分布比例分布比例分布比例分布 。两内分点值两内分点值:结论：结论：所谓黄金分割是指将一线段分成两段的方法，使整段长与较长段的长度所谓黄金分割是指将一线段分成两段的方法，使整段长与较长段的长度比值等于较长段与较短段长度的比值即比值等于较长段与较短段长度的比值即 。黄金分割法要求插入两点：黄金分割法区间消去示意图：3.4 黄金分割法（黄金分割法（0.6180.618法）法）2.2.黄金分割法的搜索过程黄金分割法的搜索过程（1）给出初始搜索区间 及收敛精度 ，将 赋以 。（2）按坐标点计算公式计算 并计算其对应的函数值 3.4 黄金分割法（黄金分割法（0.6180.618法）法）（3）根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。3.4 黄金分割法（黄金分割法（0.6180.618法）法）（4）检查区间是否缩短到足够小和函数值收敛到足够精度，如果收敛条件满足，则取最后两试验点的平均值作为极小点的数值近似解。如果条件不满足则转向步骤5。（5）产生新的插入点：如N0=0，则取（5）如果条件满足，则取最后两试验点的平均值作为极小点的数值近似解。3.4 黄金分割法（黄金分割法（0.6180.618法）法）缩短区间的总次数（迭代次数）:黄金分割法程序框图黄金分割法程序框图给定否否是是止也可采用迭代次数是否大于或等于 k 作终止准则。38迭代序号aby1比较y20-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-3：用黄金分割法求 的极小值 ，搜索区间是解：39解析解：例例 3-1 用黄金分割法求函数用黄金分割法求函数f(x)=3x3-4x+2的极小点，给的极小点，给定定 x0=0,h=1,=0.2。解：1）确定初始区间a1=x0=0,f1=f(a1)=2a2=x0+h=0+1=1,f2=f(a2)=1由于f1f2,应加大步长继续向前探测。a3=x0+2h=0+2=2,f3=f(a3)=18由于f2f3,可知初始区间已经找到，即a,b=a1,a3=0,22）用黄金分割法缩小区间 第一次缩小区间：a1=0+0.382(2-0)=0.764,f1=0.282 a2=0+0.618(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(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(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.222n概述概述n n一维搜索问题是在某一确定区间内寻求一元函数的极小点一维搜索问题是在某一确定区间内寻求一元函数的极小点一维搜索问题是在某一确定区间内寻求一元函数的极小点一维搜索问题是在某一确定区间内寻求一元函数的极小点的位置，在某些情况下，如果没有函数表达式，但能够给的位置，在某些情况下，如果没有函数表达式，但能够给的位置，在某些情况下，如果没有函数表达式，但能够给的位置，在某些情况下，如果没有函数表达式，但能够给出若干试验点处的函数值，就可以根据这些点处的函数值，出若干试验点处的函数值，就可以根据这些点处的函数值，出若干试验点处的函数值，就可以根据这些点处的函数值，出若干试验点处的函数值，就可以根据这些点处的函数值，利用利用利用利用插值法插值法插值法插值法建立函数的某种近似表达式，进而求出函数的建立函数的某种近似表达式，进而求出函数的建立函数的某种近似表达式，进而求出函数的建立函数的某种近似表达式，进而求出函数的极小点，并用它作为原来函数极小点的近似值。这种方法极小点，并用它作为原来函数极小点的近似值。这种方法极小点，并用它作为原来函数极小点的近似值。这种方法极小点，并用它作为原来函数极小点的近似值。这种方法称作称作称作称作插值法插值法插值法插值法，又称作，又称作，又称作，又称作函数逼近法函数逼近法函数逼近法函数逼近法。3.5 一维搜索的二次插值法一维搜索的二次插值法试探法试探法（如黄金分割法）与（如黄金分割法）与插值法插值法的比较：的比较：不同点不同点：表现在试验点（插入点）位置的确定方法不同。：表现在试验点（插入点）位置的确定方法不同。n多项式是函数逼近的一种常用工具。多项式是函数逼近的一种常用工具。o在搜索区间内可以利用若干试验点处的函数值在搜索区间内可以利用若干试验点处的函数值来构造低次多项式，用它作为函数的近似表达来构造低次多项式，用它作为函数的近似表达式，并用这个多项式的极小点作为原函数极小式，并用这个多项式的极小点作为原函数极小点的近似。点的近似。n常用的插值多项式为常用的插值多项式为二次多项式。二次多项式。1.1.牛顿法（切线法）牛顿法（切线法）利用一点的函数值、一利用一点的函数值、一阶导数值和二阶导数值来构造二次函数。阶导数值和二阶导数值来构造二次函数。2.2.二次插值法（抛物线法）二次插值法（抛物线法）利用三个点的函数利用三个点的函数值形成一个抛物线来构造二次函数。值形成一个抛物线来构造二次函数。1、牛顿法（切线法）、牛顿法（切线法）对于一维搜索函数对于一维搜索函数 ，假定已经给出极小点的一个较，假定已经给出极小点的一个较好的近似点好的近似点 ，在，在 点附近用一个二次函数点附近用一个二次函数 来逼近函数来逼近函数 。然后以该二次函数然后以该二次函数 的极小点作为的极小点作为 极小点的一个新的极小点的一个新的近似点近似点 。根据极值必要条件：。根据极值必要条件：牛顿法的几何解释：牛顿法的几何解释：在上图中，在在上图中，在 处用一抛物线处用一抛物线 代替曲线代替曲线 ，相，相当于用一斜线当于用一斜线 代替代替 。这样各个近似点是通过。这样各个近似点是通过对对 作切线求得与作切线求得与 轴的交点找到，故牛顿法又称为轴的交点找到，故牛顿法又称为切线法。切线法。牛顿法的计算步骤：牛顿法的计算步骤：1 1）给定初始点）给定初始点 ，控制误差，控制误差 ，并令，并令 2 2）计算）计算 3 3）求）求 4 4）若）若 ，则求得近似解，则求得近似解 ，停止计算，否则作停止计算，否则作5 5）。）。5 5）令）令 转转2 2）。）。例题：例题：给定给定 ，试用，试用牛顿法求其极小点牛顿法求其极小点 。解：解：1 1）给定初始点）给定初始点 ，控制误差，控制误差 2 2）3 3）4 4）重复上边的过程，进行迭代，直到重复上边的过程，进行迭代，直到 为止。可得到计算结果如下表为止。可得到计算结果如下表:表3-2 牛顿法的搜索过程k01234值ak35.166674.334744.03964.00066f(ak)-52153.3518332.301993.382990.00551f(ak)-24184.33332109.4458686.8699284.04720ak+15.166674.334744.039604.000664.00059优点：收敛速度快。优点：收敛速度快。缺点：每一点都要进行二阶导数，工作量大；缺点：每一点都要进行二阶导数，工作量大；当用数值微分代替二阶导数，由于舍入误当用数值微分代替二阶导数，由于舍入误差会影响迭代速度；差会影响迭代速度；要求初始点离极小点不太远，否则有可能要求初始点离极小点不太远，否则有可能使极小化发散或收敛到非极小点。使极小化发散或收敛到非极小点。牛顿法的特点：牛顿法的特点：、二次插值法（抛物线法）、二次插值法（抛物线法）基本思想：基本思想：基本思想：基本思想：二次插值的基本思想是利用目标函二次插值的基本思想是利用目标函二次插值的基本思想是利用目标函二次插值的基本思想是利用目标函数在不同数在不同数在不同数在不同3 3 3 3点的函数值构成一个与原函数点的函数值构成一个与原函数点的函数值构成一个与原函数点的函数值构成一个与原函数f f f f(x x x x)相近似的二次多项式相近似的二次多项式相近似的二次多项式相近似的二次多项式p p p p(x x x x)，以函数，以函数，以函数，以函数p p p p(x x x x)的极的极的极的极值点值点值点值点x x x xp p(即即即即p p p p(x*x*x*x*p p p p)=0)=0)=0)=0的根的根的根的根)作为目标函数作为目标函数作为目标函数作为目标函数f f f f(x x x x)的近似极值点。的近似极值点。的近似极值点。的近似极值点。（1）二次插值多项式的构成及其极值点）二次插值多项式的构成及其极值点设 在单谷区间中的三点 的相应函数值，则可以做出如下的二次插值多项式：多项式多项式 的极值点可从极值的必要条件求得的极值点可从极值的必要条件求得，即，即 ，n为了确定这个极值点，只需计算出系数为了确定这个极值点，只需计算出系数a a1 1和和a a2 2 。其方。其方法法是利用法法是利用a a0 0、a a1 1、a a2 2的联立方程组中相邻两个方程消的联立方程组中相邻两个方程消去去a a0 0 ，从而得到关于，从而得到关于a a1 1、a a2 2的方程组的方程组n解得解得n所以所以如果令如果令则则这样就得到了这样就得到了f()极小点极小点*的近似解的近似解p。）如果区间长度 足够小，则由 便得出我们所要求的近似极小点 2 2）如果不满足，必须缩小区间）如果不满足，必须缩小区间 ，根据区间消取法，根据区间消取法原理不断缩小区间。原理不断缩小区间。根据区间消去法原理，需要已知区根据区间消去法原理，需要已知区间内两点的函数值。其中点间内两点的函数值。其中点2 2的的函数值函数值y y2 2=f=f（2 2）已知，另外一点已知，另外一点可取可取p p点并计算其函数值点并计算其函数值y yp p=f=f（p p）。）。当当 y y2 2yyp p 时取时取 1 1，p p 为缩短后的搜索区间（如右图）为缩短后的搜索区间（如右图）。当当y y2 2yyp p 时取时取 2 2，3 3 为缩短后为缩短后的搜索区间。的搜索区间。二二次次插插值值法法程程序序框框图图例1：用二次插值法求 上的极小点。12144.524.54.705120355y1-0.756802-0.977590y2-0.977590-0.999974y3-0.958924-0.958924p4.7051204.710594yp-0.999974-0.999998二二次次插插值值法法计计算算过过程程示示例例例例 2 2 用二次插值法求函数用二次插值法求函数f f(x x)=3)=3x x3 3-4-4x x+2+2的极小点，的极小点，给定给定 x x0 0=0,=0,=0.2=0.2。2 2）用二次插值法逼近极小点）用二次插值法逼近极小点相邻三点的函数值相邻三点的函数值:x x1 1=0,=0,x x2 2=1,=1,x x3 3=2;=2;f f1 1=2,=2,f f2 2=1,=1,f f3 3=18.=18.代入公式：代入公式：x xp p*0.555,f0.555,fp p=0.292=0.292解解 :1 1）确定初始区间）确定初始区间初始区间初始区间 a a,b b=0,2,=0,2,中间点中间点x x2 2=1,=1,f f(x x2 2)=1)=1。由于由于f fp p f f2 2,x xp p*0.2,|=1-0.555=0.4450.2,应继续迭代。迭代。在新区在新区间，相，相邻三点的函数三点的函数值:x x1 1=0,=0,x x2 2=0.555,=0.555,x x3 3=1;=1;f f1 1=2,=2,f f2 2=0.292,=0.292,f f3 3=1,=1,代入代入x xp p*公式公式计算得：算得：x xp p*0.607,f0.607,fp p=0.243=0.243 由于由于f fp p x x2 2,新区新区间 a a,b b=x x2 2,b b=0.555,1=0.555,1|x x2 2-x xp p*|=|0.555-0.607|=0.0520.2,|=|0.555-0.607|=0.0520.2,迭代迭代终止。止。x xp p*0.607,f*=0.2430.607,f*=0.243例例 3 用二次插值法求用二次插值法求 的极值点。的极值点。初始搜索区间初始搜索区间 ，。解：取解：取x x2 2点为区间点为区间 x x1 1,x x3 3 的中点的中点 ，计算计算x x1 1,x x2 2,x x3 3 3 3点处的函数值点处的函数值f f1 1=19=19，f f2 2=-96.9375=-96.9375，f f3 3=124=124。可见函数。可见函数值满足值满足“高低高高低高”形态。形态。以以x x1 1,x x2 2,x x3 3为插值点构造二次曲线。为插值点构造二次曲线。求第一次近似的二次曲线求第一次近似的二次曲线p p(x x)的极小值点，由公式得：的极小值点，由公式得：比较函数值可知比较函数值可知 这种情况应消除左边区段这种情况应消除左边区段 。然后用。然后用 作为作为x x1 1,x x2 2,x x3 3新新3 3点点,重新构造二次曲线重新构造二次曲线p p(x x)，如此反复计，如此反复计算，直到算，直到 为止。为止。整个迭代过程的计算结果列于表。整个迭代过程的计算结果列于表。插值法和试探法的比较插值法和试探法的比较n试探法试探法中试验点位置是由某种给定的规律确定的，它不考中试验点位置是由某种给定的规律确定的，它不考虑函数值的分布。例如，黄金分割法是按等比例虑函数值的分布。例如，黄金分割法是按等比例0.6180.618缩缩短率确定的。短率确定的。插值法插值法中，试验点位置是按函数值近似分布中，试验点位置是按函数值近似分布的极小点确定的。的极小点确定的。试探法试探法仅仅利用了试验点函数值大小的仅仅利用了试验点函数值大小的比较，而比较，而插值法插值法还要利用函数值本身或者其导数信息。还要利用函数值本身或者其导数信息。n试探法试探法仅对试验点函数值的大小进行比较，而函数值本身仅对试验点函数值的大小进行比较，而函数值本身的特性没有得到充分利用，这样即使对一些简单的函数，的特性没有得到充分利用，这样即使对一些简单的函数，例如二次函数，也不得不象一般函数那样进行同样多的函例如二次函数，也不得不象一般函数那样进行同样多的函数值计算。数值计算。插值法插值法是利用函数在已知试验点的值（或导数是利用函数在已知试验点的值（或导数值）来确定新试验点的位置。当函数具有比较好的解析性值）来确定新试验点的位置。当函数具有比较好的解析性质时（例如连续可微性），质时（例如连续可微性），插值法插值法比比试探法试探法效果更好。效果更好。复习复习l 初始区间的确定方法初始区间的确定方法l 黄金分割算法黄金分割算法l 二次差值的计算二次差值的计算