一维搜索插值法.ppt

搜索方向搜索方向步长因子步长因子第三章第三章一维搜索方法一维搜索方法第一节第一节概概述述 求求多多维维目目标标函函数数 的的极极值值时时，若若迭迭代代过过程程的的出出发发点点 及及搜搜索索方方向向 已已确确定定，则则从从 出出发发，沿沿方方向向 搜索新点的迭代格式为搜索新点的迭代格式为 式中，式中，为步长因子。为步长因子。选选择择一一特特定定步步长长 ，使使产产生生的的新新点点 是是方方向向 上目标函数的极小点，即上目标函数的极小点，即 则称则称 为方向为方向 上的最优步长因子。上的最优步长因子。二维函数二维函数f(x)沿方向沿方向s的一维搜索示例的一维搜索示例 最优步长因子最优步长因子 在搜索方向上，使目标函数取得极小值的在搜索方向上，使目标函数取得极小值的步长因子，称为该方向上最优步长因子。步长因子，称为该方向上最优步长因子。一维搜索一维搜索沿给定搜索方向，求最优步长因子的一沿给定搜索方向，求最优步长因子的一元函数极值问题，称为一维搜索。元函数极值问题，称为一维搜索。一维问题是多维问题的基础一维问题是多维问题的基础解析解法解析解法先将先将f(x+adf(x+ad)进行泰勒展开，并取到二进行泰勒展开，并取到二阶项，后对泰勒展开式利用微积分求极值方阶项，后对泰勒展开式利用微积分求极值方法获得最佳步长因子。法获得最佳步长因子。求最佳步长因子方法求最佳步长因子方法数值解法数值解法利用计算机通过反复迭代计算求得最佳利用计算机通过反复迭代计算求得最佳步长因子的近似值。步长因子的近似值。基本思路是：基本思路是：先确定步长因子（最优点）所在的区间，先确定步长因子（最优点）所在的区间，然后根据区间消去法远离不断缩小此区间，然后根据区间消去法远离不断缩小此区间，从而获得最优点的数值的近似解从而获得最优点的数值的近似解。0.618法法,抛物线法抛物线法,三次插值法三次插值法.例：例：则则当当的确定方法的确定方法 1 1、运运用用进进退退法法确确定定单单变变量量函函数数 极极小小点点 所所在在的搜的搜 索区间索区间 ，该区间应是单谷区间。，该区间应是单谷区间。vv单谷区间单谷区间单谷区间单谷区间是指函数在区间内只有一个极小点。在是指函数在区间内只有一个极小点。在极小点左边的函数值应是严格下降，在极小点右极小点左边的函数值应是严格下降，在极小点右边的函数值应是严格上升，即单谷区间内的函数边的函数值应是严格上升，即单谷区间内的函数值具有的特征是：值具有的特征是：“高高低低高高”。2、运用区间消去法，求极小点、运用区间消去法，求极小点。第二节 搜索区间的确定与区间消去法原理数值解法求解一般步骤数值解法求解一般步骤l正向搜索外推法正向搜索外推法一、确定初始搜索区间的外推法（进退法）一、确定初始搜索区间的外推法（进退法）l反向搜索外推法反向搜索外推法1.取初始点取初始点为为第一点第一点,前前进进一步一步,得第二点得第二点,并并计计算函数算函数值值.2.比比较较函数函数值值,向前向前试试探探3.比比较较函数函数值值,步步长长加倍加倍,向前向前试试探探4.比比较较函数函数值值,步步长长加倍加倍,再向前再向前试试探。探。5.比比较较函数函数值值,所以所以a=2,b=8,即搜索区即搜索区间为间为a,b=2,8.-外外推推法法程程序序框框图图二、区间消去法原理二、区间消去法原理由外推法确定搜索区间由外推法确定搜索区间a,b后，在区间后，在区间内插入两点内插入两点a1和和b1（aa1b1b），计算），计算插入点的函数值，并比较其大小，确定消去插入点的函数值，并比较其大小，确定消去的区间，从而得到缩短的搜索区间，依次类的区间，从而得到缩短的搜索区间，依次类推，最后即可得到理论最小点的近似解。推，最后即可得到理论最小点的近似解。一维搜索方法分类应用区间消去原理，需要在确定的搜索应用区间消去原理，需要在确定的搜索内给出插入点。根据确定插入点的方法不同，内给出插入点。根据确定插入点的方法不同，一维搜索方法分为两大类：一维搜索方法分为两大类：v试探法：黄金分割法、斐波那契法试探法：黄金分割法、斐波那契法v插值法（函数逼近法）：二次插值法、三次插值法（函数逼近法）：二次插值法、三次插值法、格点法等。插值法、格点法等。黄金分割法的基本方法是通过不断缩小搜索黄金分割法的基本方法是通过不断缩小搜索区间的长度来搜索函数的极小点。区间的长度来搜索函数的极小点。在已确定在已确定的函数搜索区间内，其函数值呈现的函数搜索区间内，其函数值呈现”高高低低高高”的特征。通过比较搜索区间内两试点的特征。通过比较搜索区间内两试点的函数值，逐步缩短搜索区间，得到一个不的函数值，逐步缩短搜索区间，得到一个不断缩小的区间序列，直到极小点所在区间缩断缩小的区间序列，直到极小点所在区间缩小到给定的精度，取其中点作为近似极小点小到给定的精度，取其中点作为近似极小点输出。输出。这种方法步骤简单，效果较好，但是计算这种方法步骤简单，效果较好，但是计算效率偏低，是计算中常用的方法之一。效率偏低，是计算中常用的方法之一。第三节第三节 黄金分割法黄金分割法算法的关键算法的关键插入点对称分布插入点对称分布在搜索区间内插入的两个在搜索区间内插入的两个试点在区间的位置相对于区间边界对称分布。试点在区间的位置相对于区间边界对称分布。固定的区间收缩率固定的区间收缩率区间收缩率是表示每次缩小所区间收缩率是表示每次缩小所得到的新区间长度与缩小前旧区间长度之比得到的新区间长度与缩小前旧区间长度之比.整理后得到一元二次方程整理后得到一元二次方程其解其解 故黄金分割法又称为故黄金分割法又称为0.6180.618法。法。插入的两个试点为插入的两个试点为:黄金分割法的搜索过程黄金分割法的搜索过程1.给出搜索区间给出搜索区间a,b及收敛精度及收敛精度e，并置，并置=0.618。2.按照公式按照公式(1)(2)计算插入点，并计算其函数值。计算插入点，并计算其函数值。3.根据区间消去法原理，进行区间缩短。根据区间消去法原理，进行区间缩短。4.检验区间是否缩短到足够短，如果不满足转步骤检验区间是否缩短到足够短，如果不满足转步骤2。否则。否则转下步。转下步。5.取区间两端点的平均值作为极小点的数值近似解。取区间两端点的平均值作为极小点的数值近似解。终止判别条件终止判别条件 采用采用点距准则点距准则（区间足够小）：（区间足够小）：1）.在搜索区在搜索区间间内取两内取两试试点，并且点，并且计计算它算它们们函数函数值值。2）比）比较较两两试试点函数点函数值值，缩缩短搜索区短搜索区间间.由于由于 消去右区消去右区间间 初始搜索区初始搜索区间间2,82,8，迭代精度，迭代精度=0.01,收收敛敛条件条件:|b-a|。3）确定新区）确定新区间间 4）判断迭代）判断迭代终终止条件：止条件：不不满满足迭代足迭代终终止条件，止条件，继续继续搜索。搜索。708.52=ab292.412=aa6227.112-=ff4165.3)2708.5(618.0708.5)(618.01=-=-=abba2430.2104165.374165.3)(211-=+-=aff5）重新计算插入试点。）重新计算插入试点。a,b=2,5.708黄黄金金分分割割法法的的程程序序框框图图2、函数逼近法、函数逼近法将搜索区间内的若干试验点的函数值构造的将搜索区间内的若干试验点的函数值构造的低次多项式（二次多项式）作为函数的近似低次多项式（二次多项式）作为函数的近似表达式，用这个多项式的极值作为原函数的表达式，用这个多项式的极值作为原函数的极值点的近似点。极值点的近似点。第四节第四节一维搜索的插值法一维搜索的插值法1、插值方法与试探方法的比较、插值方法与试探方法的比较牛顿法和抛物线法牛顿法和抛物线法3、二次多项式逼近原函数的方法、二次多项式逼近原函数的方法一、牛顿法（切线法）一、牛顿法（切线法）基本思想基本思想取原函数极小点的一个近似点，在近似点附近用二次函数取原函数极小点的一个近似点，在近似点附近用二次函数（泰勒展开并保留到二次项泰勒展开并保留到二次项）逼近原函数，以逼近函数的极）逼近原函数，以逼近函数的极小点作为原极小点的新近似点，依此类推小点作为原极小点的新近似点，依此类推,直到近似点满足控直到近似点满足控制误差为止，取最后的近似点作为原函数的极小点。制误差为止，取最后的近似点作为原函数的极小点。迭代公式迭代公式几何解释几何解释v特特点点v收敛速度快收敛速度快v计算工作量大计算工作量大v对初始点的选择对初始点的选择要求高要求高v二次插值法是利用目标函数在若干二次插值法是利用目标函数在若干点的函数值或导数信息构造二次多点的函数值或导数信息构造二次多项式函数来逼近原一维搜索函数，项式函数来逼近原一维搜索函数，并且用并且用插值多项式插值多项式的极值点近似作的极值点近似作为目标函数的极小点。为目标函数的极小点。v由于二次多项式函数的图形是抛物由于二次多项式函数的图形是抛物线，所以二次插值法又称为抛物线线，所以二次插值法又称为抛物线插值法。插值法。二二二次插值法二次插值法1.基本思想基本思想v在在 给给 定定 目目 标标 函函 数数 的的 初初 始始 区区 间间 内内 取取 三三 点点 ，设设它它们们的的函函数数值值分分别别为为 ,满满足足条条件件 和和 。利利用用原原函函数数曲曲线线上上的的 、和和 三点构造一条抛物线三点构造一条抛物线v式中，式中，是待定系数。是待定系数。原函数原函数曲线曲线实线实线插值函数插值函数曲线曲线虚线虚线2.插入点的计算插入点的计算v求插值多项式求插值多项式 的极值点。的极值点。v待定系数由下面待定系数由下面线性方程组线性方程组得到得到v求解线性方程组得到插值极小点求解线性方程组得到插值极小点v式中式中 3.二次插值算法形成二次插值算法形成把把和和作为在区间作为在区间插入的两个试点，根据区间消去插入的两个试点，根据区间消去法原理，缩短区间。重复上述过程，直到满足终止条件，取较法原理，缩短区间。重复上述过程，直到满足终止条件，取较小的插入点作为原目标函数极小点的近似解。小的插入点作为原目标函数极小点的近似解。3.二次插值算法形成二次插值算法形成把把和和作为在区间作为在区间插入的两个试点，根据区间消去插入的两个试点，根据区间消去法原理，缩短区间。重复上述过程，直到满足终止条件，取较法原理，缩短区间。重复上述过程，直到满足终止条件，取较小的插入点作为原目标函数极小点的近似解。小的插入点作为原目标函数极小点的近似解。4终止判别条件终止判别条件 采用采用点距准则点距准则（前后两个插值点的距离不（前后两个插值点的距离不超过误差限）：超过误差限）：1.计计算初始点及其函数算初始点及其函数值值2.计计算插算插值值点点3.判断收判断收敛敛条件条件初始搜索区初始搜索区间间2,82,8，迭代精度，迭代精度0.01,收收敛敛条件条件:|ap-a2|。5.重新重新计计算插算插值值点点6.判断收判断收敛敛条件，得最条件，得最优优解解4.缩缩短搜索区短搜索区间间二二次次插插值值法法程程序序框框图图补充说明补充说明区间端点换名方法：区间端点换名方法：（1）二次插值法只要求二次插值法只要求f(x)连续，不要求其一阶可微。连续，不要求其一阶可微。（2）收敛速度比黄金分割法快，但可靠性不如黄金分割法收敛速度比黄金分割法快，但可靠性不如黄金分割法好，程序也较长。好，程序也较长。（3）如如p(x)的相邻两个迭代点重合，则产生死循环。的相邻两个迭代点重合，则产生死循环。举例举例用二次插值法求下列函数最优解。初始区间为用二次插值法求下列函数最优解。初始区间为1,7，精，精度为度为0.01。特特点点作作 业业2.2.用黄金分割法求函数用黄金分割法求函数 的极小的极小 点初始搜索区间点初始搜索区间 ，迭代精度，迭代精度3.用二次插值法求下列函数在区间用二次插值法求下列函数在区间0,2上的极小点，上的极小点，精度精度0.01。要求：要求：完成两次迭代过程完成两次迭代过程,写出详细的计算步骤。写出详细的计算步骤。