一维搜索插值法

搜索方向步长因子第三章一维搜索方法第一节概述步长求多维目标函数的极值时，假设迭代过程的出发点及搜索方向已确定，那么从出发，沿方向搜索新点的迭代格式为

式中，为步长因子。选择一特定步长，使产生的新点是方向上目标函数的极小点，即

那么称为方向上的最优步长因子。二维函数f(x)沿方向s的一维搜索例如最优步长因子

在搜索方向上，使目标函数取得极小值的步长因子，称为该方向上最优步长因子。

一维搜索

沿给定搜索方向，求最优步长因子的一元函数极值问题，称为一维搜索。一维问题是多维问题的根底解析解法先将f(x+ad)进行泰勒展开，并取到二阶项，后对泰勒展开式利用微积分求极值方法获得最正确步长因子。求最正确步长因子方法数值解法利用计算机通过反复迭代计算求得最正确步长因子的近似值。根本思路是：先确定步长因子〔最优点〕所在的区间，然后根据区间消去法远离不断缩小此区间，从而获得最优点的数值的近似解。0.618法,抛物线法,三次插值法.....例：则当确实定方法1、运用进退法确定单变量函数极小点所在的搜索区间，该区间应是单谷区间。单谷区间是指函数在区间内只有一个极小点。在极小点左边的函数值应是严格下降，在极小点右边的函数值应是严格上升，即单谷区间内的函数值具有的特征是：“高—低—高”。

2、运用区间消去法，求极小点。第二节搜索区间确实定与区间消去法原理数值解法求解一般步骤正向搜索外推法一、确定初始搜索区间的外推法〔进退法〕中间各个试探点函数值依次减少，h>0

反向搜索外推法第一试探点函数值上升，反向以后中间各个试探点函数值依次减少，h<01.取初始点为第一点,前进一步,得第二点,并计算函数值.2.比较函数值,,向前试探3.比较函数值,,步长加倍,向前试探4.比较函数值,,步长加倍,再向前试探。5.比较函数值,所以a=2,b=8,即搜索区间为[a,b]=[2,8].

-外推法程序框图二、区间消去法原理由外推法确定搜索区间[a,b]后，在区间内插入两点a1和b1〔a<a1<b1<b〕，计算插入点的函数值，并比较其大小，确定消去的区间，从而得到缩短的搜索区间，依次类推，最后即可得到理论最小点的近似解。一维搜索方法分类应用区间消去原理，需要在确定的搜索内给出插入点。根据确定插入点的方法不同，一维搜索方法分为两大类：试探法：黄金分割法、斐波那契法插值法〔函数逼近法〕：二次插值法、三次插值法、格点法等。黄金分割法的根本方法是通过不断缩小搜索区间的长度来搜索函数的极小点。在已确定的函数搜索区间内，其函数值呈现”高—低—高”的特征。通过比较搜索区间内两试点的函数值，逐步缩短搜索区间，得到一个不断缩小的区间序列，直到极小点所在区间缩小到给定的精度，取其中点作为近似极小点输出。 这种方法步骤简单，效果较好，但是计算效率偏低，是计算中常用的方法之一。

第三节黄金分割法算法的关键插入点对称分布在搜索区间内插入的两个试点在区间的位置相对于区间边界对称分布。

固定的区间收缩率区间收缩率是表示每次缩小所得到的新区间长度与缩小前旧区间长度之比.整理后得到一元二次方程其解故黄金分割法又称为0.618法。插入的两个试点为:黄金分割法的搜索过程给出搜索区间[a,b]及收敛精度e，并置=0.618。按照公式(1)(2)计算插入点，并计算其函数值。根据区间消去法原理，进行区间缩短。检验区间是否缩短到足够短，如果不满足转步骤2。否那么转下步。取区间两端点的平均值作为极小点的数值近似解。终止判别条件采用点距准那么〔区间足够小〕：1〕.在搜索区间内取两试点，并且计算它们函数值。

2〕比较两试点函数值，缩短搜索区间.由于消去右区间初始搜索区间[2,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、二次多项式逼近原函数的方法一、牛顿法〔切线法〕根本思想取原函数极小点的一个近似点，在近似点附近用二次函数〔泰勒展开并保存到二次项〕逼近原函数，以逼近函数的极小点作为原极小点的新近似点，依此类推,直到近似点满足控制误差为止，取最后的近似点作为原函数的极小点。迭代公式几何解释特点收敛速度快计算工作量大对初始点的选择要求高二次插值法是利用目标函数在假设干点的函数值或导数信息构造二次多项式函数来逼近原一维搜索函数，并且用插值多项式的极值点近似作为目标函数的极小点。由于二次多项式函数的图形是抛物线，所以二次插值法又称为抛物线插值法。二次插值法1.根本思想在给定目标函数的初始区间内取三点，设它们的函数值分别为,满足条件和。利用原函数曲线上的、和三点构造一条抛物线式中，是待定系数。

原函数曲线——实线

插值函数曲线——虚线2.插入点的计算求插值多项式的极值点。待定系数由下面线性方程组得到求解线性方程组得到插值极小点

式中

3.二次插值算法形成把和作为在区间插入的两个试点，根据区间消去法原理，缩短区间。重复上述过程，直到满足终止条件，取较小的插入点作为原目标函数极小点的近似解。3.二次插值算法形成把和作为在区间插入的两个试点，根据区间消去法原理，缩短区间。重复上述过程，直到满足终止条件，取较小的插入点作为原目标函数极小点的近似解。4终止判别条件采用点距准那么〔前后两个插值点的距离不超过误差限〕：1.计算初始点及其函数值2.计算插值点3.判断收敛条件初始搜索区间[2,8]，迭代精度ε=0.01,收敛条件:|ap-a2|<ε。5.重新计算插值点6.判断收敛条件，得最优解4.缩短搜索区间二次插值法程序框图补充说明——区间端点换名方法：〔1〕

二次插值法只要求f(x)连续，不要求其一阶可微。〔2〕

收敛速度比黄金分割法快，但可靠性不如黄金分割法好，程序也较长。〔3〕如p(x)