数学与计算科学学院
实验报告
实验项目名称使用非精确线搜索Armijo算法确定步长的最速下降法
所属课程名称最优化方法
实验类型算法编程
实验日期
班级
学号
姓名
成绩
2、向梯度相反的方向移动x，其中为步长。如果步长足够小，则可以保证每一次迭代都在减小，但可能导致收敛太慢，如果步长太大，则不能保证每一次迭代都减少，也不能保证收敛。
3、循环迭代步骤2，直到x的值变化到使得在两次迭代之间的差值足够小，比如，也就是说，直到两次迭代计算出来的基本没有变化，则说明此时已经达到局部最小值了。
4、此时，输出x，这个x就是使得函数最小时的x的取值。
【实验过程】
梯度下降法的计算过程就是沿梯度下降的方向求解极小值（也可以沿梯度上升方向求解极大值）。
其迭代公式为,其中代表梯度负方向，表示梯度方向上的搜索步长。梯度方向我们可以通过对函数求导得到，步长的确定比较麻烦，太大了的话可能会发散，太小收敛速度又太慢。一般确定步长的方法是由线性搜索算法来确定，即把下一个点的坐标ak+1看做是的函数，然后求满足f(ak+1)的最小值的即可。
因为一般情况下，梯度向量为0的话说明是到了一个极值点，此时梯度的幅值也为0.而采用梯度下降算法进行最优化求解时，算法迭代的终止条件是梯度向量的幅值接近0即可，可以设置个非常小的常数阈值。
【实验结论】（结果）
梯度下降法处理一些复杂的非线性函数会出现问题，例如Rosenbrock函数：
其最小值在处，函数值为。但是此函数具有狭窄弯曲的山谷，最小点就在这些山谷之中，并且谷底很平。优化过程是之字形的向极小值点靠近，速度非常缓慢。靠近极小值时收敛速度减慢。直线搜索时可能会产生一些问题。可能会“之字形”地下降。
【实验小结】（收获体会）
这次的实验报告，使得我们对这些算法的思想更加了解，在选择线性搜索的方法时，我们深刻体会到各类参数设置对程序效率的重要性，不同的问题要选用合适的参数来求解，这样使得问题求解及程序运行的效率最高。通过不断地翻阅课本，剖析程序，我们最后实现了对程序的修改和完善，对提供的问题作出了较好的解答。总的来说，对无约束最优化的求解，每种方法在解决不同的问题中效果不能都达到最优，所以我们在实际应用中，要根据实际情况选择合适的方法，争取最大可能的尽快的接近最优。
本次实验不仅使我们基本了解了最优化的实用算法的结构及性能，而且也使得我们对matlab的一些编程技巧更加熟悉，收获很大。
三、指导教师评语及成绩：
评语等级
评语
及
不及格
优良中
格
1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强
2.实验方案设计合理
3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）
4实验结论正确.
成绩：
指导教师签名：
批阅日期：
附录1：源程序
附录2：实验报告填写说明
1．实验项目名称：要求与实验教学大纲一致。
2．实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。
3．实验原理：简要说明本实验项目所涉及的理论知识。
4．实验环境：实验用的软、硬件环境。
5．实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过程。
对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作。对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设计思路和设计方法，再配以相应的文字说明。对于创新性实验，还应注明其创新点、特色。
6．实验过程（实验中涉及的记录、数据、分析）：写明具体实验方案的具体实施步骤，包括实验过程中的记录、数据和相应的分析。
7．实验结论（结果）：根据实验过程中得到的结果，做出结论。
8．实验小结：本次实验心得体会、思考和建议。
9．指导教师评语及成绩：指导教师依据学生的实际报告内容，给出本次实验报告的评价。
数学与计算科学学院 实验报告 实验项目名称使用精确搜索算法确定步长的最速下降法 所属课程名称最优化方法 实验类型算法编程 实验日期 201 班级 学号 姓名 成绩 一、实验概述： 【实验目的】
(1) 掌握精确搜索算法确定步长的最速下降法； (2) 使用计算机语言表达最优化方法。 【实验原理】 最速下降法又称为梯度法，是1847年由著名数学家Cauchy 给出的。他是解析法中最古老的一种，其他解析方法或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础。 设无约束问题中的目标函数 f : Rn R1一阶连续可微。 最速下降法的基本思想是：从当前点k x 出发，取函数 f (x)在点k x 处下降最快的方向作为我们的搜索方向k p .由 f (x)的 Taylor 展式知 ()()()() k k k k T k k f x f x tp t f x p o tp -+=-?+ 略去t 的高阶无穷小项不计，可见取()k k p f x =-?时，函数值下降得最多。于是，我们可以构造出最速下降法的迭代步骤。 解无约束问题的的最速下降法计算步骤 第 1 步 选取初始点(0)x ，给定终止误差ε ，令k:=0； 第 2 步 计算?f (k x )，，若‖?f (k x )‖≤ ε ，停止迭代.输出k x .否则 进行第三步 第 3 步 取()k k p f x =-?； 第 4 步进行一维搜索，求k t ，使得 1()(())min (()) k k k k k k f x f x t f x f x t f x +=-?=-? 令,k:=k+1，转第2 步。 由以上计算步骤可知，最速下降法迭代终止时，求得的是目标函数驻点的一个近似点。 【实验环境】 计算机 VC++
最速下降法求解线性代数方程组 要求：对于给定的系数矩阵、右端项和初值，可以求解线性代数方程组 一、最速下降法数学理论 在基本迭代公式k k k k P t X X +=+1中，每次迭代搜索方向k P 取为目标函数)(X f 的负梯度方向，即)(k k X f P -?=，而每次迭代的步长k t 取为最优步长，由此确定的算法称为最速下降法。 为了求解问题)(min X f ，假定我们已经迭代了k 次，获得了第k 个迭代点k X 。现在从k X 出发，可选择的下降方法很多，一个非常自然的想法是沿最速下降方向（即负梯度方向)进行搜索应该是有利的，至少在k X 邻近的范围内是这样。因此，去搜索方向为 )(k k X f P -?=. 为了使目标函数在搜索方向上获得最多的下降，沿k P 进行一维搜索，由此得到第1+k 个跌带点，即 )(1k k k k X f t X X ?-=+， 其中步长因子k t 按下式确定 ))((m in ))((k k k k k k X f t X f X f t X f ?-=?-， ))(,(1k k k X f X ls X -?=+. （1） 显然，令 ,2,1,0=k 就可以得到一个点列 ,,,210X X X ,其中0X 是初始点，由计算者任意选定。当)(X f 满足一定的条件时，由式（1）所产生的点列}{k X 必收敛于)(X f 的极小点。
二、最速下降法的基本思想和迭代步骤 已知目标函数)(X f 及其梯度)(X g ，终止限21,εε和3ε. （1）选定初始点0X ，计算)(),(0000X g g X f f ==；置0=k . （2）作直线搜索：),(1k k k g X ls X -=+；计算)(),(1111++++==k k k k X g g X f f . 用终止准则检验是否满足：若满足，则打印最优解))(,(11++k k X f X ，结束；否则，置1+=k k ，转（2） （3）最速下降法算法流程图如图所示.
《MATLAB 程序设计实践》课程考核 实践一、编程实现以下科学计算法，并举一例应用之。（参考书籍《精通MATLAB 科学计算》，王正林等著，电子工业出版社，2009年） “最速下降法无约束最优化” 最速下降法： 解： 算法说明：最速下降法是一种沿着N 维目标函数的负梯度方向搜索最小值的方法。 原理：由高等数学知识知道任一点的负梯度方向是函数值在该点下降最快的方向，那么利用负梯度作为极值搜索方向，达到搜寻区间最速下降的目的。而极值点导数性质，知道该点的梯度=0，故而其终止条件也就是梯度逼近于0，也就是当搜寻区间非常逼近极值点时，即：当▽f(a ）→0推出f(a ）→极值）（x f ，f(a ）即为所求。该方法是一种局部极值搜寻方法。 函数的负梯度表示如下： -g(x ）=-▽f(x)=-?????1 )(x x f 2)(x x f ?? … T N x x f ?????)( 搜索步长可调整，通常记为αk （第k 次迭代中的步长）。该算法利用一维的线性搜索方法，如二次逼近法，沿着负梯度方向不断搜索函数的较小值，从而找到最优解。 方法特点（1）初始值可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。（2）任意相邻两点的搜索方向是正交的，它的迭代路径胃绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。（3）全局收敛，线性收敛，易产生扭摆现象而造成早停。 算法步骤：最速下降法的基本求解流程如下： 第一步 迭代次数初始化为k=0，求出初始点0x 的函数值f 0=f （0x ）。 第二步 迭代次数加1，即k=k+1，用一维线性搜索方法确定沿负梯度方向-1-k g 的步长1k -α，其中1k -α=ArgMinaf （111k /----k k g g x α）。 第三步 沿着负梯度方向寻找下一个接近最小值的点，其中步长为1k -α，得到下一点的坐标为：1111/-----=k k k k k g g x x α。
实验报告 实验名称：加速步长法 院（系）：机电学院 专业班级：机械制造及其自动化 姓名：赵丹 学号：100710431 2013年5 月3 日
实验一：加速步长法实验日期：2013年5 月3日一、实验目的 了解MATLAB的基本运用 了解MATLB在优化中的使用 二、实验原理 加速步长法是利用试探来确定单谷函数的初始搜索区间。其主要思路是：从一点出发，按照一定的步长，试图确定出函数值呈现“高低高”规律的相邻三点。从一个方向试探搜索，如不成功，则沿反方向探索。如方向正确，则加大步长探索。直至最终三点x1x2x3，满足x1 h=-h; x2=x4; f2=f4; else x3=x2; x2=x1; x1=x4; break; end end end left=min(x1,x3); right=x1+x3-left; 四调用执行程序： clc syms t f=t^3-t^2-2*t+1; [left,right]=xiti4_1(f,0,0.1) 执行结果：left = 0.7000 right = 3.1000 实验小结 通过本实验了解了了matlab的基本操作方法，了解加速步长法的原理与基本运用 最速下降法 姓名：沈东东 班级：研1404 学号：1415033005 一、最速下降法的原理 目标函数:(1)n f R R n →>在决策变量的当前点()k n x R ∈处的一阶Taylor 展开式为 ()()()()()()()k k k T f x f x g x δδοδ+=++ 式中，()()k n g x R ∈为f 在点()k x 处的梯度向量。 当扰动量n R δ∈充分小时，有 ()()()()()()k k k T f x f x g x δδ+≈+ 设新的迭代点为(1)()k k x x δ+=+，于是得到 (1)()()()()()k k k T f x f x g x δ+-≈ 为了使(1)k x +处的目标函数值比()k x 处有所下降，需要满足 ()()0k T g x δ< 此外，梯度向量()()k g x 和扰动量δ的内积可以表示为 ()()()()cos k T k g x g x δδθ= 式中，θ为两向量之间的夹角。 若要使目标函数值的下降量尽可能大，可知δ的方向应该为梯度方向的负方向，即cos 1θ=-。 函数f 在点()k x 处的负梯度方向称为该点的最速下降方向。在每次迭代时都取最速下降方向作为搜索方向的方法就称为最速下降法。 二、最速下降法的特点 1.若()k x 不是极小点，则f 在点()k x 处的最速下降方向总是下降方向。 2.如果每次迭代时都用精确搜索方法得到最佳步长作为搜索步长，则寻优过程中相邻的最速下降方向是正交的。 3最速下降法产生的迭代点序列在一定条件下是线性收敛的，其收敛性质与极小点*x 处的Hesse 矩阵有关。 三、最速下降法的计算步骤 最速下降法的计算步骤如下： 步骤1：已知待求问题的目标函数()f x ，选择初始点(0)x ，并设定精度要求tol ，令:0k =。 步骤2：计算()f x 在点()k x 处的梯度向量()()k g x ，得到最速下降方向()()()k k d g x =-。 步骤3：从()k x 出发，沿方向()k d 进行非精确一位搜索，求得可接受步长()k α。 步骤4：计算下一个迭代点(1)()()()k k k k x x d α+=+及对应的目标函数值(1)()k f x +。 步骤5：若满足(1)()k k x x tol +-<，则终止迭代，分别输出(1)k x +和(1)()k f x +作为该问题的极小点和极小值；否则令:1k k =+，转步骤2. 四、最速下降法的流程图 最速下降法的流程图如下图所示 最速下降法Matlab实现 实验目的： 1.掌握迭代法求解无约束最优化问题的基本思想 2.通过实验掌握最速下降法的Matlab算法的基本步骤 实验内容： 1.迭代法求解无约束最优化问题的基本思想 给定一个初始点x(0), 按照某一迭代规则产生一个迭代序列{x(k)}. 使得若该序列是有限的, 则最后一个点就是原问题的极小点; 否则, 若序列{x(k)} 是无穷点列时, 它有极限点且这个极限点即为原问题的极小点. 设x(k) 为第k 次迭代点, d(k) 为第k 次搜索方向, a(k)为第k 次步长因子, 则第k 次迭代完成后可得到新一轮(第k + 1 次) 的迭代点 x(k+1) = x(k) + a(k) d(k). 2.无约束优化问题迭代算法的一般框架 步0 给定初始化参数及初始迭代点x(0). 置k := 0. 步1 若x(k) 满足某种终止准则, 停止迭代, 以x(k) 作为近似极小点. 步2 通过求解x(k) 处的某个子问题确定下降方向d(k). 步3 通过某种搜索方式确定步长因子a(k), 使得f(x(k) + a(k) d(k)) < f(x(k)). 步4 令x(k+1) := x(k) + a(k) d(k), k := k + 1, 转步1. 3. 最速下降法的基本步骤 步0 选取初始点x(0) ∈R^n, 容许误差0 ≤e ?1. 令k := 1. 步1 计算g(k) = ?f(x(k)). 若‖g(k)‖≤e, 停算, 输出x(k)作为近似最优解. 步2 取方向d(k)= ?g(k). 步3 由线搜索技术确定步长因子a(k),即 min f(a(k))=f(x(k)+a(k)d(k)). 步4 令x(k+1) := x(k) + a(k)d(k)), k := k + 1, 转步1. 变步长梯形求积法计算定积分 1．原理： 变步长求积法的主要思想是利用若干小梯形的面积代替原方程的积分，当精度达不到要求时，可以通过增加点数对已有的区间再次划分，达到所需精度时即可；其中由于新的式子中有原来n点中的部分项，故可以省略一些计算，符合了计算机计算存储的思想。 主要公式：T2n=T n/2+(h/2)*Σf(x k+; 2．C++语言实现方式： 通过每次的T n值和新增的函数值点计算T2n，再通过判断|T n-T2n|的大小来判断是否达到精度要求。 3．源程序如下： #include"" #include"" double f(double x)//预先输入的待积分函数 { double s; s=log(x*x); return(s); } double ffts(double a,double b,double eps) { int n,k; double fa,fb,h,t1,p,s,x,t; fa=f(a); fb=f(b); n=1; h=b-a; t1=h*(fa+fb)/2; p=eps+1; while(p>=eps) { s=0; for(k=0;k<=n-1;k++) { x=a+(k+*h; s=s+f(x); } t=t1/2+h*s/2; p=fabs(t1-t); cout<<"步长n为:"< . 数学与计算科学学院 实验报告 实验项目名称使用精确搜索算法确定步长的最速下降法所属课程名称最优化方法 实验类型算法编程 实验日期 201 班级 学号 姓名 成绩 【实验目的】 (1) 掌握精确搜索算法确定步长的最速下降法； (2) 使用计算机语言表达最优化方法。 【实验原理】 最速下降法又称为梯度法，是1847年由著名数学家Cauchy 给出的。他是解析法中最古老的一种，其他解析方法或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础。 设无约束问题中的目标函数 f : Rn R1一阶连续可微。 最速下降法的基本思想是：从当前点k x 出发，取函数 f (x)在点k x 处下降最快的方向作为我们的搜索方向k p .由 f (x)的 Taylor 展式知 ()()()() k k k k T k k f x f x tp t f x p o tp -+=-?+ 略去t 的高阶无穷小项不计，可见取()k k p f x =-?时，函数值下降得最多。于是，我们可以构造出最速下降法的迭代步骤。 解无约束问题的的最速下降法计算步骤 第 1 步 选取初始点(0)x ，给定终止误差ε ，令k:=0； 第 2 步 计算 f (k x )，，若‖ f (k x )‖ε ，停止迭代.输出k x . 否则进行第三步 第 3 步 取()k k p f x =-?； 第 4 步进行一维搜索，求k t ，使得 1()(())min (()) k k k k k k f x f x t f x f x t f x +=-?=-? 令,k:=k+1，转第2 步。 由以上计算步骤可知，最速下降法迭代终止时，求得的是目标函数驻点的一个近似点。 【实验环境】 计算机 VC++ 二、实验内容： 【实验方案】 1. 列举例题 2. 手工计算 3. 将计算步骤等实现程序化 4. 实验结果分析 共轭梯度法 一 共轭梯度法原理 对于线性方程组A b X =，即： 1111221n 12112222n 21122nn n n n n n n a x a x a x b a x a x a x b a x a x a x b +++=??+++=????++ += ? （1） 其中，()=ij n n a ?A 为对称正定矩阵，()1i n b b ?=，如何熟练地运 用最速下降法与共轭梯度法的求解线性方程组。 在求解线性方程组之前，首先用内积将问题转化为函数问题。 1 最速下降法 最速下降法是一种运用梯度与极值的性质，综合数值计算方法寻找局部极值。 基本思想：任一点的负梯度方向是函数值在该点下降最快的方向。将n 维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法。 具体步骤： 1、搜索方向：()k k d f x =-?，即最速下降方向。 2、搜索步长：k λ取最优步长，即满足： ()min ()k k k k k f x d f x d λ λλ+=+ 1 给定初始点0n x R ∈，允许误差0ε≥，令1k =。 2 计算搜索方向()k k d f x =-?。 3 若k d ε≤，则k x 为所求的极值点，否则，求解最优步长k λ，使得()min ()k k k k k f x d f x d λ λλ+=+。 4 令1k k k k x x d λ+=+，1k k =+ 最速下降方向是反映了目标函数的局部性质，它只是局部目标函数值下降最快的方向。 2 共轭梯度法 对于1 min ()2T T f x x Ax b x =+ 其中，0n x R ∈，A 是对称正定矩阵。 基本思想：将共轭性与最速下降法相结合利用已知迭代点的梯度方向构造一组共轭方向，并沿此方向搜索，求出函数的极小值。 具体步骤： 1 取初始点(0)x ，取第一次搜索方向为(0)(0)()d f x =-?。 2 设已求得(1) k x +，若(1) ()0k f x +?≠，令(1) ()()k g x f x +=? ，则下一个 搜索方向 (1)()1k k k k d g d β++=-+ （1） 由于(1) k d +与() k d 关于A 共轭，所以给（1）两边同时乘以()T k d A ， 即： ()(1)()()()10T T T k k k k k k k d d d g d d β++A =-A +A = 解得：()1()() k T k k k T k d A g d Ad β+= （2） 3 搜索步长的确定，已知迭代点()k x ，和搜索方向()k d ，确定 步长k λ，即：()()min ()k k f x d λ λ+ 记 ()()()()k k f x d φλλ=+， 令 ()()()()()0k k T k f x d d φλλ'=?+= 既有：()()()[()]0k k T k A x d b d λ++= 最速下降法 %% 最速下降法图示 % 设置步长为0.1，f_change为改变前后的y值变化，仅设置了一个退出条件。syms x;f=x^2; step=0.1;x=2;k=0; %设置步长,初始值,迭代记录数 f_change=x^2; %初始化差值 f_current=x^2; %计算当前函数值 ezplot(@(x,f)f-x.^2) %画出函数图像 axis([-2,2,-0.2,3]) %固定坐标轴 hold on while f_change>0.000000001 %设置条件，两次计算的值之差小于某个数，跳出循环 x=x-step*2*x; %-2*x为梯度反方向，step为步长，！最速下降法！ f_change = f_current - x^2; %计算两次函数值之差 f_current = x^2 ; %重新计算当前的函数值 plot(x,f_current,'ro','markersize',7) %标记当前的位置 drawnow;pause(0.2); k=k+1; end hold off fprintf('在迭代%d次后找到函数最小值为%e，对应的x值为%e\n',k,x^2,x) wolfe准则 unction [alpha, newxk, fk, newfk] = wolfe(xk, dk) rho = 0.25; sigma = 0.75; alpha = 1; a = 0; b = Inf; while (1) if ~(fun(xk+alpha*dk)<=fun(xk)+rho*alpha*gfun(xk)'*dk) b = alpha; alpha = (alpha+a)/2; continue; end if ~(gfun(xk+alpha*dk)'*dk>= sigma*gfun(xk)'*dk) a = alpha; alpha = min([2*alpha, (b+alpha)/2]); continue; end break; end newxk = xk+alpha*dk; fk = fun(xk); newfk = fun(newxk); ISSN 1000-0054CN 11-2223/N 清华大学学报(自然科学版)J T singh ua Un iv (Sci &Tech ),2006年第46卷第10期 2006,V o l.46,N o.1021/40 1719-1722 基于自适应步长的直线生成算法 黄斌茂, 张 利 (清华大学电子工程系,北京100084) 收稿日期:2005-07-13 基金项目:国家自然科学基金资助项目(60172027)作者简介:黄斌茂(1981-),男(汉),江西,硕士研究生。通讯联系人:张利,副教授, E-mail:chin azh angli@mail.tsingh https://www.doczj.com/doc/bc17990045.html, 摘 要:为了改进计算机图形学中画线算法的效率,提出一种基于自适应步长的直线生成算法和一种集成了对称性、最大公约数和自适应步长的集成算法。由于直线仅包含一种或两种与斜率有关的像素模式,算法利用这一特性,自适应地采用最佳步长,在单次判决中生成多个像素。通过综合使用直线像素的中点对称性、最大公约数性质以及像素模式的有限性等3种相互独立的特性,集成算法在单次判决中可生成更多像素。算法的仿真结果表明:新算法生成直线的效率更高、速度更快。 关键词:Bresenham 算法;自适应步长;对称性;最大公约 数;像素模式 中图分类号:T P 391.4文献标识码:A 文章编号:1000-0054(2006)10-1719-04 Self -adaptive step straight -line algorithms HUA NG Binmao ,ZH ANG Li (Department of Electronic Engineering , T s inghua University ,Beij ing 100084,China ) Abstract :Line draw ing algorithm in computer grap hics sys tems is improved w ith a self-adaptive s tep straight-line algor ith m and an oth er integrated algorithm th at combines self-adaptive step algorithm w ith th e s ymmetr y an d greatest com mon divisor (GCD)-based algor ith ms.Th e self-adaptive step algorithm uses the limited pixel patter ns inherent in line s egments to adaptively determine the best step that corres ponds to the line slope an d then gen erates m ulti-pixels in each judgemen t.T he integrated algorithm utilizes the sym metry,GCD,an d limited pixel patterns and gen erates more p ixels in each https://www.doczj.com/doc/bc17990045.html,parisons w ith Bresen ham 's algorithm sh ow th at the integrated algorithms are m ore effective and efficient. Key words :Bresen ham's algorithm ;self-adaptive steps;s ymmetr y; greatest common divisor (GCD);pixel patter n 直线段(简称直线)是图形的基本单元,图形渲染的速度很大程度上取决于直线的生成速度。 Br esenham 算法[1] 是目前使用最为广泛的直线生成算法,它采用整数加减运算,避免了浮点数操作和乘除运算,从而极大地提高了算法的效率。在该算法的 基础上,研究界提出了多种改进算法。其改进思路可分为两类:1)将直线分割成多条短线段,采用并行算法生成直线[2] ;2)通过一次误差判别操作,在一次循环中生成多个像素[312]。 直线上的像素点关于直线中点对称,文[5]利用这一特性,每个循环生成两个像素点。 对端点为S (x s ,y s )及E (x e ,y e )的直线,当 x e -x s 和 y e -y s 的最大公约数r 不为1时,直线上有r 段像素模式相同的线段。文[4]通过在每个循环内生成r 个像素,加速了直线的生成。但当r =1时,该算法比Brensenham 算法效率要低。文[68]采用N 步长(N ≥2)直线生成方法,将八分圆分成多个子区,每个子区有N +1种像素模式,根据直线的斜率可决定其子区归属。该算法每个循环可生成N 个像素。其不足是:每个子区中的N +1种像素模式的初始化开销很大;步长固定,不能采用最佳步长。还有一些研究者结合对称性、多步长、最大公约数提出集成算法[9]。 文[10]简要地提出自适应步长的思想,但未给出推导证明与具体算法;文[11,12]在直线斜率为0< m <0.5时,一次生成多个像素以提高直线的生成效率,但没有注意到直线像素模式关于m =±0.5的对称性。此外,文[11,12]都没有给出算法的仿真结果。 上述各种改进算法的共同点是在每个循环中生成多个像素,但每次生成的像素个数固定,不能自适应地采用最合适的步长。本文利用直线在八分圆中像素模式的对称性,以及任一直线只有一种或者两种与斜率相关的像素模式这一特性,提出一种基于 实验的题目和要求 一、所属课程名称： 最优化方法 二、实验日期: 20１０年5月１0日~２010年5月１５日 三、实验目的 掌握最速下降法,牛顿法和共轭梯度法的算法思想，并能上机编程实现相应的算法。 二、实验要求 用ＭA ＴLA Ｂ实现最速下降法，牛顿法和共轭梯度法求解实例。 四、实验原理 最速下降法是以负梯度方向最为下降方向的极小化算法，相邻两次的搜索方向是互相直交的。牛顿法是利用目标函数)(x f 在迭代点k x 处的T ａylor 展开式作为模型函数,并利用这个二次模型函数的极 小点序列去逼近目标函数的极小点。共轭梯度法它的每一个搜索方向是互相共轭的，而这些搜索方向k d 仅仅是负梯度方向k g -与上一次接 待的搜索方向1-k d 的组合。 五.运行及结果如下： 最速下降法: 题目：f=（x-2）^２+(y-４）^2 Ｍ文件： fu ｎcti ｏn [R,n]=stee ｌ（x0,y0，e ｐs) syms ｘ； syms y ; f=(x-2)^2+(ｙ-４）^2; ｖ=[x,y]; ｊ＝ｊac ｏbi ａｎ(f ，v); T=[s ｕbs(j(１),ｘ,x0）,subs （j （2),ｙ，y0)]; temp=s ｑrt((Ｔ(1)）^2＋(T （2))＾2); x １＝x0;y １=y ０; ｎ=0; sym ｓ k ｋ; w ｈi ｌe (temp>eps ） ｄ=－Ｔ； ｆ1=x １+kk*d(1);f2=ｙ1+k ｋ*ｄ（２); fT=[su ｂs(j （1),ｘ,ｆ１),ｓｕb ｓ(j(2),ｙ,ｆ2)]; fu ｎ=sqrt((fT(1））^2+(ｆT(2)）^２）; 第五题： 解：选择类型为： 2/13()x t y t x e x =+ 其中123,,x x x 是待求参数。根据最小二乘原理，参数123,,x x x 是下面优化问题的解。 []2 8 1231 m in (,,)()i i i f x x x y t y == -? 用最速下降法求解这一无约束的最优化问题。 zuiyouhua.m function sh=zuiyouhua(x0) % x0为初始猜测值 syms x y z a al; %====================================== t=[0.2,1,2,3,5,7,11,16]; r1=[5.05,8.88,11.63,12.93,14.15,14.73,15.30,15.60]; minf=0; for i=1:8 r(i)=x*exp(y/t(i))+z-r1(i); %构造最小二乘最优化的目标函数 minf=r(i)^2+minf; end %====================================== f1=diff(minf,x); f2=diff(minf,y); f3=diff(minf,z); %求目标函数的梯度 F=[f1,f2,f3]; %====================================== Fx1= -subs(F,{x,y,z},x0); Fx=Fx1/norm(Fx1); k=0; %====================================== %最速下降法核心迭代程序 while 1 x1=x0+a*Fx; P=subs(minf,{x,y,z},x1); xx1=xianxing(P); %调用线性搜索函数 al=huangjing(P,xx1); %调用黄金分割法函数； x0=x0+al*Fx; Fx1= -subs(F,{x,y,z},x0); Fx=Fx1/norm(Fx1); if norm(Fx1)<5e-4 sh=x0; return; end end %====================================== function xx=xianxing(Pa) %一维搜索法线性搜索函数 aa=findsym(Pa); a1=1; h=0.5; k=0; t1=2; while 1 a2=a1+h; Pa1=subs(Pa,aa,a1); Pa2=subs(Pa,aa,a2); if Pa2< Pa1 h=t1*h; a0=a1; a1=a2; k=k+1; if k>1000 disp('迭代步数太多，可能不收敛！'); end else if k==0 h=-h; a0=a2; else c1=min(a0,a2); d1=max(a0,a2); xx=[c1,d1]; return; end end end %====================================== function al1=huangjing(Pb,xx2) 二维铸造充型过程数值模拟的特征分数步长法? 鲁统超1，葛亮2 1山东大学数学与系统科学学院, （250100） 2 山东大学数学与系统科学学院, （250100） E-mail ：lutc@https://www.doczj.com/doc/bc17990045.html, 摘 要：铸造充型过程的数学模型是包括连续性方程和动量方程的偏微分方程组。本文利用分数步长法将动量方程分裂成两部分，对第一个方程采用特征差分法进行处理，对第二个方程结合连续性方程进行处理后得到压力的 泊松方程，用迭代法进行求解，给出了收敛性分析和稳定性条件。 关键词：分数步长；特征差分；收敛性；迭代。 1. 引 言 铸造生产的实质就是直接将液态金属浇入铸型并在铸型中凝固和冷却，进而得到铸件。液态金属的充型过程是铸件形成的第一个阶段。许多铸造缺陷(如卷气、夹渣、浇不足、冷隔及砂眼等)都是在充型不利的情况下产生的。因此，了解并控制充型过程是获得优质铸件的重要条件。但是，由于充型过程非常复杂，长期以来人们对充型过程的把握和控制主要是建立在大量实验基础上的经验准则。随着计算机的发展，铸件充型过程数值模拟才得到广泛应用。 充型过程流场数值模拟的主控方程均为非线性方程。其计算使用有限差分或有限元等数值方法求解质量守恒方程(连续性方程)和动量守恒 方程即Navier-Stokes 方程，以得出流体运动规律。在以前的研究中，Chorin(1968)和Temam(1969)分别独立的提出投影法。1972年由Minnesota 大学的Patankar 与Spalding 提出了simple 算法，这是一个压力修正算法，在以后的研究中又有simplec 方法,Raithby 提出的simplex 方法, Sheng 等提出的simplet 算法。 本文中利用分数步长法的思想将动量方程分裂成两部分，对第一个方程采用特征差分法求解，对第二个方程结合连续性方程进行处理后得到压力的 泊松方程，我们用迭代法进行求解，给出了收敛性分析和稳定性条件。 2. 问题的数学模型 铸造充型过程的模型主要由连续性方程和动量方程组成。 (a) 流体的动量方程 1x u p V u g u t x μρρ ??=???++???r " (2.1) ? 本课题得到教育部高等学校博士点基金资助，编号：20030422049 - 1 - 最速下降法与牛顿法及其区别 摘要：无约束优化方法是优化技术中极为重要和基本内容之一。它不仅可以直接用来求解无约束优化问题，而且很多约束优化问题也常将其转化为无约束优化问题，然后用无约束优化方法来求解。最速下降法和牛顿法是比较常见的求解无约束问题的最优化方法，这两种算法作为基本算法，在最优化方法中占有重要的地位。其中最速下降法又称梯度法，其优点是工作量少，存储变量较少，初始点要求不高；缺点是收敛慢，效率低。牛顿法的优点是收敛速度快；缺点是对初始点要求严格，方向构造困难，计算复杂且占用内存较大。同时，这两种算法的理论和方法渗透到许多方面，特别是在军事、经济、管理、生产过程自动化、工程设计和产品优化设计等方面都有着重要的应用。因此，研究最速下降法和牛顿法的原理及其算法对我们有着及其重要的意义。 关键字：无约束优化最速下降法牛顿法 Abstract: unconstrained optimization method is to optimize the technology is extremely important and basic content of. It not only can be directly used to solve unconstrained optimization problems, and a lot of constrained optimization problems are often transformed into unconstrained optimization problem, and then use the unconstrained optimization methods to solve. The steepest descent method and Newton-Raphson method is relatively common in the unconstrained problem optimization method, these two kinds of algorithm as the basic algorithm, the optimization method plays an important role in. One of the steepest descent method also known as gradient method, its advantages are less workload, storage variable is less, the initial requirements is not high; drawback is the slow convergence, low efficiency. Newtonian method has the advantages of fast convergence speed; drawback is the initial point of strict construction difficulties, directions, complicated calculation and larger memory. At the same time, these two kinds of algorithm theory and methods into many aspects, especially in the military, economic, management, production process automation, engineering design and product optimization design has important applications. Therefore, to study the steepest descent method and Newton-Raphson method principle and algorithm for us with its important significance. Keywords: unconstrained optimization steepest descent method 梯度法（又名,最速下降法） (该法总可以收敛，但是，在接近真解时收敛的速度会放慢。) 梯度法又称为最速下降法，用于求解实系数非线性方程组 12(,,,)0, 1,2,,i n f x x x i n == （7－15） 的一组根。梯度法首先是定义一个目标函数 2 12121 (,,,)(,,,) n n i n i x x x f x x x =Φ= ∑ （7－16） 使目标函数2 1 n i i f =Φ= ∑ 达到最小的12,,,n x x x 是我们寻找的一组解，这是非 线性最小二乘法问题。 如果第(0,1,2,)k k = 步求得一组解1 2 ,,,n k k k x x x ，使得 12(,,,)n k k k x x x ε Φ< （7－17） 则认为1 2 ,,,n k k k x x x 是原方程组满足一定精度的()ε要求的一组解。 梯度法的计算过程是： （1）先给定一组不全为零的初值1 2 000,,,n x x x ，第k 步的一组根为1 2 ,,,n k k k x x x ； （2）计算目标函数1 2 (,,,)n k k k x x x Φ 的值；(单独子程序:fn =TargetFunction) （3）若1 2 (,,,)n k k k x x x εΦ< ，则认为1 2 ,,,n k k k x x x 是满足一定精度()ε的一组 解，否则，作如下修正计算 1 α +=?Φ=-?i k i i k k k i i x x x x x （7－18） 其中 121212********* 1111222 (,,,) (,,,)(,,,)(,,,)(,,,)(,,,)(,,,)*,1,2,,α ==?Φ= ??? ??Φ ? ? ???Φ+-Φ?Φ=??Φ+-Φ?Φ= ?Φ+-Φ?Φ = ?==∑ n k j j n n n n n n k k k k n j j x x k k k k k k k k k k k k k k k k k k n n n k i i x x x x x h x x x x x x h x x h x x x x x h x x x h x x x x h h H x i n ??? ???? ??? ? ?????? （7－19） H 为控制收敛的常数，通常选为（10－5～10－6），收敛精度ε 选为（10－6～10 －8 ）。 （4）重复修正1 k i x +，直到 12111 (,,,)n k k k ε +++ΦΦΦ< ，计算终止。 牛顿法 迭代公式：(1)2()1()[()]()k k k k x x f x f x +-=-?? Matlab 代码： function [x1,k] =newton(x1,eps) hs=inline('(x-1)^4+y^2'); 写入函数 ezcontour(hs,[-10 10 -10 10]); 建立坐标系 hold on; 显示图像 syms x y 定义变量 f=(x-1)^4+y^2; 定义函数 grad1=jacobian(f,[x,y]); 求f 的一阶梯度 grad2=jacobian(grad1,[x,y]); 求f 的二阶梯度 k=0; 迭代初始值 while 1 循环 grad1z=subs(subs(grad1,x,x1(1)),y,x1(2)); 给f 一阶梯度赋初值 grad2z=subs(subs(grad2,x,x1(1)),y,x1(2)); 给f 二阶梯度赋初值 x2=x1-inv(grad2z)*(grad1z)'; 核心迭代公式 if norm(x1-x2) end end end 优点：在极小点附近收敛快 缺点：但是要计算目标函数的hesse 矩阵 最速下降法 1. ：选取初始点xo ，给定误差 2. 计算一阶梯度。若一阶梯度小于误差，停止迭代，输出 3. 取()()()k k p f x =? 4. 10 t ()(), 1.min k k k k k k k k k k t f x t p f x tp x x t p k k +≥+=+=+=+进行一维搜索，求，使得令转第二步 例题： 求min (x-2)^4+(x-2*y)^2.初始值（0,3）误差为0.1 (1)编写一个目标函数，存为f.m function z = f( x,y ) z=(x-2.0)^4+(x-2.0*y)^2; end (2)分别关于x 和y 求出一阶梯度，分别存为fx.m 和fy.m function z = fx( x,y ) z=2.0*x-4.0*y+4.0*(x-2.0)^3; end 和 function z = fy( x,y )最速下降法
最优化算法实验3-最速下降法
数值分析与算法变步长梯形求积法计算定积分
使用精确搜索算法确定步长的最速下降法
线性方程组的最速下降法与共轭梯度法
最速下降法
基于自适应步长的直线生成算法
用MATLAB实现最速下降法
最速下降法求解这一无约束的最优化问题
二维铸造充型过程数值模拟的特征分数步长法
最速下降法与牛顿法及其区别
非线性方程组-最速下降法(梯度法)
最优化牛顿法最速下降法共轭梯度法matlab代码
相关主题
文本预览