（计算数学专业论文）求解非对称线性方程组的再开始的qmr方法.pdf

摘要 本文在q m r 方法的基础上提出了两种再开始的q m r 方法，并讨论了它在求解大 型稀疏非对称线性方程组中的应用全文分为四章 第一章首先介绍了求解大型稀疏非对称线性方程组的比较常用的一些k r y l o v 子 空间方法，例如g m r e s 方法，d q g m r e s 方法，和q m r 方法然后我们介绍了 k r y l o v 子空间方法的一般定义，这是再开始q m r 算法的基础 第二章主要介绍了q m r 方法和再开始的q m r 方法，在介绍q m r 方法时，重点 介绍了l a n c z o s 双共轭方法，它是q m r 方法的核心，与此同时给出了q m r 方法的推 导过程，接着简单讨论了q m r 方法中准确残量范数的计算，并在q m r 方法的基础上 导出了两种再开始的q m r 方法 第三章讨论了再开始的q m r 方法在求解大型稀疏线性方程组中的应用，通过一些 数值例子的计算，比较了传统的q m r 方法和文中提出的两种再开始的q m r 方法，表 明再开始的q m r 方法有明显的优越性，特别是第一种再开始的q m r 方法能求解某些 q m r 方法不能解的问题 第四章首先介绍了g m r e s 方法，同时给出了它的再开始方法，然后通过一些数 值例子的计算，比较了再开始的g m r e s ( 5 ) 方法和两种再开始的q m r 方法，表明迭 代收敛的情况下再开始的q m r 方法的重新丌始次数要明显少于再开始的g m r e s ( 5 ) 方法，与此同时计算的时间也要小于再开始的g m r e s ( 5 ) 方法，特别是有些问题再开 始的g m r e s ( 5 ) 方法不能求解，而再开始的q m r 方法却能解 关键词：l a n c z o s 双共轭方法，k r y l o v 子空间方法，q m r 方法，再开始的q m r 方法，g m r e s 方法，再开始的g m r e s ( 5 ) 方法，a r n o l d i 方法 i a b s t r a c t i nt h i sp a p e r , t w or e s t a r t e dm e t h o d sb a s e do nq m rf o rs o l v i n gl a r g ea n ds p a r s en o n - s y m m e t r i c l i n e a rs y s t e m sa r ep r o p o s e d t h e r ea r ef o u rc h a p t e r si na 1 1 f i r s t , w em a k eas i m p l ei n t r o d u c t i o na b o u tt h ec o m m o nk r y l o vm e t h o d s ，s u c ha s g m r e s ，d q g m r e s lq m r a n dt h e nw eg i v eab a s i cd e f i n i t i o no fk r y l o vm e t h o d , w h i c hi st h et h e o r yb a s i so fq m r i nc h a p t e r2 ，w eg i v ea ne l e m e n t a r yi n t r o d u c t i o nt ot h eq m r t h el a n c z o s b i o r t h o g o n a l i z a t i o nm e t h o d ，t h ec o r eo fq m r ，i si l l u s t r a t e ds p e c i f c a l l y a tt h es a m et i m e fw e d i s p l a yh o wt h eq m rg e n e r a t e sa n ds i m p l yd i s c u s st h ec o m p u t a t i o no fe x a c tr e s i d u a l n o r mo fq m r o nt h eb a s i so fq m r ，t w or e s t a r t e dv a r i a n t so fq m ra r ep r o p o s e d i nc h a p t e r3 ，s u c ht w or e s t a r t e dq m rm e t h o d sa r ea p p l i e dt os o l v e l a r g ea n ds p a r s e n o n s y m m e t r i cl i n e a rs y s t e m s f o u rn u m e r i c a le x a m p l e ss h o wo u rm e t h o d sa r ee f f i - c i e n ta n dh a v i n ga no b v i o u sa d v a n t a g ec o m p a r e dw i t ht h eq m r e s p e c i a l l y , o u rf i r s t m e t h o di sa b l et os o l v ec e r t a i nn o n s y m m e t r i cl i n e a rs y s t e m sw h i c ht h eq m rc a n n o t h a n d l es o m e t i m e s i nc h a p t e r4 ，w ef i r s tb r i e f l yi n t r o d u c eg m r e s ，a n dg i v ei t sr e s t a r t e dv e r s i o n t h e n ，s o m en u m e r i c a lr e s u l t sa r ep r e s e n t e dt oc o m p a r et w or e s t a r t e dq m rm e t h o d s a n dr e s t a r t e dg m r e s r e s p e c t i v e l y i nt h ec a s e s w h e r eo u rm e t h o dn e e d sl e s se n o u g h n u m b e ro fr e s t a r t st oc o n v e r g et h a nt h er e s t a r t e dg m r e s ，t h ea s s o c i a t e dc p uc o n - s u m i n gt i m ei sa l s or e d u c e d m o r e o v e r , o u rm e t h o d c a nc o p ew i t hs o m en o n s y m m e t r i c l i n e a rs y s t e m ss u c c e s s f u l l yb u tt h er e s t a r t e dg m r e sf a i l s k e yw o r d s ：l a n c z o sb i o r t h o g o n a l i z a t i o nm e t h o d ik r y l o vm e t h o d sfq m rm e t h o d r g m r e sm e t h o d , r e s t a r t e dg m r e s ( 5 ) m e t h o d ，a r n o l d im e t h o d 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝鎏盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名： 签字日期：幻夕年多月厂日 学位论文版权使用授权书 本学位论文作者完全了解逝姿盘鲎有权保留并向国家有关部门或机 构送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝鎏盘堂 可以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影 印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：谚 导师签名： 签字日期：珈? 年6 月f 日 签字日期： 年月 日 第1 章背景介绍 1 1 引言 问题： a x = b ( 1 1 ) 其中a 是一个大型稀疏的n 维实系数矩阵，z ，b 孵此问题是数值计算中经常遇到的 问题之一例如，对偏微分方程进行有限差分或进行有限元逼近时，就会产生形如( 1 1 ) 的 线性方程组对于问题( 1 1 ) 的解，很多学者都进行了广泛、深入地研究( 【1 h 4 】，【7 】一【8 】) 而k r y l o v 子空间方法往往成为最受欢迎的方法之一我们根据( 1 1 ) 中系数矩阵的特性， 一般可分为两种情况来讨论问题( 1 1 ) 的解 ( 1 ) 当系数矩阵a 是对称矩阵时，又可将此情况细分为a 是对称正定的和a 是对称 非正定两种情况若a 是对称正定矩阵，则h e s t e n e s 和s t i e f e l d 的经典共轭梯度法是 解决这类问题的所有方法中最为有效的一种方法之一，特别是将一些预处理方法与之 结合时，往往能产生更为理想的效果若a 是对称非定矩阵时，也有学者做了大量的研 究 1 9 1 ( 2 ) 当系数矩阵a 是一般的非对称矩阵时，也可将此情况细分为两种情况来考 虑即a 是非对称正定矩阵和a 是非对称非定矩阵尤其对于一般的非对称非定矩 阵，k r y l o v 子空间方法是最常用的方法之一，例如，s a a d 和s c h u l t z 1 最早提出 了广义的最小残量方法( g m r e s ) 这种方法的核心思想是极小化处在k r y l o v 子空 间的解的残量范数，它基于a r n o l d i 过程，此过程丰要是为给定的子空间寻找基， 而且产生的基向量是正交的，对于g m r e s 方法来说，这个子空间就是系数矩阵 a 关于单位化了的初始残量的k r y l o v 子空间另外，r o l a n dw f r e u n d 2 等人提 出t q u a s i m i n i m a lr e s i d u a l ( q m r ) 方法这种方法的核心思想也是极小化处在 k r y l o v 子空间的解的残量范数，不过，q m r 方法与g m r e s 方法最大的不同点是， 它是一种近似极小化残量范数的方法，而且是种只需要三个变量的短递归方法，q m r 方法基于l a n c z o s 双共轭过程，此过程为两个k r y l o v 子空间来寻找基，其中一组基 就是解的搜索空间的基，这个搜索空间就是系数矩阵a 关于单位化了的初始残量的 k r y l o v 子空间，与a r n o l d i 过程不同的是，l a n c z o s 双共轭过程要产生两组基，而且 产生的基向量不是正交的对于g m r e s 算法来说，最常用的是它的再开始方法，即 再开始的g m r e s ( m ) 方法一般情况下，它的计算效果很好，但在某些问题上，也 可能出现停滞现象，例如，残量范数不再下降为了提高再开始的g m r e s ( m ) 的收 】 浙江大学硕士学位论文 敛速度，有学者【4 】提出了一种带权的方法另外，文献【7 】进一步研究了带权的再开始 的g m r e s ( m ) ，同时指出，预处理后的带权再开始的g m r e s ( m ) 方法并没有未预 处理的带权再开始的g m r e s ( m ) 方法好事实上，为了克服再开始的g m r e s ( m ) 停 滞的缺点，后来有学者y s a a d 和k 彤“ 1 1 1 提出了d q g m r e s 算法，它是再开始的 g m r e s ( m ) 方法的改进方法，这种方法和g m r e s 方法的不同点是，它是种基于不完 全正交过程的方法，与q m r 方法一样，它也是一种近似极小化残量范数的短递归方 法，且判断算法崩溃的准则都是根据近似的残量范数是否满足给定的精度要求，只不 过，q m r 算法通过l a n c z o s 过程要产生两组基，而d q g m r e s 只产生一组基但是在 g m r e s 算法中，逼近解的残量范数永远不会增加，但是q m r 算法和d q g m r e s 算 法却不能保证如此，为了使逼近解的残量范数在迭代的过程中不会增加，有学者 1 2 1 在 d q g m r e s 算法的基础上提出了一种再开始的方法，由于q m r 算法也会在迭代过 程中使得逼近解的残量范数增加，受文献 1 2 1 作者的启发，我们提出了两种再开始的 q m r 算法 1 2k r y l o v 子空间方法 我们知道，k r y l o v 子空间方法是求解大型稀疏线性方程组的一类较为常用的方 法，本篇文章所提及到的方法都属于k r y l o v 子空间方法，因此，我们有必要先对这类 方法做一下简单的介绍 k r y l o v 子空间方法是一种投射方法，可分为正交投射和斜交投射两种类型首先， 我们介绍什么是投射方法以问题( 1 1 ) 为例，对于求解引言中的问题( 1 1 ) 的一般投射方 法是：在维数为m 的仿射子空间x o + 中搜寻逼近解x m ，而且逼近解的残量满足 p e t r o v g a l e r k i n 条件： b a x m 上l m ( 1 2 ) 其中l m 是另一个维数为m 的子空间，这里的x o 表示问题( 1 1 ) 的一个任意初始猜测 解接下来，我们介绍一般的k r y l o v 子空间及k r y l o v 子空间方法 1 k r y l o v 子空间的定义 一般地，我们把子空间 ( a ，v ) = s p a n v ，a v ，a m - 1 u )( 1 3 ) 叫做k r y l o v 子空间 在没有歧异的情况下，将此空间简记为 2 k r y l o v 子空间方法 9 浙江大学硕士学位论文第1 章背景介绍 k r y l o v 子空间方法是指子空间是k r y l o v 子空间 ( a ，r o ) = s p a n r o ，a r o ，a m - 1 t o ( 1 3 ) 的方法，其中r o = b a x o k r y l o v 子空间方法种类较多，它们的不同点就在于另一子空间l 仇的选法不同从 逼近论的角度看，通过k r y l o v 子空间方法得到的逼近解有如下形式： a 一1 b x m = z o + q m 一1 ( a ) 7 o( 1 4 ) 其中g m 一1 是个次数为m l 的多项式最简单的情况是：x o = 0 ，则 a 。b q m 一1 ( a ) 6( 1 5 ) 3 子空间l m 的选择 ( 1 ) l m = 和l m = a k m ( 2 ) 将l m 定义为a r 关于初始残量r o 的k r y l o v 子空间，即l m = ( ，r 0 ) 在这 里，我们只给出了k r y l o v 子空间方法的简单介绍，读者要想更深入地了解这类方法， 可参看文献【8 】 3 第2 章 q m r 算法和再开始的q m r 算法 2 a 1 q m r 算法的介绍 q m r 算法是一种基于l a n c z o s 双共轭过程的方法，而l a n c z o s 双共轭过程是为以 下两个子空间建立一对双正交基 k m ( a ，v 1 ) = s p a n v 1 ，a v l ，a m 一1 v 1 ) ( ，w 1 ) = s p a n w 1 ，a r w l i ( a t ) m - 1 w 1 ) 下面，我们给出l a n c z 0 8 双共轭算法的描述 2 1 1l a n c z o s 双共轭算法 1 选择两个向量v 1 ，w 1 ，满足( v 1 ，w 1 ) = 1 2 另厨= 5 1 三0 ，w o = v o 三0 3 f o r j = 1 ，2 ，m d o ： 4 哟=( a ，) 5 瞬1 = a v 3一a j v j 一8 翔一1 6 叫；十i = 譬j q 一6 j 一1 7 妨+ 1 = i ( 略，嗡。) 1 2 , 若如+ 1 = 0 ，则停止 8 岛+ ，= ( 略，嗡t ) 岛+ 9 w j + l = ；+ l f 8 j + 1 1 0 v j + l = ”沁 6 机 1 1 e n d d o 对于l a n c z o s 算法，我们有如下几点说明： ( 1 ) 根据此算法，不难看出： ( v j + i 帅h 器，券w j + i ，= 岩= l ( 2 ) 从l a n c z o s 算法的第7 - 8 行知： 6 j 0 ，8 = 士6 4 ( 2 1 ) ( 2 2 ) ( 3 ) 为以下讨论的方便，我们定义是如下形式的三对角矩阵： ( 2 3 ) l a n c z o s 双共轭算法产生了两组基， 耽) 仁1 ，2 ，m 和 训t 信1 ，2 ，j m ，它们是双正交的， 以下定理就很好说明了它们的双正交性 定理2 11 8 1 若l a 钆c z o s 双共轭算法在第m 步之前没有崩溃，则向量序列 忱】扛1 ，2 ，m 和 叫i ) t 乩2 ，m 形成了一个双正交系统即，( ，1 1 ) i ) = 如，1 t ，j m 而且， 仇) t = 1 ，2 ，棚是 ( a ，u 1 ) 的一组基，w 。) t _ 1 2 ，仇是( 俨，w 1 ) 的一组基且以下几种关系式也成立： a = 焉+ + 1 秽m + 1 e m l m a t w m ：丁+ 风+ 1 w m + l e m r t a = 证明： 用数学归纳法证明 仇) 讧1 ，2 ，m 和 毗) t ；1 2 ，m 的双正交性 ( 2 4 ) ( 2 5 ) ( 2 6 ) ( 1 ) 由算法知，( v l ，w 1 ) = 1 ( 2 ) 现假设向量u 1 ，和叫1 ，嘶是双正交的，下面我们证明向量u 1 ，吻+ 1 和叫1 ，w j + i 也是双正交的 首先，我们要证明对于所有满足条件z 歹的z ，都有( 吻+ 1 ，w i ) = 0 ( i ) 当i = j 时，则 ( + 1 ，嘶) = 氍1 ( a v j ，w j ) 一( ，嘶) 一岛( 一1 ，吻) 】 由归纳假设知，( 一1 ，) = o r ( v j ，哟) = 1 ，又= ( a v j ，吻) 所以( + 1 ，) = 0 ( i i ) 现在考虑当t i i r 刑。1 i2 ，则停止继续迭代，与此同时令：z o = z m ， 0 = r m ，饥= l i r o l l 2 ，w l = v l = 伯7 1 ，并转到第2 步，否则继续迭代，直到满足给定 的精度要求 2 2 3 再开始的q m r 算法2 1 开始：计算7 0 = b a x o 和，y 1 = i i r o l l 2 ，伽1 = 1 = r o 7 1 2 迭代：f o rk = 1 ，2 ，md o ： o l k = ( a v k ，w k ) u 鑫1 = a v k o l k v k 一凤v k 一1 叫4 1 。a t w k o l m w k 一5 k w k 一1 以+ 1 = l ( u 4 1 ，叫4 1 ) i m ，若6 后+ 1 = 0 ，则停止 8 k + 1 ( 4 1 ，叫4 1 ) 氏+ 1 t k 一1 1 = 风，t k ，七= o l k ，t k + l ，1 = 5 k + 1 f o ri = k 一2 k 一1 ，d o ： ( t i 气+ l 南, ) = 批州t i , k ，七) 1 5 窖 = | l m m c s 浙江大学硕士学位论文第2 章q m r 算法和再开始的q m r 算法 e n d d o c 南2 孺麓霖 s 惫= 警k , k c 知 t 南，七2c k t k ，k + s k t k + l ，七 t k + 1 南= 0 ( o 。) = c k 班苫) p 南= v 七一江k - 七1 2 姗纯) 亡七， z 七= x k 一1 + 1 k p 缸 e n d d o 重新开始过程：计算l i r m l l 2 = f | 6 一a x m i l 2 ，若满足给定精度要求，则停止迭 代，否则令：x o = z m ，r o = r m ，7 1 = i i7 o 怯w l = v l = r o 7 1 ，并转到第2 步 1 7 第3 章再开始q m r 算法求解非对称线性方程组 ；3 1 1 数值算例 为了比较再开始的q m r 算法和q m r 算法，在这一节里，我们给出了一些数值例 子，其中，一些数值例子来自于某些学者的论文中，一些来自于矩阵市场【2 7 】通过这 些数值例子的比较，我们发现，在某些问题上，再开始的q m r 算法比q m r 算法更具 有优势，特别是有些问题用传统的q m r 算法无法求解，但用我们的再开始的q m r 算 法却可以求解我们先比较了再开始的q m r 算法1 和q m r 算法，然后比较了再开始的 q m r 算法2 和q m r 算法以下问题的比较都是未经预处理的比较 例3 1 此例来自于文献 2 5 1 中的例2 假设t o e p l i t z 矩阵a = t o e p l i t z ( 1 ，- 3 _ _ 5 5 ，1 ，1 ，1 】) r 2 0 0 2 0 0 是线性方程组( 1 1 ) 的系 数矩阵其中，矩阵的对角元素是标住了下划线的数字令b = a l l ，1 ，1 1 r r 2 0 0 初始 逼近解为z o = 0 ，0 ，o 】t r 2 0 0 显然，该问题的准确解是x + = 【1 ，1 ，1 】t r 2 0 0 矩阵 4 的条件数为1 3 2 9 1 1 0 1 1 我们设置的精度为f | 6 1 1 2 1 0 邙+ 1 0 _ 1 2 首先，我们用传统的q m r 算法进行计算，得到的逼近解z 的绝对误差为忙一 z + 1 1 2 = 3 4 7 9 7 8 ，可见，该解严重失真 图3 1 ：图1 1 8 浙江大学硕士学位论文第3 章再开始q f r 算法求解非对称线性方程组 图3 2 ：图2 上面的图1 给出了| | + l l l 2 的值随着m 的变化而变化的情况，而图2 给出了迭代逼近 解的真实残量范数和近似残量范数随着仇的增大而变化的情况 从图1 中，我们发现，i i + 1 1 1 2 的值在整个迭代过程中都是递增的，丝毫没有下降的 趋势，在给定的精度设置下序歹 3 ie z m + 1 i | 2 ) m ：1 ，2 是无界的而在图2 中，迭代逼近解的真 实残量范数也是稳步增加的，没有下降的趋势，因此，导致逼近解的性态极差，就算提 高精度也不会让解的精度提高，因为序列删z m + 1 1 1 2 ) m ：1 ，2 ，没有下降的趋势，提高精度设 置反而会使得逼近解越来越偏离准确解，故我们说传统的q m r 算法在求解这个问题时 是失败的 接下来，我们用再开始的q m r 算法1 进行计算，则求解该问题需要的时间 是0 5 4 秒，并且能得到问题的准确解下面的表1 给出了再开始的q m r 算法1 和传统的 q m r 算法的数值结果的比较 表3 1 ：例1 的数值结果 迭代使用的方法q m r 算法再开始的q m r 算法1 计算所耗的时间0 0 4 秒0 3 8 秒 解的绝对误差3 4 7 9 80 0 例3 2 此例中的矩阵o r s i r r 一1 r i 0 3 0 1 0 3 0 来自于矩阵市场【2 7 】，我们就令线性方 程组( 1 1 ) 的系数矩阵a - - o r s i r r _ l ，初始逼近解为z o = 0 ，0 ，o t r 1 0 3 0 ，且令6 = 1 9 浙江大学硕士学位论文第3 章再开始q m r 算法求解非对称线性方程组 a 1 ，1 ，1 】t r 1 0 3 0 该问题的准确解为z + = 1 ，1 ，l 】丁r 1 0 3 0 ，矩阵a 的条件数 为1 6 7 2 0x1 0 5 我们设置的精度) 9 1 b l l 2 1 0 6 + 1 0 1 2 下面分别用q m r 算法和再开始 的q m r 算法1 进行求解，表2 给出了两种方法的数值结果的比较 表3 2 ：例2 的数值结果 迭代使用的方法q m r 算法再开始的q m r 算法1 计算所耗的时间 1 8 4 2 秒3 0 8 秒 解的绝对误差0 o0 0 从表2 中可以看到，以上两种方法都可以得到问题的准确解，但是我们的方法不仅 可以得到问题的准确解，而且能够大大缩短运算时间，因而在求解这个问题上再开始的 q m r 算法1 优势很明显 例3 3 此例中的矩阵o r s i r r _ 2 r s 8 6 8 8 6 来自于矩阵市场【2 7 】，我们就令线性方 程组( 1 1 ) 的系数矩阵a = o r s i r r _ 2 ，初始逼近解为铷= 0 ，0 ，o 】t r 8 8 6 ，且令6 = a 1 ，1 ，1 t r 8 8 6 该问题的准确解为z + = 1 ，1 ，1 】t r 8 8 6 ，矩阵a 的条件数 ) 91 6 7 1 6x1 0 5 我们设置的精度为i i b l l 2x1 0 6 + 1 0 1 2 分别使用q m r 算法和再开始的 q m r 算法1 进行计算，表3 给出了两种方法的数值结果的比较 表3 3 ：例3 的数值结果 迭代使用的方法q m r 算法 再开始的q m r 算法1 计算所耗的时间5 9 2 秒2 5 0 秒 解的绝对误差0 0o 0 例3 4 此例中的矩阵s a y l r l r 2 3 8 2 3 8 来自于矩阵市场【2 7 】，我们就令线性方程 组( 1 1 ) 的系数矩阵a = s a y l r l ，初始逼近解为z o = 0 ，0 ，o 】t r 2 3 8 ，b = a 1 ，1 ，1 】r r 2 3 8 该问题的准确解为z + = 1 ，1 ，1 丁r 2 3 8 ，矩阵4 的条件数) 9 1 5 9 1 8x1 0 9 我们设 置的精度) 91 1 b l l 2 1 0 6 + 1 0 1 2 分别使用q m r 算法和再开始的q m r 算法1 进行计算， 表4 给出了两种方法的数值结果的比较 表3 4 ：例4 的数值结果 迭代使用的方法q m r 算法再开始的q m r 算法1 计算所耗的时间 t 4 9 4 1 秒 解的绝对误差 t 0 0 0 7 6 2 0 浙江大学硕士学位论文 第3 章再开始q m r 算法求解非对称线性方程组 表4 中的虚线”t ”表示此种方法不收敛 由以上几个数值例子的比较，我们发现，在都能解决问题的前提下，即得到的逼近 解的误差满足一定要求的时候，再开始的q m r 算法1 比传统的q m r 算法所用的时间 要少，特别是有些问题，传统的q m r 算法不能求解，但是我们的方法可以解，另外， 对于例4 ，虽然再开始的q m r 算法1 可以求解，但是时间消耗偏大，事实上，以上的比 较都是未经预处理的比较，实际上，我们可以考虑采用一些预处理技术应用到再开始的 q m r 算法1 当中，以减少时间上的消耗接下来，我们改用再开始的q m r 算法2 来重新 求解上面的四个数值例子，并且将其与传统的q m r 算法进行比较，算法的精度设置均 保持不变，数值结果见以下四个表格 首先，我们给出的是再开始的q m r 算法2 和传统的q m r 算法在求解以上的 例3 1 的数值结果 表3 5 ：例1 的数值结果 迭代使用的方法 q m r 算法再开始的q m r 算法2 计算所耗的时间0 0 4 秒0 4 2 秒 解的绝对误差 3 4 7 9 80 0 从上表可知，再开始的q m r 算法2 对以上问题也能有效解决，能得到原问题的准 确解 下面的表6 是再开始的q m r 算法2 和传统的q m r 算法在求解上面的例3 2 的数值结 果 表3 6 ：例2 的数值结果 迭代使用的方法 q m r 算法再开始的q m r 算法2 计算所耗的时间1 8 4 2 秒4 6 6 秒 解的绝对误差 o 00 0 从表6 我们看到，在求解此问题时，再开始的q m r 算法2 也能得到问题的准确解， 而且与q m r 算法相比，计算时间大大减少，因而，我们的再开始的q m r 算法2 在这 个问题的求解上优势也是明显的 接下来，我们给出的是在求解上面的例3 3 时，再开始的q m n 算法2 和q m r 算法 的数值结果的比较 2 1 浙江大学硕士学位论文第3 章再开始q m 只算法求解非对称线性方程组 表3 7 ：例3 的数值结果 迭代使用的方法q m r 算法再开始的q m r 算法2 计算所耗的时间5 9 2 秒 4 0 2 秒 解的绝对误差0 0 0 o 下面的表8 是求解上面的例3 4 时，再开始的q m r 算法2 和q m r 算法的数值结果的 比较图中的符号”干”表示该方法不收敛，可见，这两种方法在求解这个问题上都是失 败的 表3 8 ：例2 的数值结果 迭代使用的方法q m r 算法再开始的q m r 算法2 计算所耗的时间 tt 解的绝对误差 t t 3 2总结 在本篇文章里，我们提出了求解大型稀疏非对称线性方程组的两种再开始的方法， 即再开始的q m r 算法1 和再开始的q m r 算法2 两种方法的共同点是都要进行迭代逼近 解的准确残量范数，并以此作为迭代终止的准则，这和传统的q m r 算法是不一样的， 因为传统的q m r 算法不用计算逼近解的准确残量范数，而是近似的残量范数，且以此 作为迭代终止的准则再开始的q m r 算法1 和再开始的q m r 算法2 的不同点体现在以下 两方面 ( 1 ) 在进行迭代求解时，再开始的q m r 算法1 是每迭代一次都要计算一次逼近解的 准确残量范数，而再开始的q m r 算法2 是每隔m 步计算一次逼近解的准确残量范数， 其中m 的值是预先给定的，像本文中仇的值是1 0 ( 2 ) 两种再开始的q m r 算法再开始的具体实现过程不一样对于再开始的q m r 算 法1 来说，如果在迭代时，当前步的逼近解的准确残量范数大于上一步的逼近解的准确 残量范数，且逼近解的精度没满足给定的要求则将当前的逼近解作为初始猜测解重新开 始q m r 算法但是再开始的q m r 算法2 是每m 步计算一次逼近解的准确残量范数，看 逼近解的准确残量范数是否满足给定的精度要求，若满足则终止迭代，否则以当前步的 逼近解作为初始猜测解重新开始q m r 算法 当然，无论是再开始的q m r 算法1 还是再开始的q m r 算法2 ，一项重要又比传统 的q m r 算法耗时多的工作就是逼近解的准确残量范数的计算，这也是我们的再开始的 浙江大学硕士学位论文第3 章再开始q m 兄算法求解非对称线性方程组 q m r 算法和传统的q m r 算法一个很大不同的地方既然计算逼近解的准确残量范数要 消耗额外多的时间，为什么我们还要选用逼近解的准确残量范数作为迭代终止的准则 呢? 在这里，我们进一步说明一下，事实上，在用传统的q m r 算法进行迭代时，逼近 解的真实残量范数和近似残量范数有可能会出现差距很大的现象，本章中的例1 就能说 明这种现象，这会使得迭代解严重失真我们的再开始的方法就是为了避免这种现象而提 出的，而且，我们要指出，我们的方法在求求解以下类型的问题是有明显优势的 ( 1 ) 在迭代过程中，逼近解的准确残量范数和近似残量范数差距很大时，例如，数值 例子的例1 和例4 就属于这种情况 ( 2 ) 在迭代过程中，逼近解的近似残量范数的下降速度很慢，特别出现停滞现象的时 候，例如，数值例子的例2 和例3 属于此情况 通过前面四个数值例子的比较，不难发现，我们的再开始的q m r 算法还是有明显 优势的，在都能解决问题的前提下，再开始的q m r 算法往往能够节省不少时间，特 别是再开始的q m r 算法1 能够求解传统的q m r 算法不能解的某些问题虽然再开始的 q m r 算法2 只能求解其中的三个，但是与传统的q m r 算法相比，仍不失它的优势， 在都能求解的情况下，再开始的q m r 算法2 也能节省很多时间不过从上面的计算结果 看，再开始的q m r 算法1 比再开始的q m r 算法2 更具有优势 第4 章再开始g m r e s 算法和再开始q m r 算 法的比较 4 1引言 我们知道，广义的最小残量算法( g m r e s ) ，特别是再开始的g m r e s ( m ) 算法是 一种比较常用的k r y l o v 子空间方法，它在求解很多大型的稀疏问题上都有优势，由 于再开始的g m r e s ( m 1 算法和我们引进的再开始的q m r 算法都要进行准确残量范 数的计算，而且迭代终止的准则都是一样的，即看迭代逼近解的准确残量范数是否满 足我们给定的精度要求因此，在这一章里，我们想通过一些数值例子来比较再开始的 g m r e s ( m 1 和两种再开始的q m r 算法 4 2g m r e s 算法的简介 既然要比较再开始的g m r e s ( m ) 算法和再开始的q m r 算法，那么首先我们有必 要了解什么是g m r e s ( m ) 算法，事实上，g m r e s ( m ) 算法是一种基于k = 和 l = a 的正交投射方法，其中是( 1 1 ) 中系数矩阵a 关于v 1 = r o l l r o l l 2 的m 维 k r y l o v 子空间，即k m ( a ，v 1 ) = s p a n v 1 ，a v t ，a m - - 1 v l ，r o 是初始残量下面，我们 简要阐述一下g m r e s ( m ) 算法的基本思想，它可以从以下三方面考虑 ( a ) 在仿射子空间z o + k n 中寻找逼近解x ) 通过下面的a r n o l d i 算法找到子空间的一组正交基，设产生的这m 个基向量 组成的矩阵为，则逼近解可以表示为： x = x o lv m y a r n o l d i 算法描述 1 选择向量v l ，使其满足i i u l l l 2 = 1 2 f o r j = 1 ，2 ，仇d o ： 3 计算= ( a v i ，耽) ，i = 1 ，2 ，j 4 计算w j = a 名1 仇 5 + 1 ，j = 1 1 w j i l 2 5 如果h j + 1 ，j = 0 则停止 2 4 ( 4 1 ) 浙江大学硕士学位论文第4 章再开始g m r e s 算法和再开始q m r 算法的比较 7 v j + 1 = 叫j h j h j 8 e n d d o 并且我们记瓦是由a r n o l d i 算法产生的所有非零元素h 巧构成的( m + 1 ) 仇矩 阵，而是百m 去掉最后一行形成的矩阵，由a r n o l d i 算法，可得以下等式： a = + 1 日m ( 4 2 ) ( c ) 通过极小化如下形式的泛函来唯一确定逼近解的表示形式 j ( y ) = i i b a x l l 2 = 1 1 6 一a ( x o + 可) 1 1 2 =