（计算数学专业论文）改进的正则化共轭梯度法.pdf

瞌 l 奄 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 日驯c ) 年莎月日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 躲雌淼 净tt。 i p 毫 童 ， 摘要 摘要 现代科学工程计算中的很多问题最终都要简化为一个大型稀疏线性系统的求 解问题，因此数值代数与科学计算一直是人们研究的热点。尤其是如何高效、快 速地求解大型稀疏线性方程组具有重要的实际意义。对称正定线性系统有较好的 性质，通常用共轭梯度法进行求解。但是共轭梯度法也不是万能的，对于一些对 称正定线性系统，收敛速度很慢，或者根本不收敛。因此为了提高迭代法的收敛 速度，必须借助于预处理技术。预处理在某种程度上是改善稀疏矩阵谱的性质， b a i ，z h a n g ar e g u l a r i z e dc o n j u g a t eg r a d i e n tm e t h o df o rs y m m e t r i cp o s i t i v ed e f i n i t e s y s t e mo fl i n e a re q u a t i o n s ，zc o m p u t m a t h ，2 0 0 2 ，2 0 ：4 37 “8 】提出了一种对正定 线性系统进行正则化的预条件技术，这种方法结合共轭梯度法有效地解决了很多 病态正定系统的求解问题，能有效地节约计算时间，预处理共轭梯度法的收敛速 度也较快。 针对希尔伯特矩阵，对正则化方法进行改进。改进后的正则化方法更加有效 地解决了病态矩阵收敛慢的问题。改进后的正则化方法结合共轭梯度法的迭代次 数和收敛速度也比原来的方法有很大的改进，数值实验也显示了算法的有效性。 针对最小二乘问题的求解问题提出正则化过程。由于问题的复杂性，结合矩 阵正交化的预条件技术，从理论上进行分析，得出正则化预条件共轭梯度法是最 小二乘问题求解问题的一类快速求解算法。 关键词：病态矩阵，共轭梯度法，正则化，正交化预条件 9盏， c a b s t r a c t a bs t r a c t al o to fm o d e me n g i n e e r i n gc a l c u l a t i o n sa r eu l t i m a t e l yr e d u c e dt oal a r g es p a r s e l i n e a rs y s t e m t h e r e f o r e ，n u m e r i c a la l g e b r aa n ds c i e n t i f i cc o m p u t i n gh a sa l w a y sb e e n a l li m p o r t a n ts t u d y i np a r t i c u l a r ，h o wt os o l v el a r g es p a r s el i n e a re q u a t i o n se f f i c i e n t l y a n dq u i c k l yi sv e r yi m p o r t a n t s y m m e t r i cp o s i t i v ed e f i n i t el i n e a rs y s t e mh a sg o o d p r o p e r t y i ng e n e r a l ，t h ec o n j u g a t eg r a d i e n tm e t h o d i sa l w a y su s e dt os o l v ei t h o w e v e r ， t h ec o n j u g a t eg r a d i e n tm e t h o di sn o tap a n a c e a , f o rs o m es y m m e t r i cp o s i t i v ed e f i n i t e l i n e a rs y s t e m sl i n e a rs y s t e m s ，c o n v e r g e n c es p e e di sv e r ys l o w ，o rn o ta ta l lc o n v e r g e t h e r e f o r e ，i no r d e rt oi m p r o v et h ec o n v e r g e n c er a t eo fi t e r a t i v em e t h o d ，p r e c o n d i t i o n i sn e c e s s a r y p r e c o n d i t i o ni m p r o v e st h es p e c t r a lp r o p e r t i e so fs p a r s em a t r i xt os o m e e x t e n t b a i ，z h a n g ar e g u l a r i z e dc o n j u g a t eg r a d i e n tm e t h o df o rs y m m e t r i cp o s i t i v e d e f i n i t es y s t e mo fl i n e a re q u a t i o n s ，zc o m p u t m a t h ，2 0 0 2 ，2 0 ：4 37 “8 p r o p o s e da c l a s so fr e g u l a r i z e dc o n j u g a t em e t h o d sf o rl i n e a rs y s t e mo fw h i c ht h ec o e f f i c i e n t m a t r i xi si l l c o n d i t i o ns y m m e t r i cp o s i t i v ed e f i n i t em a t r i x ，w h i c hc a ns o l v et h el i n e a r s y s t e me f f e c t i v e l ya n dq u i c k l y i m p r o v e m e n to ft h er e g u l a r i z e dm e t h o di s m a d ef o r t h eh i l b e r tm a t r i x t h e i m p r o v e dr e g u l a r i z a t i o nm e t h o di sa ne f f e c t i v es o l u t i o nt ot h ei l l - c o n d i t i o n e dm a t r i x t h ei m p r o v e dr e g u l a r i z a t i o nm e t h o dc o m b i n ew i t ht h ec o n j u g a t eg r a d i e n tm e t h o d i t e r a t i o nh a sah i g h e rc o n v e r g e n c es p e e dt h a nt h eo r i g i n a lo n e l a s t l y ，t h en u m e r i c a l r e s u l t so ft h em e t h o dw eh a v ep r o p o s e da r ec o m p a r e d 、加t 1 1t h eo l dm e t h o dt oc o n f i r m t h ee f f e c t i v e n e s so ft h ep r o p o s e dm e t h o d r e g u l a r i z a t i o np r o c e s si sp r o p o s e df o r t h el e a s t s q u a r e sp r o b l e m d u e t o c o m p l e x i t yo ft h ep r o b l e m ，c o m b i n e d w i t h o r t h o g o n a l i z a t i o np r e c o n d i t i o n ，t h e e f f e c t i v e n e s so ft h ep r o p o s e dm e t h o di sj u s ts h o w ni nt h e o r y k e y w o r d s ：i l l c o n d i t i o n e dm a t r i x ，c o n j u g a t eg r a d i e n tm e t h o d ，r e g u l a r i z a t i o n ， o r t h o g o n a l i z a t i o np r e c o n d i t i o n i n g i i 曩，偿噜 、， 目录 目录 第一章引言1 1 1选题背景和意义1 1 2 迭代法2 1 3预处理技术7 1 3 1 预条件技术简介7 1 3 2 预处理方法的类型8 1 4正定矩阵简介9 1 4 1 矩阵的二次型1 0 1 4 2 正定矩阵1 l 1 5本文的工作1 2 第二章改进的正则化共轭梯度法1 3 2 1 正则化共轭梯度法1 3 2 2 改进的正则化共轭梯度法1 3 2 3 数值实验2 2 第三章最小二乘问题的预条件技术2 6 3 1 最小二乘问题的简介2 6 3 2 正交化预处理技术：2 7 3 3 最小二乘问题的正交化预处理正则化共轭梯度法2 9 致谢3 3 参考文献j 3 4 攻硕期间取得的研究成果3 6 i i i 第一章引言 第一章引言 本文研究的对象是大型稀疏线性方程组 a x = b a = ( a o ) r “，x ，b r “ 此方程组的求解问题是一个非常实际的问题，它既涉及数学理论方面的研究，也 涉及工程设计方面的应用，许多计算数学问题最终都要归结为线性代数方程组的 求解问题，或者是与矩阵的特征值相关的矩阵计算问题，而这部分通常是数值计 算中最耗时的一部分。尤其当系数矩阵a 的阶数比较大时，这个看似简单的数值 问题，却给计算数学带来了很大的挑战。 1 1 选题背景和意义 众所周知，对大规模稀疏线性方程组的求解算法的研究是数值计算领域的一 个重要研究方向。已经成为电路的设计和计算分析、电力系统网络、化学工程进 程、经济模型、生物学、现代物理学等领域处理数学问题中不可缺少的强大工具。 到目前为止线性方程组的求解有直接法和迭代法。直接法是基于高斯消元的 方法把系数矩阵分解成为易于求逆矩阵的一种方法，该方法得到了广泛的应用， 特别是它的可靠性是我们所关注的。在系数矩阵的阶数比较小时，直接法取得了 很好的效果，但是对具有成千上万甚至是上亿个未知量的大型线性系统的求解， 直接法的效果是差强人意的，特别是三维空间中的偏微分方程的离散化问题。迭 代法比直接法需要更少的存储和更少的计算( 尤其是当要求低精度近似解的时 候) ，但是迭代法不具有直接法的可靠性，而且一般的迭代法进行求解时收敛速度 太慢，在某些应用中甚至不收敛。由于迭代法的收敛速度与系数矩阵的谱性质有 很大的关系，于是为了减少迭代时间需要对系数矩阵进行预处理，使得线性方程 组的稀疏矩阵的谱相对集中，或者把矩阵的条件数降低之后再利用迭代法进行求 解。 预处理就是关于把当前的线性系统转化成另一个对迭代求解具有更好性质的 线性系统。预条件子就是一个实现这种转化的矩阵。一般来说，预处理试图去改 电子科技大学硕士论文 进系数矩阵的谱性质。对于对称正定矩阵( s p d ) ，共轭梯度法的收敛率是依赖于 系数矩阵彳的特征值分布的。理想的情况是，预处理矩阵有一个更小的谱条件数， 或者预处理矩阵的特征值凝聚在1 的附近。对非对称问题来说，情况是相当复杂 的，系数矩阵彳的特征值并不能描绘出非对称矩阵迭代的收敛性。然而，远离零 的凝聚谱通常会产生快速的收敛，尤其是当预处理矩阵接近一般化的时候。 大型稀疏线性方程组的求解技术的研究是现代计算数学的主要研究课题之 一，根据系数矩阵的特征进行构造高效的预条件子，结合强有力的迭代法，是当 今数值计算研究的焦点之一。 1 2 迭代法 线性方程组的求解方法一般分为直接法和迭代法【15 1 。直接法是基于高斯消元 的，对系数矩阵进行分解，一般稀疏性是无法保证的，而且随着系数矩阵的阶数 增加，所需的浮点运算量，内存量急剧增加，因此直接法只针对于大中型矩阵比 较有效。对于超大型矩阵通常采用迭代法，迭代法一般分为定常迭代法和非定常 迭代，定长迭代法是基于矩阵分裂的，不妨假设系数矩阵彳有如下分裂 a = m n ，m 是非退化矩阵， 则系数矩阵爿所对应的线性方程组a x = b 的迭代格式为： m x 5 “= n x 。+ b ，s = 0 ，1 。r l 其迭代矩阵为m _ 1 ，采用不同的分裂方式就会产生不同的m ，m 的不同就对应 不同的迭代法，比如当m 为以矩阵么的对角元为对角元的对角阵时就形成了 j a c o b i 迭代【1 9 】。同理g u a s s s e i d e l 迭代，松弛迭代法，超松弛迭代法等都是根据m 的不同而形成的迭代法，它们都是比较经典的定常迭代法，它们的数学形式非常 完整，但是收敛性有时不好判断，尤其是松弛迭代法，超松弛迭代法等收敛参数 不好确定。而且当矩阵的阶数比较大时，定长迭代法一般是无能为力。近年来， 随着科学计算技术的发展和探索，出现了一些新的定长迭代法，g o l u b 和白中治 针对非h e r m i t i a n 正定线性方程组提出的p s s 迭代方法就是其中的一个。对数值 计算中非h e r m i t i a n 正定线性方程组的求解产生了积极的影响。 非定长迭代法k r y l o v 子空间方法，是基于投影方法求解大型稀疏线性方程组 2 第一章引言 的强有力的算法。对于n 阶线性方程组 a x = b ， 其中a 是大型稀疏非奇异方阵。设初始解为x o ，定义- - b - 如为残量。用k a y l o v 子空间方法迭代m 步产生扰维的k r y l o v 子空间如( 彳，) - s p a n ( r o ，a r o ，a 一1 ) 和近似解z x o + 疋并满足p e t r o v - g a l e r k i n 条件 上厶， 其中l 是一个m 维的子空间。k r y l o v 子空间方法的本质就是逐渐扩大( 仿射) k r y l o v 子空间并不断求解它的正交基，选择不同的乙和不同的基向量计算方法将 会产生不同的算法。当选择乙= 么k 时，将使近似解的剩余2 一范数极小，即产 生最：j , - - 乘问题的算法，例如g r ，g c r ，g m r e s ，o r t h o d i r 等等。当选取 l = k ，则可导致一类g a l e r k i n 型算法，例如c g ，f o m ，o r t h o r e s 算法等等。 l 还可以选定其他子空间，例如k m ( 么r ，) ，k ( a r , a ，a r r 0 ) 等等并且建立相应的 算法。从数值稳定性，健壮性，并行性，存储量，计算量等等方面考虑，c g ， b i c g s t a b 和g m r e s 法是一般情况下是比较理想的。 共轭梯度法简称c g 法，其思想源于极小化范数函数【1 4 】。给定一个函数 妒( x ) = 互1 x r a x _ x r b 么是正定方阵 求其极小值，根据连续函数极小值的求解方法，该问题等价于其导数为零的极值 点的求解问题，即求解a x = b ，因此共轭梯度法的最小化么可定义为： i i x i x 吧= ( 五一x ，彳( 薯一x ) ) 薯墨( 么，r o ) 向量关于a 共轭：对于正定矩阵么，刀维非零向量p ( ，p ( 2 1 ，p ( h ) 满足 ( p ，和) = o ，v i ，j ，f ，则称p ，p ，p 相互a 共轭或者a 正交。 p ( ，p ( 甜，p ( 月) 的线性无关性不难证明，因此如果x r “是方程( 1 ) 的解，p r 4 电子科技大学硕士论文 是任意向量，则x 。一x o 可以表示为) 的线性组合，即工一p = 吼为常 数。从而 ，一( 0 ) ：6 一瓴：( x * - - x 0 ) = 羔却 分别用p ( ，p ( 引，p ( h ) 对上式做内积，则 故若取 则 铲鼢 k = 石。+ 口，p ( ， x ( m ) = x ( 。+ + l p ( 五+ 1 ) ， ”) ：， 这说明若用上式迭代法求方程组( 1 - 1 ) 的解，则最多经过，z 次即可得精确解x ， 这里算的都是精确的，没有舍入误差，设尸( 。) ：6 一血( ) 为k 次迭代的残差 且 考虑二次型 七 ，( = ，叭一口f a p ， ，( 删= ，( “一a k + l a p ( 州 日( x ) = ( 么( x x ) ，x x ) 4 第一章引言 ：窆( 薯一# ) ( 一彳) i , j = l 由于么对称正定性，显然当x ：x 时，日( 工) 取得极小值，不妨假设已知p ( ) 和 x ( k - 1 ) ，现在要求吃使得日( x ( k - 1 ) a k p t ) 取得极小值。h ( x ( k - o + 瓯p ) 关于 求导，令其等于零，可以解得 口，：(兰【三：二三!：!：竺!：!：幽 吼2 万移广2 网 需要确定p ( 1 1 ，p ( 2 1 ，p ( ，也就是说有了x ( 。) 如何去确定p ( ，有了x o ) 如何去 确定p ( 2 1 ，不妨假设已经得到石( ，p ( t 来确定p ( m ) ，如果取p 【为日( x ) 在x = x 。 处的负梯度方向，即p ( m ) = ，( 。) + 展+ 。p ，此处展+ 。为一待定的常数，由于要求 p 砷) 与彳正交，故上式两边用却做内积，得 一黼 不难证明右端等于一百r 嘲( - o , r ( k - o ) ，即 一溯， 当要求解的线性方程组是对称正定线性方程组，标准的迭代方法就是共轭梯 电子科技大学硕士论文 度法。共轭梯度法有许多种变形算法，但是不管怎么变形，它的三条性质总是尽 可能地被保留下来【l 】。 第一，每次迭代都是在k r y l o v 子空间k 。( 么，r o ) 暑s p a n ( r o ，a r o ，么”1 ) 上； 第二，残差向量相互正交； 第三，残差向量的三次循环，使得共轭梯度法在存储计算上都非常节省。一 个较一般的预条件c g ( p c g ) 算法可以表示为 x o = 0 ，日= r o = b ，屈= 0 ，k = 1 ，2 ， 解方程组m z 川= r k 反= ( z k - ir x 1 ) ( k 1 ，珞一1 ) ， 足= z 川+ 尾足_ l ， = ( 乙书乍一1 ) ( 足，么足) ， = x k l + 口k & ， r k = k l a k 么足。 当| 珞i 满足某种条件，则停止。这里当m = ，时，就是古典的c g 方法。 从p c g 算法的收敛性不难发现如下定理： 定理1 2 1 【2 1 经过共轭梯度法估计出来的值和真实值之间的关系式为 i i x ，一工1 | 2 i ( 石4 ；+ - 1 割 x 0 - - x * 这里r = k ( m _ 1 枷九洒( m _ 1 栅，k ( m - 1 句和 丸妯( m 一么) 表示m - 1 a 的最大和最小特征值。 证明略。 定理给出的估计是粗糙的，而且实际计算时其收敛速度往往要比这个估计快 得多，但是它却表明了共轭梯度法的一个重要点的性质：只要线性方程的系数矩 6 第一章引言 阵是十分良态的，则共轭梯度法就会收敛得很快。即使系数矩阵不是良态的，我 们也可以通过引入预条件子肘一，进行预处理使原有的线性系统转化为另一个系 数矩阵比较良态的线性系统。方程组的病态问题严重影响了计算结果的准确性和 可靠性，人们一直在寻找有效的解法。 因此预条件技术还是很有必要的。 1 3 预处理技术 1 3 1 预条件技术简介 对于，z 阶线性方程组 a x = b ，a r ”，x ，b r ” 其中彳是大型稀疏非奇异方阵，用k r y l o v 子空间法进行求解的时候，有时其收敛 速度特别慢，甚至不能接受。这时候需要对原系统进行预处理来降低它的条件数， 使它的谱相对集中，进而加速迭代，因此需要构造一个矩阵p 一- 使得原问题转化 为 p a x = p b ， ( 1 2 ) 其中预处理后的系数矩阵p 一1 4 具有较好的条件数，( 1 2 ) 就称为左预条件【3 】相 应的也可以右预处理系统( 1 1 ) 使之成为如下等价形式 a p y = b ， 其中y = p x ，这样的矩阵p 称为预条件矩阵或者预条件子。有数学家还提出了分 裂预条件，即 暑。么巧1 y = 写b ，x = 巧1 y ， ( 1 3 ) 这里的预条件子是p = 置丘，称为预条件矩阵。 引入预条件矩阵的目的在于减少迭代次数，最终的目的在于减少运算时间。 7 电子科技大学硕士论文 当然如果能并行计算预条件矩阵，那么效果将会更好。一个好的预处理子应该具 有如下两个性质3 】： 预处理后的系统应该容易求解。 预处理子应该较容易构造且应用预处理后的求解代价不能太高。 1 3 2 预处理方法的类型 比较常见的预处理技术主要有： 一不完全分解方法( i l u ) 2 3 】： 不完全l u ( i l u ) 分解方法是常用的构建预条件矩阵的方法。矩阵的么的不完 全分解通常是基于高斯消元法的。系数矩阵的分解过程中，在系数矩阵原来的零 元素位置上出现了非零元素，这些元素成为填充，这样就增加了我们的存储空间， a = l u + e ，e 为误差矩阵。这样我们将会得到简单和有用的预条件矩阵p = l u ， 这里和u 是系数矩阵的不完全( 近c a ) 分解因子。因此为了分解的稳定性和代 价方面考虑，我们需要把这些填充去除，去除的方法有如下几种：一是考虑填充 位置，二是考虑数值大小，三是同时考虑位置和数值大小。 不妨记矩阵a2 ( ) ，其中先固定一个子集p ，不妨记为零模式， p c ( f ，列f j ；1 f ，z ，p 通常为口 = 0 和非对角元，不完全l u 分解中因子 的填充只有在不属于p 时才不会被舍弃，用一个简明的式子表示就是： 旷r 嬲；茎； 当零模式就是真正意义上的零模式时，该分解过程就是i l u ( 0 ) 。 其次就是根据填充数值的大小来舍弃填充元。首先找到一个舍弃容忍值f ， 如果产生的填充元素的绝对值小于该f ，就把该填充元舍弃，否则保留。这种方 法的弊端是r 的大小不容易选取，还有保留的填充元多少无法确定，进而空间存 储不好控制。 最后就是s a a d 在文献 1 6 中提出的双重填充丢弃策略，记为i l u t ( f ，p ) 。事 先固定两个正数f 和p ，p 表示不完全分解产生的l 和u 每行中可以允许填充数 第一章引言 的个数，在每一步高斯消元中，对于大于f | fa ，f l ：的填充保留，在从这些保留元素 中最多选取p 个填充元。 最后在文献 2 2 中r c m i t t a a n d a h a 1 一k u r d i 提出结合图论的分解模式， 也就是说，我们首先取出矩阵的邻接矩阵，不妨记为b ，即把矩阵中原来的非零 元素记为l ，原来的零元素不变。然后让它自身相乘，直到b t ：口“- ，这是取出口 的稀疏模式，作为不完全分解的稀疏模式，这种稀疏模式值得思考，但是经过大 量的数值实验证明，它所针对的只是比较稀疏的矩阵的分解，不足以推广到比较 一般的稀疏模式。 二稀疏近似逆方法( s a i ) ： 稀疏近似逆预条件子具有天然并行性。该方法具有不完全l u 分解所没有的 优点，构造的预条件子也有自己独特的优势。稀疏近似逆按其求解方式的不同又 分以下三种情况： ( 1 ) 基于对8 胧一i l l f 极小值的求解来构造稀疏近似逆。s 为某种稀疏矩阵的 集合，1 1 1 l ，为矩阵的f r o b e n i u s 范数。由于0 化：刈；2 喜物一彳聊：，所以i l 唑：i l l ， 的极小化的求解就转化为n 个独立的线性最d , - 乘问题的求解，充分体现了稀疏 近似逆预条件子的天然并行性【4 】。 ( 2 ) b e i z i 等人提出的基于爿正交过程来求系数矩阵逆的稀疏近似分解的近 似逆技术，一般有f s a i ，a i n v 和s a i n v 等形式 5 1 。 ( 3 ) 基于矩阵么的不完全l u 分解来构造系数矩阵的稀疏近似逆。不妨假设 a l u ，令m ：f 1 u 一，m 就是系数矩阵的稀疏近似逆。 由于每种预条件技术都不是万能的，因此需要根据矩阵的结构和实际问题进 行分析，构造出高效的预处理矩阵。 1 4 正定矩阵简介 2 0 】 正定矩阵在矩阵论中占有十分重要的地位，在实际中有非常广泛的应用，最 初正定矩阵的研究是出现在二次型与h e r m i t e 型的研究中。 9 电子科技大学硕士论文 1 4 1 矩阵的二次型 任意一个方矩阵么的二次型瓜是一个实际标量，以三阶实方矩阵为例， 其二次型为： 工r 4 x = c 五，恐，屯， 三：三茎 兰 = 彳一恐五一屯五+ 4 x l x 2 + 7 + 6 x 3 x 2 + 2 x l x 3 + 5 x 2 x 3 + 3 = # + 7 + 3 9 + 3 x l x z + x l x s + 1l x z x s 这就是未知向量x 的二次型函数，因此称，出为矩阵a 的二次型。进而推广到n 阶实方阵。若x = i x l ，恐吒 7 ，么= ( ) 贝u - & y d i = nj = n x r a x = x f x j a i = 1 = l i = ni = nj = n = # + a u x ，x j i = 1 i = 1 扭户l 存在许多矩阵a ，它们的二次型，血相同。但是，只有唯一的对称矩阵满足 儿= 缸和，茎，和坼其元素为= 弛码= 如嗨) 卿“ 因此在讨论矩阵的二次型时，通常都是假设矩阵为实对称矩阵或者复共轭对称( 即 h e r m i t i a n 矩阵) 矩阵。 l o 0h一 口+ 向陆 一汹 + # 吒 胁随 = 第一章引言 1 4 2 正定矩阵 如果对于任意的非零向量x ，二次型x a x 0 0 ，则称次二次型为正定的二次 型，其对应的h o - m i t i a n 矩阵称为正定矩阵。 如果矩阵么是正定矩阵，则它具有如下性质： 矩阵彳的所有特征值都大于零。 所有的主子式都是正的行列式。 存在一个非奇异的，z 忍矩阵r ，使得么= 尺r 。 存在一个非奇异的t n 矩阵p 使得p m 4 尸是正定矩阵。 当一个线性方程组的系数矩阵是对称正定矩阵时，标准求解方法是共轭梯度 法。如果收敛速度不是很理想时，需要借助预条件技术。考虑对称正定矩阵的性 质，一般采取不完全c h o l e s k y 分解，或者对称超松弛迭代，但是这两种方法都有 局限性，它们一般对于对角占优或不可约弱占优矩阵很有效，另外不完全e h o l e s k y 分解往往会因为出现非正主元而导致分解失败。由定理1 2 1 可知共轭梯度法的收 敛速度与系数矩阵的条件数有关，因此可以从降低系数矩阵的条件数出发，构造 高效的预条件子。 对于任意一个矩阵彳，它的的条件数定义为j j ( 么) = 怕。1 l | | i 么l i ，其中| | i l 表示范 数。如果范数的定义是二范数的话那么条件数就等于尼( 彳) = 昙：芒筹，进而当彳是 对称正定矩阵来说，它的条件数就是最大特征值和最小特征值之比，即 尼( 彳) = 麦i 旨。若尼( 彳) 很大，则称a 是病态的，彳x = 6 是病态方程组。 在工程计算上来说对于有些矩阵，矩阵中某个元素的一个很小的扰动，会引 起最后计算结果的很大差别，甚至会面目全非，工程上称这种矩阵为病态矩阵。 在进行差值近似逼近的时候往往会产生病态矩阵。希尔伯特矩阵以简记为h i l b e r t 矩阵，矩阵元素h 0 = _ _ ，f ，j = 1 ，2 ，z 。很明显h i l b e r t 矩阵是对称矩阵， 另外， 电子科技大学硕士论文 x 7 以x = 毫薯_ = 毫+ 薯t 出= 毫( j ：) 2 出 。 所以h i l b e r t 矩阵是对称正定矩阵。由m a t l a b 计算可以看出随着阶数刀的增加， 条件数也成指数比例在增加，严重的病态性使得h i l b e r t 线性系统的求解一直是比 较棘手的问题。在图像处理、解卷积、模型参数估计等许多领域都需要求解病态 方程组，因此病态方程组的求解还是很重要的。 注：下面提到的范数均为二范数。 1 5 本文的工作 目前关于正定矩阵的研究已经非常成熟了，共轭梯度法是它的标准迭代方法， 但是当矩阵的条件数非常大时，有时共轭梯度法也无能为力。白中治在文章 8 提 出一种正则化共轭梯度法，首先通过正则化过程把线性方程组的系数矩阵的条件 数降低，然后再用共轭梯度法。基于这种思想，本文的主要工作是改进正则化共 轭梯度法，把它应用于希尔伯特线性系统。 1 2 第二章改进的正则化共轭梯度法 第二章改进的正则化共轭梯度法 2 1 正则化共轭梯度法 对于对称正定线性方程组的标准迭代法就是共轭梯度法，但是当线性系统比 较病态时，必须借助预处理技术，构造高效的预条件子。白中治在文章 8 提出求 解病态线性对称正定系统的正则化共轭梯度法。该方法首先通过合适的参数把线 性系统进行正则化，然后用共轭梯度法逼近正则化后的线性系统的近似解，即把 线性系统( 1 1 ) 正则化为 ( + 彳) x = q x + 6 ( 2 1 ) 其中，是单位矩阵，i r “一，q 0 ，q 称为正则化因子。通过正则化过程，其条 件数满足如下关系式 叱川) = 鬻描 0 ，只要矩阵a 的条件数不小于 k ( 么) = 阜 嘉+ k ( q d + 么) g + 以 垡互 t c ( q d + a ) 差2 n - 拳1 ：雩型l 。 犁：j 牲 t o l l v ( 。) 和z k 9 如果，= 1 就令；- - - - 0 和p ：2 厂；否则 计算= p ( h ) p ( m ) 和p = r + p p 1 0 计算w = q d p + a p 1 1 1 2 1 3 1 4 计算口= 户( h ) p r w 计算y = y + o t p 计算r 2 ，一o t w 计算p ( ，) = ；和v ( ，) ：万 电子科技大学硕士论文 1 5 循环出来令，= ，+ l 1 6 结束循环 1 7 令x ：2 y 1 8 令k ：= k + l 1 9 转到循环5 2 0 继续 2 1 结束 第八行到第十六行其实就是第k 次外迭代，即经典的共轭梯度法应用于线性系 统( 2 3 ) ，等价于g = 0 ，只要令t o l k = t o l l 和k = k 即可。 对改进的共轭梯度法的算法复杂度进行分析，我们不难看出只需储存五个向量 工yp ，w 和尸。每次内迭代进行两个矩阵向量的乘积( q d p ，a p ) ，两个内积( 一个是 p r w ，另一个是p 7 = ：) 。- - + u + e v 的运算形式，其中“，1 ，是向量，是常数。 每个外迭代需要一个矩阵向量乘积和一个u v 形式的运算( 残差向量r = b a x ) ， 一个内积( p 。= i ) 。因此不妨假设矩阵么r 蝴的第f 行的非零元素个数缈( f ) ， 则每次内迭代共轭梯度法的复杂度： 对应的外循环需要 = 2 ( 2 c o “- 1 ) + 7 n + l = 4 c o “+ 5 n + l i = 1 i - - 1 形咿= ( 2 c o “- 1 ) + 3 n - 1 - - 2 e c o u + 2 n 一1 i = 1i = 1 另外假设改进的正则化共轭梯度法的第k 次迭代需要m ( t ) 步内共轭梯度法达到终 止条件t o l l 。那么改进的正则化共轭梯度法第k 次迭代的复杂度就是 陟龆g ：，z ( ) 矽品+ w o 。舯：( 4 m ( t ) + 2 ) 主卯( f ) + ( 5 所( i ) + 2 ) 靠+ 聊( 一l i - - 1 特别当c o ( ) = c o ( i = l ，2 ，咒) 和m ( t ) ：m ，那么改进的正则化共轭梯度法每次迭代的 总的复杂度将是 1 6 笙三兰整垄塑垩型些茎翌堡堡竺 一 _ - _ _ 一 w m r c g = ( 9 m + 4 ) ，z + 朋一1 首先，为了简洁起见，引入下面将会反复用到的一些记号，以便文章的整齐 ；( g ) = 。r a 。，。i 尸n 。，：。m 。a j x 。，i p ( 女( z ) i b ) 2 c 等群 2 赤+ 是厕以扒 k ) 2 荭q 瓦+ 丧厕似b ) 投加东k + 乏x 厕拨g ) ， 扩) ( 加荭q 瓦+ 乏x 厕q 臼) 不妨规定对任意向量z 尺一，它关于矩阵么的范数定义i | z i l = 压。 引理2 2 1 1 9 1 如果a r 肼”是对称正定矩阵，则对于任意向量 降1 1 2 ：l h i 一 并且 厕爿 - h ：- o ，则有 以v ) ，鼓批v ) 和拨v ) 扩。 引理2 2 3 i s 如果么r 是对称正定矩阵，x 是线性系统( 2 - 3 ) 的真实解， 初坂诀代向量0 0 ) # 驴，则足步迭代之后，线性系统( 2 3 ) 的第k 次近似解又。) 满 电子科技大学硕士论文 x k ) - x * i i - 婶( o ) l i x c 。，一x i l 爿y 似，( o ) i f x c 。，一x 0 彳 由上述引理，对改进的正则化共轭梯度法进行收敛性分析，得出了正则化因子的 上界，证明方法参考文献 8 。 定理2 2 2 如果a r 是希尔伯特矩阵，q 是非负常数，x + 是线性系统( 2 3 ) 的真实解，初始迭代向量x ( o ) r 一，则k 步迭代之后，线性系统( 2 3 ) 的第k 次 近似解石( q 满足： 卜血”t ，2 - ( g ) l i b - a x ( k ) i l - 8 ( ) ( 冲一驯l ： i i x c k + - x i ：；m p ( g ) j | x ( k ) - x * 8 ：乡( j ，r ( i ) ( g ) l i x e k ) _ x l l ： 证明：记 6 ( 。) ( g ) = g 眈( ) + 6 么( g ) = 么+ g d 设工( 。女) 是线性系统( 2 3 ) 的真实解，满足 么( g ) x ( ，t ) ：b ( k ( g ) ，且y ( t ，m ) 最终内迭代在第七次外迭代之后的值，那么由引理( 2 。2 。3 ) 知 0 y ( 女 一q ) 一工( ，女l l 。，；一”c g ，l i y ( t 0 ) 一x ( 女8 。， 另外由于 y ( 女。) ：x ( 和1 ，( 枷) ：工( m ) ，则 8 z c t + t ，一x c i i 一”) ( g ) l i x c 女，一x t ，女，0 。， c2 4 ) 记改进的共轭梯度法第k 次外迭代的残差为，- ( t ) ，即，( ) = 6 一a x ( 。) 又 工( 。+ 1 ) 一工似) ：a - i ( 彳x ( 。+ 一a x ( ) ) = 彳一1 ( r ( ) 一，( 。+ 1 ) ) ( 2 5 ) 由( 2 5 ) 和直接运算知道 彳( g ) x ( + 1 ) 一6 ( 。) ( 9 ) = ( g d + 彳) x ( 。+ 1 ) 一( q d x ( ) + 6 ) 第二章改进的正则化共轭梯度j 丢 = q d ( x ( 。+ 1 ) 一工( 。) ) 一，( + 1 ) = q d a 一1 ( r ( ) 一，( ) ) 一，( 川) = q d a 一1 一( i + q d a 一1 ) ，( + 1 ) = q d a 一1 ，( 。) 一a ( q ) a 一1 r ( 州 因此 ) = 彳( g ) 一1 4 捌妒+ ( 批g ) 一么( g ) ) = 么( g ) 一1 d r k ) + a ( b 女( g ) 一彳( g ) x + 1 ) ( 2 6 ) 和 ，一】：( i + 1 ) = a 一1 r ( i + 1 ) 因为 = 彳( g ) 一1 q d ( x - x ( k ) + b ( g ) 一么( g ) x + l ( 2 - 7 ) ， ) ：6 一a x ( i ) ：( q d x ( ) + 6 ) 一( q d x ( ) 地( ) ) = 6 ( ) ( g ) 一a ( q ) x ( ， 由( 2 4 ) 和简单的运算，得到 0 6 ( 女( g ) 一a ( q ) x ( k + oi l ：= 0 么( g ) ( 彳( g ) 一16 似( g ) 一彳( g ) x 。) 0 ： 页丽l i x p j 一x 似+ l 0 一。， 4 2 , 。x a ( q ) y ( 一q ) ( 非h t 凯。， 芦n ( 巾( 耐棚0 ： ：x x ：( a ( q ) ) r “m 。1 1 6 砷( g ) 一彳( g ) 工( t l l ： ：瓜硒1 ，i i ： 在式子( 2 6 ) 和( 2 8 ) 两边同时取二范数，并由引理2 2 1 知 1 9 ( 2 - 8 ) 电子科技大学硕士论文 0 r 似+ 1 8 ：g d0 彳( g ) 。10 ：9 ，似0 ：+ 0 彳( g ) 。1 么i l ：