【精品】VC++GMRES算法的加速收敛现象分析(论文+源代码)
收藏
资源目录
压缩包内文档预览：(预览前20页/共46页)
编号：1639426
类型：共享资源
大小：4.32MB
格式：RAR
上传时间：2017-08-30
上传人：机****料
认证信息
个人认证
高**（实名认证）
河南
IP属地：河南
50
积分
- 关 键 词：
-
精品
vc
gmres
算法
加速
收敛
现象
分析
论文
源代码
- 资源描述：
-
【精品】VC++GMRES算法的加速收敛现象分析(论文+源代码),精品,vc,gmres,算法,加速,收敛,现象,分析,论文,源代码
- 内容简介：
-
学院理学学士论文 摘要 I 摘要 随着科学和工程技术的发展，越来越多的问题需要求解大规模的线性方程组，对这类方程的快速求解已成为数值代数研究的热点之一，特别是具有稀疏结构的大型方程组的求解。基于 理的 法是求解这种线性代数方程组的近似算法，以下称这种方法为广义极小残余算法 (法 )。 法在迭代过程中通常表现出一种加速收敛行为，随着迭代次数的增加，这种加速收敛现象越明显，即残量收敛会随着迭代步数的增加而逐渐得到改善。在 法中，这种加速收敛与 有密切关系。通过分析，我们发现 加速收敛与其斜投影过程中产生的 对特征值的逼近程度有关系。在实际应用中，为了减少存储量和计算量，我们通常使用 法的重新开始版本来求解大型非对称线性方程组。本文描绘了 m)的加速收敛现象，并通过实验给予解释。 关键字 ： 广义最小残量； 空间； ； 加速收敛； 正交投影方法； 非对称线性方程组 学院理学学士论文 Ab s t r a c t n of of is of is is to of we ( is of so of It a of to as of be as we in to a of of we in to be to In we m) m), 学院理学学士论文 目录 录 摘要 . I . 一章 引言 . 1 第二章 法基础知识 . 3 向量范数 . 3 线性方程组最小二乘问题 . 4 交化方法 . 4 换 . 4 第三章 法理论 . 6 空间方法的基本理论 . 6 法 . 7 法结构 . 8 第四章 法的加速收敛现象分析 . 9 第五章 数值示例与算法实现 . 19 数值实验 . 19 5 算法改进与实现 . 22 预处理技术 . 22 算法实现 . 24 实验总结 . 34 致谢 . 35 参考文献 . 36 F . 37 文献报告 . 41 学院理 学学士论文 第一章 引言 1 第一章 引言 关于线性方程组的数值解法一般分为两大类 :直接法和迭代法。 直接法是在没有舍入误差的情况下，通过有限步四则运算可以求得方程组精确解的方法。但是，在实际计算时，由于初始数据变为机器数而产生的误差以及计算过程所产生的舍入误差等都对解的精确度产生影响，因此直接法实际上也只能算出方程组真解的近似值。直接法的基本思想是将结构上比较复杂的原始方程组，通过 等价变换化成结构简单的方程组，使之变成易于求解的形式，然后再通过求解结构简单的方程组来得到原始方程组的解。即 A x b G x d G 通常是对角矩阵、三角矩阵或者是一些结构简单的矩阵。目前较实用的直接法是 去法的一些变形，例如选主元的 去法和矩阵的三角分解法，它们都是目前计算机上常用的有效方法。 迭代法就是对任意给定的初始近似解向量 (0)x ，按照某种方法逐步生成近似解序列 ( 0 ) ( 1 ) ( 2 ) ( ), , , . . . . . , , . . x x x,使极限 ()kk 为方程组的解，即 ()Ax b 。因此迭代法是用某种极限过程去逐步逼近真解的方法，从而也可以用有限步运算出具有指定精确度的近似解。迭代法主要有 代法、 代法、逐次超松弛法以及共轭斜量法。 直接法的优点是计算量小，并且可以事先估计，缺点是所需存储单元较多，编写程序复杂；迭代法的优点是原始系数矩阵始终不变，因而算法简单，编写程序也比较方便，且所需存储单元也较 少，缺点是只有近似解序列收敛时才能被采用，而且存在收敛性和收敛速度的问题。对于中等规模的 n 阶 (m), m is of ; if(; j=i+1;jk;j+) gi-=hji*gj; gi/=hii; /更新解 x=x0+vi*yi i=0;ik;i+) x +=gi*(*vi); r =x, /计算残差，检查是否收敛 ; if( /如果残差很小，终止 /x); /得到最后的残差 /为 v 和 h 重新分配空间 i=0; i=m;i+)vi; v; i=0;im;i+) hi; h; if(; ; /m)结束 学院理学学士论文 第五章 数值示例与算法实现 31 以下是一个 法运算界面，做界面的目的是为了更好地分析 做的是一个基于对话框的应用程序。运算主界面如图 5图 5运算界面图 of 5个 算对话框功能主要分成三个部分，它们分别是输入、检验、输出。 输入部分包括输入所要计算的方程组、输入参与 参数。检验部分主要是对稀疏压缩矩阵进行长度匹配检验和对重启 代中的 m 进行检验。输出部分主要由列表输出结果和图形输出结果两个功能。 在输入所要计算方程组中，有三种矩阵输入 :一般矩阵输入、特殊二对角矩阵输入、特殊三对角矩阵输入。界面分别如下图 555学院理学学士论文 第五章 数值示例与算法实现 32 图 5一般矩阵输入图 of 5二对角矩阵输 入图 of 5三对角矩阵输入图 院理学学士论文 第五章 数值示例与算法实现 33 算界面的计算流程如下图 5图 5算流程图 满足 不满足 满足 开始 输入大型稀疏线性方程组 输入运算参数 输出结果和图形 验证 验证 满足 进行 算 学院理学学士论文 第五章 数值示例与算法实现 34 实验总结 此次实验的目的主要是分析 法过程中的加速收敛现象，以上举了几个具有明显特征的数值例子。根据例子表明， 法的收敛效果取决于方程组系数矩阵的实际分布情况，如谱的分布和 与 A 的特征值的逼近程度等。在实际应用中，为了减少存储量和计算量，我们通常使用 法的重新开始版本，在重新开始版本中，对重新开始迭代步长的选择也是至关重要的，合适的m 能够加速 法的收敛，过小 则可能导致迭代的收敛失败，过大则导致计算量的成倍增加及收敛速度减缓。另外，对于预处理子的选择也对 法收敛有重要的影响。 学院理学学士论文 致谢 35 致谢 在系领导的关怀和支持下，经过两个多月以来的努力，此次毕业设计得以完成，愿借此机会向他们表示感谢。在此特别感谢指导老师杨利华在此期间对我的指导和对毕业设计提出宝贵意见及建议，感谢同学们的支持和帮助，感谢学校在此期间为我提供专业机房作为毕业设计场所。另外毕业设计的过程中参考了许多文献，在此也对校图书馆资料室及其作者表示感谢。 学院理学学士论文 参考文献 36 参考文献 1 A 7(1986), 8562 . an of of 1986, 48: 5433 . J. 1993, 48: 3274 钟宝江 . 一种灵活的混合 法 . 高校计算数学学报 , 2001， 23： 2615 Y. M. H. A . 1986, 7: 856 6 B. J. On of 2002, 11: 1377 Y. 105 8 钟宝江 . 法收敛率 . 南京学报 , 1998,5. 9 . A . 1992, 13(3): 79610 杨道奇 ,王小鸽 . C+ 和面向对象数值计算 (C+M. 人民邮电出版社 , 11 王育坚 . 面向对象编程教程 M. 清华大学出版社 , 2003 年 7 月 . 学院理学学士论文 附录 F 7 附录 : he of on of of in to by a is as We do it 937, to a x=b a (A) in an to up of on in is to In 952 of is “of is to be as of a . We if we of is of is of in on in is in 959. 956, as an of is we in 963 a x=b b, A is to a 学院理学学士论文 附录 F 8 in 960s by 955. 972, to an on of G we as as of It in to be or of on U by in as as by of by of to a of an of of of 980s it be in to of be at in a in to as a to A of be to to of In it is to a in of in is a 院理学学士论文 附录 F 9 an of a is an to so it If to in an in a is to LU of a of OR as a to in to be a of OR of to in a of of in in , in a e. g., by it be of of a a is to to is to of is in an on of is a It to of is A of be as a of if is a 院理学学士论文 附录 F 0 to to of on A a of in a to In it is to of be as in to of 73 by of of of by It to in of at as of 学院理学学士论文 附录 文献报告 41 附录 : 文献报告 预处理方法 迭代方法的收敛性 取决于线性方程组系数矩阵谱的分布情况，为了改善这种情况，我们经常利用一种合适的变换来改变线性方程组 。这种方法称为预处理技术。 我们目前还不能确定谁最先提出“预处理技术”这个概念 也可能是 O 基础上提出来的。不管怎么样，这种想法一提出就被广泛应用。 1937 年提出用一个多项式 P（ A） 乘以给定的线性方程组 AX=b 企图加快 代的收敛速度。 在这参考过程中程被称为 迭代。 在 1992 年 表的论文中，多项式预处理被定义于：“求逆矩阵相当于对给定矩阵化为单位矩阵的线性变换。单位矩阵 是一种特殊的矩阵，它的特征值都是 1。假如我们只需要少量变换稀疏的原方程组，那么我们需要计算量更少。 ” 这个程序的目的是“降低线性方程组的倾斜度”，而不是提出确切的解决办法。 他的数学论文中直接使用“预处理”这个名词。 多项式预处理也同样在 1959 年 论文中提及。 956 年认为 法是对一定矩阵的一种加速技术。他的正交化过程相当于预处理的 法。 最后，我们提到 963 年出版的书中使用到了预处理来变 换一个线性方程组，从 AX=b 变换到 b， 的 K 非常接近一个单位矩阵。 现代预处理技术开始于 1960 末和 1970 初。 代中使用预处理因子 而，这种方法早在 1955 年 有过研究。在 1972年， 出在 种不完全 得非常流行而且推导出 程。 O了一篇关于预处理对 法的作用有影响力的论文。 下面介绍并行预处理： 并行 预处理早在向量和并行计算机第一次出现时，就有关于并行预处理的讨学院理学学士论文 附录 文献报告 42 论。标准的基于目前相当流行的 处理本来就是连续的，而且既不能被取代也不能被执行，这种现象很明显。被提出和讨论的第一种思想是基于 解方法。利用 L 和 U 方法就如一开始通过求解原矩阵的逆矩阵方法一样。这也产生了许多有关于“多项式预处理 ” 的文章。这篇调查报告对 20 世纪 80年代末产生了许多区域艺术而且在这篇文章里我们也能够看到多项式预处理被人关注。另一种方法称为“时刻层次”或“波层次”方法，是一种前后方不平行的方法。由于稀疏性，许多 方程组能用这种方法从不同的层次同时求出解一种技术被人称作图论的“拓扑排序”允许检测不同的层次。 然而，这两种方法很快被认为没多大的潜力。时刻层次只有有限的并行条件，并且第一层次和最后一层次小的不能构成条件。很多方法被人们使用来改善这种情况，然而，多项式预处理遇到了最大的挑战。多项式预处理的表现相对于现在存在的方法来说没有太多说服力，尤其是对于迭代很少时。另外，在没定义的矩阵中，我们也很难找到一个非常合适的多项式。当代对这项技术的兴趣已消失的无影无踪。这就是一种例子说明好的基于数学的方法不足以克服这种方法本 身所具有的一种局限性。 红黑混合排顺序是为结构问题改善并行属性的一种很明显的办法，但是实验结果让人很失望，因此这种方法是不可用的。假如对它认真分析，他们能有效地得出很重要的结果。 出这样一种设想，让红黑混合排顺序结合一种降低线性系统阶数的技术。 想法是简单地消除红点，然后为降低了阶数的黑点构造一个 条件。最近， 有 议用一种少阶数的红黑混合排序法以 为 预处理条件。 在这种例子中，成功的关键看起来好象是一种作为红黑 混合排序的 速收敛的综合效率，而且 空间可以消除在关于处理矩阵的一些单个特征值的加速收敛现象中的停滞现象。 另一种关于并行预处理的思想来源于区域分裂法。这种方法存在于偏微分方程中，文献也存在不同的格式，请看下面的例子，比如调研报告。尽管区域分裂法被并行计算机推动使用，但是我们发现这种方法在有构造连续预处理时才能成功。区域分裂法用来解决偏微分方程的离散现象。想法是把区域分成各个子域，然后在各个子域中解决离散偏微分方程。主要问题是在各个子域内部找到恰当的边界值。区域分裂法通常在迭代中使用，而且 内部的边界条件通常是基于对前面学院理学学士论文 附录 文献报告 43 迭代恰当的临近子域近似方法的信息。 明区域分裂法能够加快收敛速度，假如子区域不是很大的话。沿着对角线把矩阵分块，我们也可以把这种方法叫做区域分裂法，假如这个矩阵和一个离散偏微分方程有关系的话，而且这个矩阵排列好了，这是 出来的。他们建议为子模块构造不完全因数分解，然后子模块被应用到向量的相应部分，有的
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号