机械优化设计三次PPT课件.pptx

何军良 2020 3 21 1 2 目录 CONTENTS 2020 3 21 第三章一维搜索方法 概述 01 搜索区间确定与区间消去法原理 一维搜索的试探方法 一维搜索的插值方法 02 03 04 2020 3 21 3 4 3 4一维搜索的插值方法 第三章一维搜索方法 假定我们的问题是在某一确定区间内寻求函数的极小点位置 虽然没有函数表达式 但能够给出若干试验点处的函数值 我们可以根据这些点处的函数值 利用插值方法建立函数的某种近似表达式 进而求出函数的极小点 并用它作为原来函数极小点的近似值 这种方法称作插值方法 又称作函数迫近法 2020 3 21 5 3 4 1牛顿法 第三章一维搜索方法 设f 为一个连续可微函数 则在 0附近 函数应该与一个二次函数接近 即可在点 0附近用一个二次函数 逼近函数f 即 二次函数的 极小点 1作为f 极小点的一个近似点 根据极值必要条件 3 4一维搜索的插值方法 2020 3 21 6 第三章一维搜索方法 图中 在 0处用一抛物线 代替曲线f 相当于用一斜直线 代替曲线f 这样各个近似点是通过对作f 切线求得与轴的交点找到的 所以 有时牛顿法又称作切线法 3 4 1牛顿法 3 4一维搜索的插值方法 相当于在曲线f 上按照一定的规则找到某个点 并不断的作切线 直到切线的斜率接近于0 规则就是 2020 3 21 7 第三章一维搜索方法 在牛顿法的计算步骤是 给定初始点 0 控制误差 并令k 0 计算f k 和f k 计算 k 1 k f k f k 若 k 1 k 则求得近似解 k 1 停止计算 否则进入步骤4 令k k 1 转步骤1 3 4 1牛顿法 3 4一维搜索的插值方法 问 控制误差 还可以怎样设定 f k 1 0 几何解释 在 k 1在处的一阶导数的斜率接近0 2020 3 21 8 第三章一维搜索方法 例 给定f 4 4 3 6 2 16 4 试用牛顿法求其极小点 解 为计算方便 先求出函数的一阶导数和二阶导数 f 4 3 3 2 3 4 f 12 2 2 1 给定初始点 0 3 控制误差 0 001 3 4 1牛顿法 3 4一维搜索的插值方法 2020 3 21 9 第三章一维搜索方法 3 4 1牛顿法 3 4一维搜索的插值方法 Step1 Step2 Step3 Step4 将 1代入到步骤1 重复步骤2 3 直到 2020 3 21 10 第三章一维搜索方法 3 4 1牛顿法 3 4一维搜索的插值方法 得到计算结果如下表 2020 3 21 11 第三章一维搜索方法 优点 收敛速度快 缺点 每一点都要进行二阶导数 工作量大 当用数值微分代替二阶导数 由于舍入误差会影响迭代速度 要求初始点离极小点不太远 否则有可能使极小化发散或收敛到非极小点 3 4 1牛顿法 3 4一维搜索的插值方法 可能跳过了极小点 开始发散 2020 3 21 12 3 4一维搜索的的插值方法 3 4 2抛物线法 二次插值法 第三章一维搜索方法 二次插值的基本思想是利用目标函数在不同3点的函数值构成一个与原函数f x 相近似的二次多项式p x 以函数p x 的极值点x p 即p x p 0的根 作为目标函数f x 的近似极值点 1 基本思想 2020 3 21 13 第三章一维搜索方法 2 二次函数的构成 利用在单谷区间中的三点 1f 2 f 3 作如下二次插值多项式 3 4一维搜索的的插值方法 3 4 2抛物线法 二次插值法 2020 3 21 14 第三章一维搜索方法 2 二次函数的构成 求系数a1和a2 3 4一维搜索的的插值方法 3 4 2抛物线法 二次插值法 多项式 的极值点可从极值的必要条件求得 即 2020 3 21 15 第三章一维搜索方法 式中 求出a1和a2后得 为便于计算 可将上式改写为 2 二次函数的构成 3 4一维搜索的的插值方法 3 4 2抛物线法 二次插值法 可得f 极小点 的近似解 p 2020 3 21 16 第三章一维搜索方法 3 区间缩小 3 4一维搜索的的插值方法 3 4 2抛物线法 二次插值法 假如本身为二次函数 则在理论上按前式一次求值就可找到最优点 若为高于二次的函数或者其他函数 可采用区间消去法逐步缩小区间 2020 3 21 17 第三章一维搜索方法 3 区间缩小 3 4一维搜索的的插值方法 3 4 2抛物线法 二次插值法 根据区间消去法原理 需要已知区间内两点的函数值 其中点 2的函数值y2 f 2 已知 另外一点可取 p点并计算其函数值yp f p 当y2 yp时取 1 p 为缩短后的搜索区间 当y2 yp时取 2 3 为缩短后的搜索区间 2020 3 21 18 第三章一维搜索方法 根据 p和 2 f p 和f 2 的相互关系 以及h的正反向 分8种情况进行区间缩小 在已有 1 2 3 p的四点中选择新的三个点 1 2 3 再进行二次插值 选点要求 y1 y2 y3 高 低 高形态 3 区间缩小 3 4一维搜索的的插值方法 3 4 2抛物线法 二次插值法 2020 3 21 19 第三章一维搜索方法 3 区间缩小 3 4一维搜索的的插值方法 3 4 2抛物线法 二次插值法 y3 2020 3 21 20 第三章一维搜索方法 3 区间缩小 3 4一维搜索的的插值方法 3 4 2抛物线法 二次插值法 2020 3 21 21 4 算法框图 2020 3 21 22 第三章一维搜索方法 按上述步骤设计的二次插值法的程序框图 有以下3点需作说明 判断C2 0 若成立 则有说明3个插值点P1 P2和P3在一条直线上 判断 p 1 3 p 0 若不成立 说明 p落在 1 3 外 以上两种情况只是区间已经缩得很小 3个插值点已经十分接近 由于计算机的舍入误差可能发生 此时 取 2和f2作为最优解是合理的 4 算法框图 3 4一维搜索的的插值方法 3 4 2抛物线法 二次插值法 2020 3 21 23 第三章一维搜索方法 例 用二次插值法求f sin 在区间是4 5的极小值 解 3 4一维搜索的的插值方法 3 4 2抛物线法 二次插值法 2020 3 21 24 第三章一维搜索方法 例 用二次插值法求函数f x 3x3 4x 2的极小值点 给定x0 0 0 2 解 1 确定初始区间 2 用二次插值法逼近极小点 相邻三点x1 0 x2 1 x3 2函数值f1 2 f2 1 f3 18 代入公式 12 22 32 1 32 12 2 12 22 3 2 3 1 3 1 2 1 2 3 x p 0 555 fp 0 292 可得 3 4一维搜索的的插值方法 3 4 2抛物线法 二次插值法 确定初始区间 a b 0 2 中间点x2 1 外推法确定 h 1 x1 0 x2 1 x3 2 f1 2 f2 1 f3 18 f1 f2 f3 2020 3 21 25 第三章一维搜索方法 x p 0 607 fp 0 243 由于fp0 2 继续迭代 在新区间 相邻三点的函数值 x1 0 x2 0 555 x3 1 f1 2 f2 0 292 f3 1 由于fpx2 新区间 a b x2 b 0 555 1 f2 fx p f2 0 292 0 243 0 292 0 167 0 2 迭代终止 3 4一维搜索的的插值方法 3 4 2抛物线法 二次插值法 2020 3 21 26 第三章一维搜索方法 例 用二次函数插值法f x x4 4x3 6x2 16x 4的极值点 初始搜索区间 x1 x3 1 6 0 002 解 取x2点为区间 x1 x3 的中点 计算x1 x2 x3处的函数值 函数f1 19 f2 96 9375 f3 124 可见函数值满足 高 低 高 形态 以x1 x2 x3为插值点构造二次曲线 求第一次近似的二次曲线p x 的极小值点 由公式得 x p 1 9545 比较函数值可知 3 4一维搜索的的插值方法 3 4 2抛物线法 二次插值法 2020 3 21 27 第三章一维搜索方法 这种情况应消除左边区段 x1 x p 然后用x p x2 x3作为x1 x2 x3新3点 重新构造二次曲线p x 如此反复计算 直到满足条件为止 整个迭代过程的计算结果列于下表 3 4一维搜索的的插值方法 3 4 2抛物线法 二次插值法 2020 3 21 28 第三章一维搜索方法 对于二次函数用二次插值法求优 只需一次插值计算即可 对于非二次函数 随着区间的缩短使函数的二次性态加强 因而收敛也是较快的 二次插值法收敛速度快 有效性好 但是程序复杂 可靠性较差 3 4一维搜索的的插值方法 3 4 2抛物线法 二次插值法 2020 3 21 29 3 5一维搜索的比较 第三章一维搜索方法 区间缩小方法 试探法中试验点位置是由某种给定的规律确定的 它不考虑函数值的分布 例如 黄金分割法是按等比例0 618缩短率确定的 插值法中 试验点位置是按函数值近似分布的极小点确定的 试验点确定 试探法仅对试验点函数值的大小进行比较 而函数值本身的特性没有得到充分利用 这样即使对一些简单的函数 例如二次函数 也不得不象一般函数那样进行同样多的函数值计算 插值法是利用函数在已知试验点的值 或导数值 来确定新试验点的位置 当函数具有比较好的解析性质时 例如连续可微性 插值法比试探法效果更好 2020 3