MATLAB黄金分割法课程论文--

中中南南林林业业科科技技大大学学 本科课程论文 学 院 理学院 专业年级 14 级信息与计算科学 2 班 学生姓名 邱文林 学 号 20144349 课 程 MATLAB 程序设计教程 设计题目 基于 MATLAB 的黄金分割法 与抛物线插值法 指导教师 龚志伟 2016 年 4 月 精品文档 2欢迎下载2欢迎下载 精品文档 3欢迎下载3欢迎下载 中中文文摘摘要要 为了求解最优化模型的最优解 可使用基于 MATLAB 算法编程的黄金分割法与 抛物线插值法 来实现求解的过程 黄金分割法是通过所选试点的函数值而逐步缩 短单谷区间来搜索最优点 利用迭代进而得出结论 抛物线插值法亦称二次插值法 是一种多项式插值法 逐次以拟合的二次曲线的极小点 逼近原寻求函数极小点的 一种方法 通过将 MATLAB 与最优化问题相结合 不仅可以加深对黄金分割法 抛物 线插值法的基本理解和算法框图及其步骤的全面理解 也有利于帮助我们掌握 MATLAB 的使用方法 关键词 关键词 MATLAB 黄金分割法 抛物线插值法 最优解 迭代 精品文档 4欢迎下载4欢迎下载 英英文文摘摘要要 In order to solve the optimization model of the optimal solution using MATLAB algorithm based on the golden section method and the parabola interpolation method to realize the process of solving The golden section method is used to search the most advantage through the function value of the selected pilot which can be used to search for the most advantage Parabolic interpolation method also known as the two interpolation method is a polynomial interpolation method successive to fit the two curve of the minimum point the original search function to find a very small point of the method By combining MATLAB and optimization problems can not only deepen the comprehensive understanding of the golden section method the parabola interpolation basic understanding and block diagram of the algorithm and steps but also conducive to help us to grasp the method of using MATLAB KeyKey words words MATLAB golden section method parabolic interpolation method optimal solution iteration 精品文档 5欢迎下载5欢迎下载 目目 录录 1 黄金分割法 2 1 1 算法原理 2 1 2 算法步骤 2 1 3 黄金分割法算法框图 3 2 抛物线插值法 4 2 1 算法原理 4 2 2 算法步骤 4 2 3 抛物线插值法算法框图 5 3 算法的 MATLAB 实现 6 3 1 黄金分割法程序代码 6 3 2 实例验证 6 3 3 误差分析 9 3 4 抛物线插值法程序代码 10 3 5 实例验证 11 3 6 误差分析 12 3 7 黄金分割法与抛物线插值法的对比 13 参考文献 15 精品文档 1欢迎下载 引言引言 为了对最优化问题进行求解 为了更好的掌握 MATLAB 的运用 本文主要介绍一 维最优化问题的一维搜索法黄金分割法与抛物线插值法 利用 MATLAB 算法将其实现 黄金分割法也叫 0 618 法 它是一种基于区间收缩的极小点搜索算法 当用进退法 确定搜索区间后 我们只知道极小点包含于搜索区间内 但是具体是哪个点 无法 得知 黄金分割法的思想很直接 既然极小点包含于搜索区间内 那么可以不断的 缩小搜索区间 就可以使搜索区间的端点逼近到极小点 抛物线插值法 parabolic interpolation met hod 亦称二次插值法一种多项式插值法 逐次以拟合的二次曲线 的极小点 逼近原寻求函数极小点的一种方法 能求得精度较高的解 但速度会比较 慢 时至今日 经过 Math Works 公司的不断完善 MATLAB 已经发展成为适合多学 科 多种工作平台的功能强劲的大型软件 在国外 MATLAB 已经经受了多年考验 在欧美等高校 MATLAB 已经成为线性代数 自动控制理论 数理统计 数字信号处 理 时间序列分析 动态系统仿真等高级课程的基本教学工具 成为攻读学位的大 学生 硕士生 博士生必须掌握的基本技能 在设计研究单位和工业部门 MATLAB 被广泛用于科学研究和解决各种具体问题 精品文档 2欢迎下载 1 1 黄金分割法黄金分割法 1 11 1 算法原理算法原理 黄金分割法的基本原理 黄金分割法又称 0 618 法 它是通过不断缩短搜索区间的长度来寻求一维函数的极 小点 这种方法的原理是 在搜索区间 a b 内按如下规则对称地取两点 计算它们的函数值 f1 f a1 f2 f a2 比较它们的大小 结果有两种可能 1 21 2 算法步骤算法步骤 1 f1 f2 如图 1 所示 极小点必在 a1 b 内 消去区间 a a1 令 a a1 产 生新区间 a b 到此区间缩短了一次 值得注意的是新区间的 a1 点与原区间的 a2 点重合 可令 a1 a2 这样可少找一个新点和节省一次函数值计算 2 f1 f2 极小点必在 a a2 内 消去区间 a2 b 令 b a2 产生新区间 a b 到 此区间缩短了一次 同样新区间 a2 点与原区间的 a1 点重合 可令 a2 a1 f2 f1 3 当缩短的新区间长度小于等于某一精度 即 b a f2 b a2 a2 a1 f2 f1 a1 a 0 382 b a f1 f a1 a a1 a1 a2 f1 f2 a2 a 0 618 b a f2 f a2 b a 0 令 a0 a b0 b k 0 求二次插值多项式的极小点 tk 1 2 10 2 1 222222 kkkkkkkkk kkkkkkkkk batfatbftbaf batfatbftbaf 若 f tk 1 f tk 则当 tk 1 tk e 时 停止迭代输出 tk 1 否则转 若 f tk 1 f tk 则当 tk 1 tk e 时 停止迭代输出 tk 否则转 若 tk 1 tk 令 ak 1 ak bk 1 tk tk 1 tk 1 置 k k 1 转 否则令 ak 1 tk bk 1 bk tk 1 tk 1 置 k k 1 转 若 tk 1 tk 令 ak 1 tk 1 bk 1 tk tk 1 tk 置 k k 1 转 否则令 ak 1 ak bk 1 tk 1 tk 1 tk 置 k k 1 转 初始插值内点可以取搜索区间 a b 的中点 精品文档 5欢迎下载 2 32 3 抛物线插值法算法框图抛物线插值法算法框图 开始 确定 tk ak bk 要求 f ak f tk f bk f tk 按 2 10 计算 tk 1 tk 1 tk e t tk 1 f f tk 1 Y 输出 t f 结束 N tk 1 tk Y f tk 1 f tk bk tk 1 f bk f tk 1 Y ak tk tk tk 1 f ak f tk f tk f tk 1 f tk 1 f tk N Y bk tk tk tk 1 f bk f tk f tk f tk 1 ak tk 1 f ak f tk 1 精品文档 6欢迎下载 3 3 算法的算法的 MATLABMATLAB 实现实现 3 13 1 黄金分割法程序代码黄金分割法程序代码 在 MATLAB 中编程实现的黄金分割法函数为 golden 功能 用黄金分割法求解一维函数的极值 调用格式 tmin golden f a b e 其中 f 目标函数 a 极值区间左端点 b 极值区间右端点 e 精度 tmin 目标取最小值时的自变量值 黄金分割法的 MATLAB 程序代码如下 主程序 主程序 syms t a b e a input 搜索区间第一点 a b input 搜索区间第二点 b e input 搜索精度 ne disp 需求的最优化函数 f f t tmin golden f a b e m m文件 文件 function tmin golden f a b e format long k 0 a1 b 0 618 b a a2 a 0 618 b a while b a e y1 subs f a1 y2 subs f a2 if y1 y2 a a1 a1 a2 y1 y2 a2 a 0 618 b a else b a2 a2 a1 y2 y1 a1 b 0 618 b a 精品文档 7欢迎下载 end k k 1 end tmin a b 2 fmin subs f tmin fprintf k n disp k x 3 0 001 5 y x x 2 plot x y k tmin fmin bp 3 23 2 实例验证实例验证 minf t t t 2 已知初始单谷区间 a b 3 5 按精度 e 0 001 计 算 代入到主程序代码 代入到主程序代码 搜索区间的第一点 a 3 搜索区间的第二点 b 5 搜索精度 e 0 001 需求的最优化函数 f f t tmin golden f a b e f t t 2 f t t 2 tmin golden f a b e k 19 tmin 1 000120312207862 精品文档 8欢迎下载 fmin tmin tmin 2 fmin 0 999999985524973 目标函数的曲线图如图目标函数的曲线图如图 1 11 1 所示所示 注 图中 所标识的点为黄金分割法所求的极小点 图 1 1 函数 f t t t 2 的曲线图 精品文档 9欢迎下载 3 33 3 误差分析误差分析 1 1 f t t t 2 的精确解如下 f 1 2 0 p polyder f t1 roots p f1 polyval f t1 t1 1 f1 1 极小点误差 e1 tmin t1 t1 1 000120312207862 1 1 1e 4 极小值误差 e2 f1 fmin f1 1 0 999999985524973 1 1e 8 结论结论 在精度 e 0 001 的情况下 通过黄金分割法经过 19 次迭代 求得 tmin 1 000120312207862 与精确值的误差 e1 1e 4e fa subs f findsym f a 区间左端点函数值 fb subs f findsym f b 区间右端点函数值 ft0 subs f findsym f t0 内插点函数值 tu fa b 2 t0 2 fb t0 2 a 2 ft0 a 2 b 2 td fa b t0 fb t0 a ft0 a b t1 tu 2 td 插值多项式的极小点 ft1 subs f findsym f t1 插值多项式的极小值 精品文档 11欢迎下载 tol abs t1 t0 if ft1 ft0 if t1 t0 b t0 t0 t1 else a t0 t0 t1 end k k 1 else if t1 syms t f t t 2 tmin fmin minPWX f 3 5 tmin 1 fmin 精品文档 12欢迎下载 1 目标函数的曲线图如图目标函数的曲线图如图 1 21 2 所示所示 注 图中O O所标识的点为抛物线插值法所求的极小点 图 1 2 函数 f t t t 2 的曲线图 3 63 6 误差分析误差分析 1 1 f t t t 2 的精确解如下 f 1 2 0 p polyder f t1 roots p f1 polyval f t1 t1 1 f1 1 精品文档 13欢迎下载 极小点误差 e3 tmin t1 t1 1 1 1 0 极小值误差 e4 fmin f1 f1 0 3 73 7 黄金分割法与抛物线插值法的对比黄金分割法与抛物线插值法的对比 注 下图中红色 是黄金分割法的极小点标识位置 蓝色 O O 是抛物线插值法的极小点标识位置 图 1 3 函数 f t t t 2 的曲线图 精品文档 14欢迎下载 对比结论 对比结论 由图分析 精度 e 0 001 的情况下 如上图 1 3 所示 黄金分割法与抛物线插值法求出的极小 点都极为接近精确值 由误差分析 黄金分割法极小点误差 e1 tmin t1 t1 1 000120312207862 1 1 1e 4 抛物线插值法极小点误差 e3 tmin t1 t1 1 1 1 0 可见 在满足同精度的情况下 抛物线插值法能求出精度更高的解 但是速度会比 较慢 黄金分割法的优点是可以用