.
数学与计算科学学院
实验报告
实验项目名称使用精确搜索算法确定步长的最速下降法所属课程名称最优化方法
实验类型算法编程
实验日期 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++
【实验结论】
最小值：0.0006096631611
最优解时：x1=0.0329218107
X2=-0.008230452675
附录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的基本操作方法，了解加速步长法的原理与基本运用 最速下降法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. 实验结果分析 最速下降法 %% 最速下降法图示 % 设置步长为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/cf6040334.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/cf6040334.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/cf6040334.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 - 梯度法（又名,最速下降法） (该法总可以收敛，但是，在接近真解时收敛的速度会放慢。) 梯度法又称为最速下降法，用于求解实系数非线性方程组 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 ) 随着人工智能、模糊控制、模式识别、人工网络等新技术的应用和发 展。可以让它们与广义预测控制相结合，建立高精度、多模态的预测模型。 使广义预测控制在异常情况下可以稳定运行，推进广义预测控制的进一步 发展。 2.2.1最速下降法 最速下降法是无约束最优化中是比较有效的方法，它是以d}=一可(x})作为下 降方向的算法。其迭代格式为 xx+i=xx一。*Of (xk) 上式中，一般通过精确线搜索准则求得步长因子。*，当然也不排除可以利用非精确 线搜索准则来求得步长因子。*。不管最速下降法采取何种线搜索准则，它均具有全 局收敛性，但是这也不能直接就认为最速下降算法就是一个良好的优化算法。在实际 试验中，有很多优化问题利用最速下降法并不是下降的特快，反而下将的十分缓慢。 这是因为出现了锯齿现象:就是在计算过程中，最速下降法开始几步还是挺快的，但 是当目标函数f (x)的等高线接近于一个球的时候，就出现了类似锯齿现象，前进十 分缓慢，降低了算法的效能。 2.2.12.2.2 牛顿法 牛顿法也是无约束最优化问题中的一种经典算法，它是利用目标函数.f (x)的二 次泰勒展开式，并将二次泰勒展开式进行极小化。其迭代格式为 x}+}=xA十d} (2-5) 其中步长因子。、=l} d、为02f (x} )d + Of (xA ) = 0的解。当目标函数f(x)是正定二次函数的时候，牛顿法可以一步达到最优解;当目标函数f (x)是非二次函数的时候， 牛顿法经过有限次迭代之后就不能确保求得目标函数f (x)的最优解。我们知道目标 函数f (x)在极小点附近是很接近于二次函数的，所以，假如初始点非常靠近无约束 最优化问题((1-1)的最优解x的时候，并且}Z.f (x.)正定的时候，那么牛顿法就会有 很快的收敛速度，而由此算法产生的点列也具有了超线性收敛速度，同时还在一定条 件下具有二次收敛性;假如初始点与无约束最优化问题(1-1)的最优解x’相距比较 远的时候，这时的}Z.}(x})就不一定是正定的了，也就存在了一个问题，那就是此时 的牛顿方向就不一定是下降方向，有可能是上升方向，此时由此算法产生的点列可能 也就不收敛于无约束最优化问题((1-1)的最优解了。综上所述，让步长“R =1即“*恒 取常数是不合适的。经过研究学者们发现了一个方法可以改善这个情况，那就是利用 已有的线搜索方法来确定步长因子，也就是步长因子是可变的。其迭代格式为 x1. }, = x:一a}.OZ f (x}.)一，Of (x,. ) C 2-6 ) 2.2.2牛顿法 牛顿法也是无约束最优化问题中的一种经典算法，它是利用目标函数.f (x)的二 次泰勒展开式，并将二次泰勒展开式进行极小化。其迭代格式为 x}+i=xA+d}(2-5) 其中步长因子。、=l} d、为02f (x} )d + Of (xA ) = 0的解。当目标函数f(x)是正定二次函数的时候，牛顿法可以一步达到最优解;当目标函数f (x)是非二次函数的时候， 牛顿法经过有限次迭代之后就不能确保求得目标函数f (x)的最优解。我们知道目标 函数f (x)在极小点附近是很接近于二次函数的，所以，假如初始点非常靠近无约束 %利用wolf-powell线性搜索步长 function alpha1=wolfpowell(f,x,x0,d) g=jacobian(f,x); %求函数f的梯度 sigma1=0.25; %给定常数1 sigma2=0.7; %给定常数2 beta1=5; %步长初始值 theta1=0.5; %步长变化比例1 theta2=0.7; %步长变化比例2 %求步长alpha1 if subs(f,x,x0+d)<=subs(f,x,x0)+sigma1*subs(g,x,x0)*d'&&subs(g,x,x0+d)*d'>=sigm a2*subs(g,x,x0)*d' alpha1=1; %满足第一个条件的最大步长 else alpha1=beta1; while subs(f,x,x0+alpha1*d)>subs(f,x,x0)+sigma1*alpha1*subs(g,x,x0)*d' alpha1=theta1*alpha1; end while subs(f,x,x0+alpha1/theta1*d)<=subs(f,x,x0)+sigma1*alpha1/theta1*subs(g,x,x0)*d' alpha1=alpha1/theta1; end end %使步长满足第二个条件 while subs(g,x,x0+alpha1*d)*d' 微分方程数值解 姓名： 班级： 一．二维抛物方程分布步长法 实验用的二维热传导 是方程是： 22(,,)sin()sin()0,1,0t u x y t x y e x y t πππ-=<<> 它满足书中 0,,0(,,0)(,)(0.,)(,,)(,0.)(,.)0l xx yy u u u x y l t u x y x y u y t u l y t u x t u x l t ?=+<<>?? =??====? 的要求，这里1l =。以0t =为初始时刻，分别用ADI,LOD,对称LOD （记为symLOD ）进行算法设计，求在时刻1t =的数值解，并与精确解做比较。 实验过程： 1.t=1时刻原始图像 当x,y 方向上的网格数是160，时间t 方向上的网格数是40时，t=1时刻的原始图像为 2．ADI法恢复的图像 当x,y 方向上的网格数是160，时间t方向上的网格数是40时，ADI法所绘t=1时刻图像为 3．LOD法恢复图像 当x,y 方向上的网格数是160，时间t方向上的网格数是40时，LOD法所绘t=1时刻图像为 4．对称LOD法（记为symLOD）恢复图像 当x,y 方向上的网格数是160，时间t方向上的网格数是40时，symLOD法所绘t=1时刻图像为 5.x,y方向上的网格数和误差关系 t=40固定,x,y方向的的网格数分别取[10,50,100,250,500] 三者的误差的二范数分别为（见error2.m） ADI=[8.730504221745552e-010, 6.029451734592973e-009, 1.265923756496139e-008, 3.206705449439820e-008, 6.425372124435197e-008]; LOD=[8.730504221745788e-010, 6.029451734600921e-009, 1.265923756507861e-008, 3.206705449886893e-008, 6.425372131563230e-008]; SymLOD=[8.730502288715592e-010, 6.029452708815150e-009, 1.265923951388676e-008, 3.206705936704847e-008, 6.425373098974900e-008]; Richardson 外推加速法在数值微分与积分 中的应用 信息与计算科学专业学生：XX 指导老师：XX [摘要]：本文介绍了数值微分与数值积分的Richardson 外推加速算法，基于Euler-Maclaurin 公式给出了算法的推导过程，再根据Richardson 外推方法推导出了收敛更快的数值微分与积分公式，经数值实验验证该公式有良好的计算效果. 关键词：Richardson 外推法，Romberg 算法,Euler-Maclaurin 公式 Abstract: the paper gives a introduction of Richardson ’s Extrapolation Method, then, listing the derivation and proof of Richardson ’s Extrapolation depending on Euler-Maclaurin. According to the Richardson ’s Extrapolaton,this paper got the faster numerical differentiation and integral formula.The formula is prove to be efficient by numerical experiment. Keyword: Richardson’s Extrapolation, Romberg’s Algoritm, Euler-Maclaurin Algoritm 0 引言： Richardson 外推法用以低阶公式产生高精度收敛效果进而改善序列收敛效率，它是 在20世纪前期由英国数学家，物理学家，气象学家Lewis Fry Richardson 提出的.在数值分析领域，Richardson 外推法有很多实际应用，如隆贝格积分方法，是在梯形公式的基础上应用Richardson 外推法导出的；还有用于求解常微分方程的Bulirsch –Stoer 算法. 1 Richardson 外推加速算法 1.1 Richardson 外推加速算法 李查逊外推加速法基于如下原理 定理 设: ()[]b a C x f ,∞∈ ，则成立最优化算法实验3-最速下降法
数值分析与算法变步长梯形求积法计算定积分
使用精确搜索算法确定步长的最速下降法
最速下降法
基于自适应步长的直线生成算法
用MATLAB实现最速下降法
最速下降法求解这一无约束的最优化问题
二维铸造充型过程数值模拟的特征分数步长法
非线性方程组-最速下降法(梯度法)
最优化牛顿法最速下降法共轭梯度法matlab代码
最速下降法
wolf-powell算法搜索步长
分步步长法和多重网格法_实验
【精品】Richardson外推加速算法在数值分析公式中的应用
相关主题
文本预览