最优化课程设计--共轭梯度法算法分析与实现(设计程序) 题目共轭梯度法算法分析与实现 班级 / 学号 14140101/2011041401011 学生姓名黄中武指导教师王吉波王微微 课程设计任务书 课程名称最优化方法课程设计院(系) 理学院专业信息与计算科学 课程设计题目共轭梯度法算法分析与实现课程设计时间: 2014 年 6月 16日至 2014 年 6月 27日 课程设计的要求及内容: [要求] 1. 学习态度要认真，要积极参与课程设计，锻炼独立思考能力; 2. 严格遵守上机时间安排; 3. 按照MATLAB编程训练的任务要求来编写程序; 4. 根据任务书来完成课程设计论文; 5. 报告书写格式要求按照沈阳航空航天大学“课程设计报告撰写规范”; 6. 报告上交时间:课程设计结束时上交报告; 7. 严禁抄袭行为，一旦发现，课程设计成绩为不及格。 一、运用共轭梯度法求解无约束最优化问题 要求:1)了解求解无约束最优化问题的共轭梯度法; 2)绘出程序流程图; 3)编写求解无约束最优化问题的共轭梯度法MATLAB程序; 4)利用编写文件求解某无约束最优化问题;
5)给出程序注释。 指导教师年月日 负责教师年月日 学生签字年月日 沈阳航空航天大学 课程设计成绩评定单 课程名称最优化理论与算法课程设计院(系) 理学院专业信息与计算科学课程设计题目共轭梯度法算法分析与实现学号 2011041401011 姓名黄中武指导教师评语: 课程设计成绩 指导教师签字 年月日 最优化方法课程设计沈阳航空航天大学课程设计用纸目录 目录 一、正 文 (1) 二、总结 ............................................................... 8 参考文 献 ............................................................... 9 附录 .. (10) 第 I 页 最优化方法课程设计沈阳航空航天大学课程设计用纸正文 一、正文 一无约束最优化问题的共轭梯度法
function iteration A=[10,1,2,3,4; 1,9,-1,2,-3; 2,-1,7,3,-5; 3,2,3,12,-1; 4,-3,-5,-1,15]; b=[12,-27,14,-17,12]'; x0=[0,0,0,0,0]'; tol=1e-12; disp('jacobi迭代法的结果和次数如下:') [x,k]=Fjacobi(A,b,x0,tol) disp('G-S迭代法的结果和次数如下:':') [x,k]=Fgseid(A,b,x0,tol) disp('超松弛的结果和次数如下:':') [x,k]=Fsor(A,b,x0,1.2,tol) disp('共轭梯度法的结果和次数如下:':') [x,k]=Fcg(A,b,x0,tol) %jacobi迭代法 function [x,k]=Fjacobi(A,b,x0,tol) max=300; D=diag(diag(A)); L=-tril(A,-1); U=-triu(A,1); B=D\(L+U); f=D\b; x=B*x0+f; k=1; while norm(x-x0)>=tol x0=x; x=B*x0+f; k=k+1; if(k>=max) disp('μü′ú3?1y300′?￡?·?3ì×é?é?ü2?ê?á2'); return; end end %G-S迭代法 function [x,k]=Fgseid(A,b,x0,tol) max=300; D=diag(diag(A)); L=-tril(A,-1); U=-triu(A,1); G=(D-L)\U; f=(D-L)\b; x=G*x0+f; k=1; while norm(x-x0)>=tol x0=x; x=G*x0+f; k=k+1; if(k>=max) disp('μü′ú3?1y300′?￡?·?3ì×é?é?ü2?ê?á2'); return; end
偏微分方程数值解 （Numerical Methods for Partial Differential Equations） 课程代码：10210801 学位课程/非学位课程：非学位课程 学时/学分：46/3 课程简介： 《偏微分方程数值解》是数学类专业必修的一门专业课。主要内容包括：变分形式和Galerkin有限元法、椭圆型方程的差分方法、抛物型方程的差分方法、双曲型方程的差分方法、离散方程的解法。通过本课程的学习，使学生掌握求解偏微分方程数值解的基本方法，能够根据具体的微分方程使用合适的计算方法。 一、教学目标 1、知识水平教学目标 偏微分方程数值解课程的教学，要使学生掌握椭圆型微分方程、抛物型微分方程、双曲型微分方程等典型方程的差分方法，了解与之相关的理论问题，理解变分原理、有限元方法以及离散方程的解法，理解各种计算方法的收敛条件和收敛速度。 2、能力培养目标 通过偏微分方程数值解课程教学,应注意培养学生以下能力： （1）连续问题离散化能力——掌握科学的思维方法，能够使用差分方法和有限元方法的各种格式对三类典型方程进行离散化处理。 （2）算法分析与设计能力——结合各类偏微分方程的特点，设计各种计算方法，对计算方法的收敛条件和收敛速度等进行分析，具体设计易于上机实现的算法。（3）离散方程组的快速求解能力——理解离散方程组的特点，使用数学软件编程，具体上机实现，进行数值模拟的动手能力。 3、素质培养目标 通过数学物理方程课程教学,应注重培养学生以下素质： （1）具体问题有限化——善于对现实世界中得到的偏微分方程进行有限差分、有限元分析的有限化思想素养。 （2）数值解法定性化——通过学习，引导学生树立偏微分方程数值求解的基本原则，培养学生对数值方法中的稳定性、收敛性和误差等进行定性分析的素质。（3）算法实现程序化——培养学生的创造性和具体实现程序化的思维，使学生学会用数学中算法的观点思考实际问题，用程序和计算机解决数学问题。 二、教学重点与难点 1、教学重点：椭圆型、抛物型、双曲型等微分方程的差分方法，有限元方法。 2、教学难点：各种计算方法的稳定性、收敛性和误差分析，变分形式。 三、教学方法与手段 以教师讲授为主，安排上机实验，辅以习题课、课堂讨论、小论文，注重理论联系实际。 四、教学内容与目标 教学内容教学目标课时分配 （46学时） 1. 边值问题的变分形式 6 二次函数的极值掌握 两点边值问题掌握
共轭梯度法 1.算法思想： 共轭梯度法是利用目标函数梯度逐步产生共轭方向作为线搜索方向的方法，每次搜索方向都是在目标函数梯度的共轭方向，搜索步长通过一维极值算法确定。 2.算法步骤： 用共轭梯度法求无约束多维极值问题min (),n f x x R ∈的算法步骤如下： （1） 给定初始点(0)x ，及精度0ε>； （2） 若 (0)()f x ε ?≤，停止，极小值点为(0)x ，否则转步骤（3）； （3） 取(0)(0)()p f x =-?，且置0k =； （4） 用一维搜索法求k t ，使得()()()()()0 ()min k k k k k t f x t p f x tp ≥+=+，令，(1)()()k k k k x x t p +=+，转步骤5； （5） 若 (1)()k f x ε +?≤，停止，极小值点为(1)k x +，否则转步骤（6）； （6） 若1k n +=，令(0)()n x x =，转步骤（3），否则转步骤（7）； （7） 令(1)(1)()()k k k k p f x p λ++=-?+，2(1)2 () () () k k k f x f x λ+?=?，置1k k =+，转 步骤（4）。 3.算法源程序： #include
#define N 10 #define eps pow(10,-6) double f(double x[],double p[],double t) { double s; s=pow(x[0]+t*p[0],2)+25*pow(x[1]+t*p[1],2); return s; } /*以下是进退法搜索区间源程序*/ void sb(double *a,double *b,double x[],double p[]) { double t0,t1,t,h,alpha,f0,f1; int k=0; t0=2.5; /*初始值*/ h=1; /*初始步长*/ alpha=2; /*加步系数*/ f0=f(x,p,t0); t1=t0+h; f1=f(x,p,t1); while(1) {
超松弛迭代法如何选取最佳松弛因子 船建学院B1301095 wj 一、课题背景 逐次超松弛迭代法是Gauss-Seidel方法的一种加速方法，是解大型稀疏矩阵方程组的有效方法之一，它具有计算公式简单，程序设计容易，占用计算机内存较少等优点，但需要选择好的加速因子（即最佳松弛因子）。 最佳松弛因子ω的确定是数值代数中的一个理论难题，对于不同的矩阵，其最佳松弛因子往往相差很大，没有统一的计算公式来确定ω。由于对称正定矩阵sor方法收敛的充分必要条件为w在0到2之间，故利用对称正定矩阵一定收敛的性质，本文提供一种针对于系数矩阵为对称正定矩阵时，如何选取合适的最佳松弛因子的方法。 二、课题研究流程图 三、SOR迭代公式 逐次超松弛(Successive Over Relaxation)迭代法，简称SOR迭代法，它是在GS法基础上为提高收敛速度，采用加权平均而得到的新算法，设解方程的GS法记为 (1)
再由与加权平均得 这里ω＞0称为松弛参数，将（1）式代入则得 (2) 称为SOR迭代法，[WTBX]ω＞0称为松弛因子，当ω=1时(2)式即为GS法，将(2)式写成矩阵形式，则得 即 于是得SOR迭代的矩阵表示 (3) 四、Matlab程序 %sor法确定对称正定矩阵的最佳松弛因子w% clc;clear; n=100; %矩阵的阶数% for num=1:100 X=diag(rand(n,1)); U=orth(rand(n,n)-0.5); a=U'*X*U; %以上是利用随机对角矩阵和随机正交矩阵，产生随机的对称正定矩阵，正交变化不改变特征值% L=zeros(n,n); U=zeros(n,n); %分配L和U的内存空间% step=0.02; %定义w的计算精度% for k=1:(2/step) %由于对称正定矩阵sor方法收敛的充分必要条件为w在0到2之间% w=(k-1)*step; for i=1:n %一个总的for循环给三个矩阵赋值D-L-U=A,% for j=1:i-1 L(i,j)=-a(i,j);%L矩阵的赋值% end for j=i+1:n U(i,j)=-a(i,j);%U矩阵的赋值% end D(i,i)=a(i,i);%D矩阵的赋值% end
#include printf("\n"); printf("input the Maxtr X\n"); /*给X0输入一个初始向量*/ for(i=0;i 高等数值计算实践题目一 1. 实践目的 本次计算实践主要是在掌握共轭梯度法，Lanczos 算法与MINRES 算法的基础上，进一步探讨这3种算法的数值性质，主要研究特征值特征向量对算法收敛性的影响。 2. 实践过程 （一）生成矩阵 （1）作5个100阶对角阵i D 如下： 1D 对角元：1,1,...,20,1+0.1(-20),21,...,100j j d j d j j ==== 2D 对角元：1,1,...,20,1+(-20),21,...,100j j d j d j j ==== 3D 对角元：,1,...,80,81,81,...,100j j d j j d j ==== 4D 对角元：,1,...,40,41,41,...,60,41+(60),61,...,100j j j d j j d j d j j =====-= 5D 对角元：,1,...,100j d j j == 记i D 的最大模特征值和最小模特征值分别为1i λ和i n λ，则i D 特征值分布有如下特点： 1D 的特征值有较多接近于i n λ，并且1/i i n λλ较小， 2D 的特征值有较多接近于i n λ，并且1/i i n λλ较大， 3D 的特征值有较多接近于1i λ，并且1/i i n λλ较大， 4D 的特征值有较多接近于中间模特征值，并且1/i i n λλ较大， 5D 的特征值均匀分布，并且1/i i n λλ较大 （2）随机生成10个100阶矩阵j M ： (100(100))j M fix rand = 并作它们的QR 分解，得j Q 和j R ，这样可得50个对称的矩阵T ij j i j A Q DQ =，其中i D 的对角元就是ij A 的特征值，若它们都大于0，则ij A 正定，j Q 的列就是相应的特征向量。结合（1）可知，ij A 都是对称正定阵。 一、共轭梯度法 共轭梯度法（Conjugate Gradient）是共轭方向法的一种，因为在该方向法中每一个共轭向量都是依靠赖于迭代点处的负梯度而构造出来的，所以称为共轭梯度法。由于此法最先由Fletcher和Reeves （1964）提出了解非线性最优化问题的，因而又称为FR 共轭梯度法。由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用于实际问题中。共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些搜索方向d仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方便，效果好。 二、共轭梯度法的原理 设有目标函数 f（X）=1/2X T HX+b T X+c 式1 式中，H作为f（X）的二阶导数矩阵，b为常数矢量，b=[b1,b2,b3,...b n]T 在第k次迭代计算中，从点X（k）出发，沿负梯度方向作一维搜索，得 S(K)=-?f（X（k））式2 X(k+1)=X(k)+ɑ(k)S(k) 式3 在式中，ɑ（k）为最优步长。 设与S(k）共轭的下一个方向S(k+1)由点S(k）和点X(k+1)负梯度的线性组 合构，即 S (k+1)=-?f （X （k+1））+β(k)S (k) 式4 根据共轭的条件有 [S (k)]T ?2f （X (k)）S (k+1)=0 式5 把式2和式4带入式5，得 -[?f(X (k))]T ?2f （X (k)）[-?f （X （k+1））+β(k)S (k) ]=0 式6 对于式1，则在点X (k)和点X (k+1)的梯度可写为 ?f(X (k))=HX (k)+b 式7 ?f （X （k+1）)=HX (k+1)+b 式8 把上面两式相减并将式3代入得 ɑ(k)H S (k)=?f （X （k+1）)-?f(X (k)) 式9 将式4和式9两边分别相乘，并代入式5得 -[?f （X （k+1）)+β(k)?f(X (k))]T [?f （X （k+1）)-?f(X (k)]=0 式10 将式10展开，并注意到相邻两点梯度间的正交关系，整理后得 β （k ） =2 2 ||))((||||))1((||k X f k X f ?+? 式11 把式11代入式4和式3，得 S （k+1）=-?f （X (k)）+β （k ） S （k ） X (k+1)=X （k ）+ɑ（k ）S （k ） 由上可见，只要利用相邻两点的梯度就可以构造一个共轭方向。以这种方式产生共轭方向并进行迭代运算的方法，即共轭梯度法。 最优化方法第四次作业 题目：利用FR-共轭梯度法求解无约束优化问题222 12122min ()44412x R f x x x x x x ∈=+--。初始点(0)(0.5,1).T x =- () ()T k k T k k k k k k k g g g g k d g k g d 111110.0,;0,-----=???≥+-=-=ββ 一、程序 function [x,val,k]=frcg(fun,gfun,x0) %功能：用FR 共轭梯度法求解无约束问题min f （x ） %输入：x0是初始点，fun,gfun 分别是求目标函数和梯度 %输出：x,val 分别是近似最优点和最优值，k 是迭代次数 maxk=5000; rho=0.6; sigma=0.4; k=0; epsilon=1e-4; n=length(x0); while (k while (m<20) %用Armijo 搜索求步长 if (feval(fun,x0+rho^m*d) 车辆薄板有限元分析中的多因子不完全分解 预处理解法 姚 松 田红旗 1中南大学轨道交通安全教育部重点实验室，湖南长沙，410075 dynacn@https://www.doczj.com/doc/e416303430.html, 摘要：薄板是轨道车辆结构的主要形式，本文基于离散Kirchhoff 假设的DKT 弯曲板单元推导了四边形弯曲板单元DKQ 的构造过程，并进一步阐述了用于一般薄板问题分析的平板单元的构造。提出了一种“多因子不完全分解” 的预处理方法，与共轭梯度迭代法结合能够大大加快薄板问题大型稀疏方程组的收敛速度，经过数值试验，说明该方法是稳定可靠的。该方法避免了常规不完全分解不适用于薄板这样的 “病态”结构的情况。在此基础上，编写了一般薄板问题分析的有限元程序，程序对结构刚度矩阵采用压缩存贮的方法，节约了大量内存空间。本文还对分解算法中的可选参数进行了优化研究。通过一个数值试验，本程序计算结果与商业有限元软件ANSYS5.7的结果完全一致。 关键词：薄板结构，DKQ 单元，预处理，不完全分解，共轭梯度法 1 概 述 有限元单元法已经成为结构分析的重要方法，薄板结构是轨道车辆的主要结构形式，因此薄板结构有限元分析已成为车辆结构分析中的重大课题。早期的弯曲板单元大多基于经典的薄板理论，在以该理论为基础的板单元的能量泛函中，包含位移的二阶偏导数，要求位移为类连续。这给构造板单元带来了困难，由此研究人员将注意力转向了中厚板单元，大多采用中厚板理论，其能量泛函仅包含位移的一阶导数，只要求位移是类连续，但是用厚板理论建立的单元仅对中厚板有效，当板逐渐变薄时，单元刚度矩阵中的剪切项占主导地位，计算出的弯曲变形远小于实际变形；当板非常薄时，求得的位移趋向于零，从而产生了“剪切闭锁”现象。 1C issner Mindlin Re ?0C 基于离散的假设， 通过挠度和转角分别独立插值，然后在若干个离散点上强迫挠度与转角满足薄板经典理论中的约束，构造出三角形（DKT ）和四边形（DKQ ）薄板弯曲单元，其泛函的表达式又回复为经典薄板理论的泛函表达式，又自然解决了“剪切闭锁现象”问题。多个文献表明DKT 元与DKQ 元在求解薄板弯曲问题时都显示出良好的性能，具有较高的精度。在对实际车辆结构进行有限元分析时，由于结构受力复杂，在承受板平面内的载荷的同时，也有可能板平面外的载荷，因此在进行分析时所采用的平板单元是平面应力单元与DKT 弯曲单元的组合而成。由于三角形平面应力单元为常应变单元，为了提高分析的精度，在本文中我们讨论由四边形膜单元和DKQ 单元组合而成的平板单元。 Kirchhoff Kirchhoff 1 教育部博士点基金（20020533007）项目资助 1https://www.doczj.com/doc/e416303430.html, 编号:_ 09 《最优化方法》 课程设计 题目：共轭梯度算法分析与实现 院系：数学与计算科学学院 专业：数学与应用数学 姓名学号： 指导教师： 日期：2013 年12 月23 日 摘要 在最优化计算中，共轭梯度法是非常重要的一种方法。共轭梯度法是一种改进的最速下降法，介于最速下降法与牛顿法之间的一种无约束优化算法,是为求解目标函数为二次函数的问题而设计的一类算法。它利用目标函数的梯度逐步产生共轭方向并将其作为搜索方向的方法，收敛速度快。共轭梯度法仅需利用一阶导数信息，避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，具有二次终止性。 关键词：共轭梯度法；牛顿法；二次函数；无约束优化 Abstract In the calculation of optimization method, conjugate gradient method is a very important one. The conjugate gradient method is a unconstrained optimization method between the steepest descent method and Newton method, and sove the objective function for the original quadratic function problems and design for a class of algorithm. Conjugate gradient method using only first derivative information, to avoid the Newton method requires storage and computing the inverse Hesse matrix and shortcomings, this method has the quadratic termination. Keywords: Conjugate gradient method; Newton method;Unconstrained optimization 最优化课程设计--共轭梯度法算法分析与实现 (设计程序) 题目共轭梯度法算法分析与实现 班级 / 学号 14140101/11 学生姓名黄中武指导教师王吉波王微微 课程设计任务书 课程名称最优化方法课程设计院(系) 理学院专业信息与计算科学 课程设计题目共轭梯度法算法分析与实现课程设计时间: 2014 年 6月 16日至2014 年 6月 27日 课程设计的要求及容: [要求] 1. 学习态度要认真，要积极参与课程设计，锻炼独立思考能力; 2. 严格遵守上机时间安排; 3. 按照MATLAB编程训练的任务要求来编写程序; 4. 根据任务书来完成课程设计论文; 5. 报告书写格式要求按照航空航天大学“课程设计报告撰写规”; 6. 报告上交时间:课程设计结束时上交报告; 7. 严禁抄袭行为，一旦发现，课程设计成绩为不及格。 一、运用共轭梯度法求解无约束最优化问题 要求:1)了解求解无约束最优化问题的共轭梯度法; 2)绘出程序流程图; 3)编写求解无约束最优化问题的共轭梯度法MATLAB程序; 4)利用编写文件求解某无约束最优化问题; 5)给出程序注释。 指导教师年月日 负责教师年月日 学生签字年月日 航空航天大学 课程设计成绩评定单 课程名称最优化理论与算法课程设计院(系) 理学院专业信息与计算科学课程设计题目共轭梯度法算法分析与实现学号 11 黄中武指导教师评语: 课程设计成绩 指导教师签字 年月日 最优化方法课程设计航空航天大学课程设计用纸目录 目录 一、正文 ............................................................... 1 二、总 结 ............................................................... 8 参考文 献 ............................................................... 9 附 录 (10) 第 I 页 最优化方法课程设计航空航天大学课程设计用纸正文 一、正文 一无约束最优化问题的共轭梯度法 共轭梯度法最初是由Hesteness和Stiefel于1952年为求解线形方程组而提出的。后来，人们把这种方法用于求解无约束最优化问题，使之成为一种重要的最优化方法。 下面，重点介绍Fletcher-Reeves共轭梯度法，简称FR法。 万方数据 万方数据 大型复线性方程组预处理双共轭梯度法 作者：张永杰， 孙秦， ZHANG Yong-jie， SUN Qin 作者单位：西北工业大学航空学院,西安,710072 刊名： 计算机工程与应用 英文刊名：COMPUTER ENGINEERING AND APPLICATIONS 年，卷(期)：2007,43(36) 被引用次数：1次 参考文献(6条) 1.Wu J P;Wang z H;Li X M High-performanco solution and paral lel computation of sparse linear equations 2004 2.Xu S F Theories and Methods on matrix computations 1995 3.Jin J M The finite element method in electromagneties 2002 4.Zhang Yongjie;Sun Qin A new ICCG method of large scale sparse linear equations[期刊论文]-Journal on Numerical Methods and Computer Applications 2007(02) 5.Betmmens Robert Itemtive solution methods 2004 6.Wu J P;Wang Z H Problems and improvements to the incomplete Cholesky decomposition with thresholds [期刊论文]-Journal on Numerical Methods and Computer Applications 2003(03) 引证文献(1条) 1.明星.苑秉成.刘建国基于共轭梯度的宽带相关处理快速算法[期刊论文]-系统工程与电子技术 2010(12) 本文链接：https://www.doczj.com/doc/e416303430.html,/Periodical_jsjgcyyy200736007.aspx 竭诚为您提供优质文档/双击可除 共轭梯度实验报告 篇一：共轭梯度法实验报告 数值代数实验报告 一、实验名称：用共轭梯度法解线性方程组。 二、实验目的：进一步熟悉理解掌握共轭梯度法解法思路，提高matlab编程能力。三、实验要求：已知线性方程 矩阵，应用共轭梯度法在相关软件编程求解线性方程组的解。 四、实验原理： 1．共轭梯度法： 考虑线性方程组 Ax?b 的求解问题，其中A是给定的n阶对称正定矩阵，b是 给定的n维向量，x是待求解的n维向量.为此,定义二次泛 函 ?(x)?xTAx?2bTx. 定理1设A对称正定,求方程组Ax?b的解，等价于求二次泛函?(x)的极小值点.定理1表明，求解线性方程组问题 就转化为求二次泛函?(x)的极小值点问题.求解二次函数极 小值问题，通常好像盲人下山那样，先给定一个初始向量x0，确定一个下山方向p0，沿着经过点x0而方向为p0的直线 x?x0??p0找一个点 x1?x0??0p0， 使得对所有实数?有 ??x0??0p0????x0??p0?， 即在这条直线上x1使?(x)达到极小.然后从x1出发， 再确定一个下山的方向p1，沿着直 线x?x1??p1再跨出一步，即找到?1使得??x?在 x2?x1??1p1达到极小： ??x1??1p1????x1??p1?. 重复此步骤，得到一串 ?0,?1,?2, x?xk??pk上确定步长?k使 和p0,p1,p2, ， 称pk为搜索方向，?k为步长.一般情况下，先在xk点 找下山方向pk，再在直线 ??xk??kpk????xk??pk?, 最后求出xk?1?xk??kpk.然而对不同的搜索方向和步长，得到各种不同的算法. 油藏数值模拟技术现状与发展趋势 摘要：介绍了当前国内外油藏数值模拟的现状，简述了并行算法、网格技术、粗化技术、数值解法、动态油藏模型建立、动态跟踪模拟及三维显示等技术，指出了数值模拟的发展趋势。 关键词：并行算法；网格技术；网格粗化；分阶段模拟；动态跟踪模拟；数值解法 引言 近年来，随着计算机、应用数学和油藏工程学科的不断发展，油藏数值模拟方法得到不断的改进和广泛应用。通过数值模拟可以搞清油藏中流体的流动规律、驱油机理及剩余油的空间分布；研究合理的开发方案，选择最佳的开采参数,以最少的投资,最科学的开采方式而获得最高采收率及最大经济效益[1]。经过几十年的发展,该技术不断成熟和完善并呈现出一些新的特点。 1 国内外现状 1.1 并行算法 并行算法是一些可同时执行的诸进程的集合这些进程互相作用和协调动作从而达到给定问题的求解[2]。并行算法首先需合理地划分模块,其次要保证对各模块的正确计算,再次为各模块间通讯安排合理的结构,最后保证各模块计算的综合效果并行机及并行软件的开发和应用将极大地提高运算速度,以满足网格节点不断增多的油藏数值模型。在并行计算机上使用并行数值解法是提高求解偏微分方程的计算速度,缩短计算时间的一个重要途径[3,4]。在共享内存的并行机上把一个按向量处理的通用油藏模拟器改写成并行处理是容易的,但硬件扩充难；分布内存并行机编程较共享式并行机困难,但硬件扩充容易,关键是搞好超大型线形代数方程组求解的并行化。并行部分包括输入输出、节点物性、构造矩阵、节点流动及井筒等。 1.2 网格技术 为了模拟各种复杂的油藏、砂体边界或断层渗透率在垂向或水平方向的各向异性,以及近井地区的高速、高压力梯度的渗流状态,近年来在国外普遍发展了各种类型的局部网格加密及灵巧的网格技术。这种系统大体可以分为二类：一类称控制体积有限元网格(CVFE),这是将油藏按一定规则剖分为若干个三角形以后,把三角形的中心和各边的中点连接起来所形成的网格。另一类则称垂直等分线排比网格(PEBI),其剖分方法是将油藏分成若干三角形后,使三角形各边的垂直等分线相交而形成网格。这些方法在处理复杂几何形状油藏及进行局部网格加密时简单而一致。在多相流情况下,参照某一给定的几何准则时该方法是单调的,这保证了其稳定性和收敛性。这两种方法都能以直观的控制体积的概念出发并且采用一致的上游权而推导得出这些方法对网格的方向不敏感,在某些情况下比九点差分格式的效果好。 1.3 计算机辅助历史拟合技术 最速下降法and 共轭梯度法 分类：matlab 2011-04-17 17:02 961人阅读评论(2) 收藏举报算法出版优化 注明：程序中调用的函数jintuifa.m golddiv.m我在之前的笔记中已贴出 最速下降法 %最速下降法求解f = 1/2*x1*x1+9/2*x2*x2的最小值，起始点为x0=[9 1] %算法根据最优化方法（天津大学出版社）97页算法3.2.1编写 %v1.0 author: liuxi BIT %format long syms x1 x2 alpha; f = 1/2*x1*x1+9/2*x2*x2;%要最小化的函数 df=jacobian(f,[x1 x2]);%函数f的偏导 epsilon=1e-6;%0.000001k=0; x0=[9 1];%起始点 xk=x0; gk=subs(df,[x1 x2],xk);%起始点的梯度 gk=double(gk); while(norm(gk)>epsilon)%迭代终止条件||gk||<=epsilon pk=-gk;%负梯度方向 f_alpha=subs(f,[x1 x2],xk+alpha*pk);%关于alpha的函数 [left right] = jintuifa(f_alpha,alpha);%进退法求下单峰区间 [best_alpha best_f_alpha]=golddiv(f_alpha,alpha,left,right);%黄金分割法求最优步长xk=xk+best_alpha*pk; k=k+1; gk=subs(df,[x1 x2],xk); gk=double(gk); end best_x=xk;%最优点 best_fx=subs(f,[x1 x2],best_x);%最优值 共轭梯度法 最速下降法 最速下降法又称为梯度法，是1847 年由著名数学家Cauchy 给出的，它是解析法中最古老的一种，其他解析方法或是它的变形，或是受它的启发而得到的，因此它是最优化方法的基础。作为一种基本的算法，他在最优化方法中占有重要地位。其优点是工作量少，存储变量较少，初始点要求不高；缺点是收敛慢，效率不高，有时达不到最优解。非线性规划研究的对象是非线性函数的数值最优化问题。它的理论和方法渗透到许多方面，特别是在军事、经济、管理、生产过程自动化、工程设计和产品优化设计等方面都有着重要的应用。而最速下降法正是n元函数的无约束非线性规划问题min f (x)的一种重要解析法，研究最速下降法原理及其算法实现对我们有着极其重要的意义。 最速下降法 1.最速下降方向 函数f(x)在点x处沿方向d的变化率可用方向导数来表示。对于可微函数，方向导数等于梯度与方向的内积，即： Df(x;d) = ▽f(x)Td, 因此，求函数f(x)在点x处的下降最快的方向，可归结为求解下列非线性规划：min ▽f(x)Td s.t. ||d|| ≤ 1 当 d = -▽f(x) / ||▽f(x)|| 时等号成立。因此，在点x处沿上式所定义的方向变化率最小，即负梯度方向为最速下降方向。 2.最速下降算法 最速下降法的迭代公式是 x(k+1) = x(k) + λkd(k) , 其中d(k)是从x(k)出发的搜索方向，这里取在x(k)处的最速下降方向，即 d = -▽f(x(k)). λk是从x(k)出发沿方向d(k)进行一维搜索的步长，即λk满足 f(x(k) + λkd(k)) = min f(x(k)+λd(k)) (λ≥0). 计算步骤如下： (1)给定初点x(1) ∈ Rn，允许误差ε> 0，置k = 1。 (2)计算搜索方向d = -▽f(x(k))。 (3)若||d(k)|| ≤ε，则停止计算；否则，从x(k)出发，沿d(k)进行一维搜索，求λk，使 f(x(k) + λkd(k)) = min f(x(k)+λd(k)) (λ≥0). (4)令x(k+1) = x(k) + λkd(k) ，置k = k + 1，转步骤(2)。 https://www.doczj.com/doc/e416303430.html,/yangxi/archive/2011/10/20/2219408.html 梯度下降法 牛顿法 迭代公式：(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 ) 共轭梯度法及其基本性质 预备知识 定义1 设是对称正定矩阵。称是A-共轭的，是指 性质1 设有是彼此共轭的维向量，即 则一定是线性无关的。 ［证明］若有一组数满足 则对一切一定有 注意到，由此得出：即所有的＝０．因此， 是线性无关的． 性质２设向量是线性无关的向量组，则可通过它们的线性组合得出一组向量，而是两两共轭的． ［证明］我们用构造法来证实上面的结论． Ｓ０：取； Ｓ１：令，取． …… Ｓm：令 取 容易验证：符合性质２的要求． 性质３设是两两Ａ－共轭的，是任意指定的向量，那么从出发，逐次沿方向搜索求的极小值，所得序列，满足： ． ［证明］由下山算法可知，从出发，沿方向搜索，获得 从而 性质４设是两两Ａ共轭的，则从任意指定的出发，依次沿搜索，所得序列满足： （１） （２），其中是方程组(5.1.1)的解． ［证明］（１）是性质３的直接推论，显然成立． （２）由于是两两Ａ共轭的，故是线性无关的．所以对于向量可用线性表出，即存在一组数使 由于及，得出 ， 于是，再由得出 于是，与得出一样地，我们可以陆续得出： 对比和的表达式可知， 证明完毕 性质４是性质３的直接推论．但它给出了一种求（５.１.１）的算法，这种算法称之为共轭方向法．结合性质２，我们可以得到如下的性质５． 性质５设是上的一组线性无关的向量，则从任意指定的出发，按以下迭代产生的序列： Ｓ１：取，，； Ｓ２：计算，取； 计算，得出； 如此进行下去，直到第n步： Ｓn：计算取 计算，得出． 显然： 根据性质４可知，不论采用什么方法，只要能够构造个两两Ａ共轭的向量作为搜索方向，从任一初始向量出发，依次沿两两Ａ共轭的方向进行搜索，经 步迭代后，便可得到正定方程组的解．清华大学高等数值计算(李津)实践题目一(共轭梯度CG法,Lanczos算法与MINRES算法)
共轭梯度法程序
作业4-FR共轭梯度法
车辆薄板有限元分析中的多因子不完全分解预处理解法
共轭梯度算法分析与实现
最优化课程设计--共轭梯度法算法分析与实现
大型复线性方程组预处理双共轭梯度法
共轭梯度实验报告
油藏数值模拟技术现状与发展趋势
共轭梯度法
消去法实验报告19
最优化牛顿法最速下降法共轭梯度法matlab代码
共轭梯度法及其基本性质
相关主题
文本预览