（计算数学专业论文）richardson迭代算法的研究.pdf

中文摘要 摘要：研究r i c h a r d s o n 迭代算法的收敛性在理论和实践中都非常重要。本文用奇 异值分解( s v d ) 得到了r i c h a r d s o n 算法的迭代表达公式，并建立了算法收敛的充 分必要条件。通过对松弛参数的选取研究其迭代的收敛性和收敛速度。本文不仅 对松弛参数为固定的情形建立算法收敛的充分必要条件且对松弛参数的选取是复 杂的，在某一区间上变化时的情形研究迭代的收敛性和收敛速度。通过数值实验 得出结论：当松弛参数选取为系数矩阵的特征值分之一时r i c h a r d s o n 算法收敛。 当松弛参数的选取是变化的，且变化区间为1 k 寸2 k 时可通过调整步长来提 高收敛速度。 关键词：r i c h a r d s o n 算法：奇异值分解( s v d ) ；松弛参数；收敛速度； 分类号：0 2 4 1 6 a b s t r a c t a b s t r a c t ：s t u d yt h ec o n v e r g e n c eo ft h er i c h a r d s o ns c h e m ei si m p o r t a n ti nt h e o r y a n dp r a c t i c a l i t y u s i n gt h es i n g u l a rv a l u ed e c o m p o s i t i o n ( s v d ) ，w ed e r i v ea l li t e r a t i v e r e p r e s e n t a t i o nf o r m u l af o rt h er i c h a r d s o ns c h e m ea n dc o n s e q u e n t l ye s t a b l i s ht h e n e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n sf o ri t sc o n v e r g e n c e i nt h i sa r t i c l ew es t u d yt h e r e l a x a t i o np a r a m e t e r ss e l e c t i o ni nt h er i c h a r d s o n i t e r a t i v ea l g o r i t h m s ，a n ds t u d yt h e c o n v e r g e n c ea n dc o n v e r g e n c er a t eo ft h ei t e r a t i v ea l g o r i t h m sw h e nr e l a x a t i o np a r a m e t e r i si n v a r i a b l e w ee s t a b l i s ht h en e c e s s a r ya n ds h 佑c i e n tc o n d i t i o n sf o ri t sc o n v e r g e n c e w h e nr e l a x a t i o np a r a m e t e r si na ni n t e r v a ln o ti n v a r i a b l e o u rr e s u l t sa l l o wt h e r e l a x a t i o np a r a m e t e r st ob ec o m p l e x m o r e o v e r , i ti sf o u n dt h a tt h er i c h a r d s o ns c h e m e c a nc o n v e r g ew i t h i nf i n i t ei t e r a t i o n sw h e nt h er e l a x a t i o np a r a m e t e r sa r ec h o s e nt ob et h e i n v e r s e so ft h en o n z e r os i n g u l a rv a l u e s w h e nt h er e l a x a t i o np a r a m e t e r si n c r e a s e m o n o t o n o u s l yf r o m1 a 咄t o2 a n dt h es t e pl e n g t hi sa d j u s t e dp r o p e r l y , t h e i r e r a t i v ec o n v e r g e n c er a t ec a nb ei m p r o v e d k e y w o r d s ：r i c h a r d s o n - i t e r a t i v ea l g o r i t h m ；s v d ；r e l a x a t i o np a r a m e t e r ； c o n v e r g e n c er a t e ； c l a s s n o ：0 2 4 1 6 索引 涵义 月值域 a 零空间 奇异值分解 普半径 代数重建算法 每次迭代的松弛参数 系数矩阵的最大特征值 系数矩阵的最小特征值 系数矩阵 a 共轭转置矩阵 矩阵a 的2 一范数 向量 错 州 m 5|耵肿五 彳 批 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：她￥ 签字日期： 2 留年6 月牛只y 月 、f d 莲年 协 曲 ，派 钟 名 期 签 日 师 字 导 签 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：签字日期：年月 日 2 7 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：签字日期：年 月日 致谢 本论文的工作是在我的导师渠刚荣教授的悉心指导下完成的，渠刚荣教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三年来 渠刚荣老师对我的关心和指导。 渠刚荣教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都给 予了我很大的关心和帮助，在此向渠刚荣老师表示衷心的谢意。 渠刚荣教授对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷 心的感谢。 在实验室工作及撰写论文期间，孙杰同学对我论文中的一些细节问题的研究 工作给予了热情帮助，在此向他们表达我的感激之情。另外也感谢我的父亲和我 的母亲，他们的理解和支持使我能够在学校专心完成我的学业。 1 引言 大型线性方程组的求解是计算数学中的重点研究方向之一，科学和工程计算 中的许多重要领域，工程设计、图像处理、模型参数估计等许多领域的数值计算中 都是通过适当的离散化，将原方程化为线性方程组 a x = b ( 1 1 ) 图像重建常常被转化为线性方程组( 1 1 ) 的求解问题，其中b 是被采集的投影数 据，彳是投影系数矩阵，j 是图像基函数。文献 1 研究了迭代松弛参数的选取在 一般l a n d w e b e r 迭代算法，包括同时迭代算法( 简称s a r t 算法) 和块迭代算法中 的收敛性问题。文献 2 用矩阵的奇异值定理研究了l a n d w e b e r 迭代算法对更广泛 松弛参数选取的收敛性。使用新算法求解线性方程组，首先要选择松弛参数，松 弛参数的选取直接影响到方程组的收敛及收敛速度。恰当的松弛参数能大大提高 计算效率关于如何选取最佳松弛参数的问题，至今仍没有有效地解决。目前， 在实际计算中，采取试算的方法寻找较好的松弛参数。在今后的研究中，将致力 于这个方向。 判断一个计算方法的好坏，可以用算法是否稳定、解的精确程度以及计算量、 存储量的大小等来衡量。然而，同一种方法用于不同问题，效果却可能相差很远， 这就涉及到问题本身的状态，而线性系统又包括常态线性系统和非常态线性系统， 在常态情况下，线性系统问题的解决非常简单容易。但在许多问题中，人们经常 会遇到非常态线性系统，即病态线性系统问题，且其危害性是非常严重的病态 线性方程组，因其矩阵的条件数较大，当原始数据有较小扰动或在计算过程中因 舍入误差的存在都可能引起方程组的不稳定，难以控制其误差的传播，更可能导 致解的严重失真正是由于这个原因，病态方程问题引起了相关领域科技人员的 广泛关注。l f r i c h a r d s o n 提出了一种方法来求解离散化得到的系数矩阵为正定 矩阵的线性代数方程组l a n d w e b e r 算法与r i c h a r d s o n 算法不同，可以应用于不定 适线性系统中且系数矩阵彳可以为任意矩阵。 本文用奇异值分解得到了r i c h a r d s o n 算法的迭代表达公式，建立了算法收敛 的充分必要条件。通过数值实验，研究了r i c h a r d s o n 算法中松弛参数的不同选取 对迭代算法的收敛速度的影响。选取松弛参数为入( 0 入2 ，入r ) 乘以系数矩 阵最大特征值分之一的收敛效果比直接选取为最大特征值分之一要好，当松弛参 数的选取是变化的，且变化区间为l 旯一一2 厶瓠时可通过调整步长来提高收敛速 度。本文通过试验发现：当松弛参数选取为系数矩阵的特征值分之一时，有限步 迭代之后可收敛到精确解。 2 离散不适定性问题 数学问题的适定性概念( 解的存在性、唯一性和稳定性) 是由j h a d a m a r d 首先 提出的，它使微分方程的研究前进一大步受其影响，长期以来人们以为不适定 问题没有实际意义，近几十年来，在科研、生产等方面，已遇到愈来愈多的不适 定问题急待解决，对不适定问题的深入研究已被列入日程，而且越来越引起各方 面学者和工程技术人员的密切关注，本文对线性方程组的不适定问题进行探讨。 2 1 离散不适定性问题 离散不适定性问题精确地说就是解的存在性、唯一性和连续性至少有一个不 满足，我们就称该问题是不适定的。下面我们用简单的数学语言来描述之 对于线性方程组： a x = b ( 2 1 ) 或最d , - 乘问题： m j n t a x - b 0 ( 2 2 ) 其中a k m x n ，m n ，x k ，6 k ， 假设矩阵a 的奇异值分解为【3 】： a = u z v r = “，雎 ( 2 3 ) 其中以为奇异值l 2 纨0 以递减顺序排列，= d i a g ( l ，2 ，) ： 为右奇异向量，相互正交，v = ( 1 ，。，1 ，：，) k m ， ，为左奇异向量，相互正 交，u = ( “。，“：，“) k 胁则问题的最小二乘解( 若存在的话) 可表示为 4 】： 舻善学 亿4 ， 有了上述基本问题与概念，下面我们给出离散不适定问题的基本概念：若矩 醐的奇异值满足下述两个条件【5 】： 1 彳的奇异值逐渐趋向于零； 2 彳的最大奇异值与最小奇异值之比。伽较大。 则称上述两个问题( 2 1 ) ，( 2 2 ) 为离散不适定问题。条件2 说明，矩阵a 的条件 数( 记为c o n d ( a ) = “) 非常大，因此方程组是病态的，解对数据b 的敏感度非 常高；条件l 说明，我们无法找到一个良态的方程或秩确定的矩阵去逼近原始问 2 题及其矩阵。 不适定性问题的上述特征并不意味着不适定性问题不可解，而是说传统的线 性代数的方法，如高斯消去法、叫、c h o l e s k y 、q r 分解法等无法直接应用于问 题的求解，因为这些方法所求得的解可能与问题的真实解相距甚远，使得这些解 对实际问题来讲毫无意义。事实上，从表达式( 2 4 ) 可以看出，造成问题( 2 1 ) ，( 2 2 ) 不适定的主要原因是其系数矩阵彳的部分奇异值较小，当数据项6 有一个较小的 扰动时，较小的奇异值对这一扰动具有放大作用，因此，使得所求的解较大地偏 离原问题的真实解，本文用r i c h a r d s o n 算法研究这类不适定性问题的收敛性。 2 2 奇异值分解 设矩阵a k 胁的奇异值分解为式( 2 3 ) ，与之相联系离散不适定问题的奇异 值和奇异向量具有下述特征【6 】： 奇异值，0 逐渐下降且趋于0 ，且在下降期间没有明显的跳跃；当矩阵彳 的维数增加时，小奇异值的个数也将随之而增加。 随着下标f 的增加，所逐渐下降，其所对应的左右奇异向量“，的元素 之间将有较多的符号变化。 尽管上述两个特征在许多实际离散不适定问题中经常出现，但是验证这两个 条件确是非常困难的，有时甚至是不可能的。 下面我们从矩阵a 的奇异值分解来考察矩阵a 的病态特征，若矩阵a 的奇 异值分解式为( 2 3 ) ，则有下述关系式成立： a v f = 麒“i f = 1 , 2 ，n( 2 5 ) i l a y f0 ，= , i t ， 扣1 , 2 ，n( 2 6 ) 由这两个式子可见，当奇异值以与1 1 4 ，= “相比较小时，矩黼的列向量的线性 组合a v ，的2 范数( = ，) 较小：换句话说，矩阵a 的列向量之间存在近似的相关性， 也就是说矩f f - a 是近似于秩亏的，小的奇异值，对应的左奇异向量，几乎在矩黼 的零空间n ( a ) r o 。由此可见，离散不适定问题的系数矩阵具有严重的病态特性。 另一方面，从矩阵a 的奇异值分解还可以分析解对数据项b 的依赖特性，对于任 意向量，由奇异值分解可知工= ( ，j 工n 考虑映射： 卫可 一 a x = 以( 1 ，? 工) “t ( 2 7 ) 由于被较小的奇异值乘，相对于低分量而言，高分量被严重削弱；作为上述映射 的逆问题，即根据血= b 或哑n 0 血一圳拙，其效果将相反，也h 1 3 b 中的高分量被 加强，低分量被削弱【7 】 3 迭代算法的介绍 3 1r i c h a r d s o n 迭代算法 3 1 1松弛参数为固定时r i c h a r d s o n 迭代算法收敛性分析 r i c h a r d s o n 迭代算法是解系数矩阵为对称正定阵的大型线性方程组的有效方 法，考虑线性方程组a x = b 的求解问题，其中彳是给定的阶对称正定阵，b 是 给定的维向量，x 是待求的维向量，r i c h a r d s o n 迭代算法的迭代公式为： 工4 + 1 = 石4 + 以( 6 一a x “) ，刀= 0 ，1 ，( 3 1 ) 兄。是松弛参数，工( o 是初始值，r i c h a r d s o n 迭代算法公式可以变化为： x 4 + 1 = ( ，一a a ) x ”+ 乃6 ，刀= 0 ，3 2 ) 设迭代矩阵丁= i 一以彳矩阵a 的特征值为以则r 的特征值为；= 1 2 , ，；设 矩阵a 为正定矩阵，口分别为特征值上下界，0 口以，显然为使 p ( 丁) = m a x 1 一九“i l 必须而且只需0 以 2 p ，于是我们得到以下定理： 定理3 1 ：设a 为正定对称矩阵，其特征值的上下界分别为，口则当 0 以 2 f l时解( 1 1 ) 的r i c h a r d s o n 算法收敛 8 】。 定理3 2 ：解方程组( 1 1 ) 的迭代法( 3 1 ) 对任意的b r ( a ) 及初始向量工o 均收 敛的充分必要条件是p ( t ) 0 由上可知 彳：u r o v 【oo j 称为a 的奇异值分解。鸬o = 1 , 2 ，厂) 称为彳的正奇异值，u ( r ) 的第f 列称为 彳对应儿的左( 右) 奇异向量。 我们研究彳为半正定矩阵( 正定是半正定的特殊形式) 时r i c h a r d s o n 迭代算 法奇异值分解的表达式，由奇异值分解定理知存在正交矩阵u u a u 。= d i a g b u i i ，以i o ，o ) l 以 0 是彳的特征值，t 是k 阶单位矩阵，每个段的代数重度为p 设u = ( ”i l ，”l 毋，u s ls “s p l “l 甜q ) ，u k j 是以，k = l ，s 相应的特征相量， “ ，k = l ，q 是0 相应的特征相量，因此材l i ，“l n ，”小u 印。，”i 一，u g 构成k m 的正交基。对于任意的b r ( 4 ) ，a x = b 存在解，假设 x - - - - - “茸+ 以“。- - - - x ，+ x 2 ( 3 8 ) k = lj = lk = l 由于x ，n ( a ) ， 5 j 6 = a x = 七量l 设迭代算法的初始值为 工p 晶 t2 一c 村“材 _ l l卧 q 工) - 艺p 可+ 以“i = + 嚣 k = l = l k = l ( 彳) 定理3 3 ：迭代算法在刀次迭代之后 证明： 用归纳法： 工( 1 ) = 工( o ) j 工佃= 工l + j - z k = l兀肘= l a ( 1 - 2 。儿) ( c 灯一弦杉 j = l 如果n = l ，由( 3 1 ) ，( 3 8 ) ，( 3 9 ) ，( 3 1 0 ) + 6 一丑血o ， 工：+ x ：+ 七= l k = l 。兰掣茸一，= l p i “灯+ 石p + x 1 一_ + j = l k = l 七= i sp k = j l + 工；o 一( 1 一丑) ( c 可一p 灯j 5 ， k = l j = l 假设n 时等式成立，以下证明n + l 时是否成立 j ( “+ 1 ) = j a 肌 七= l p i “可 j = l ( 3 9 ) ( 3 1 0 ) 艺+ 工一兀( 1 - l u 。) p k ( 一_ 眵+ 乃。p k “村 卢j月j k = l j = l k = l= l j = l j + l = 工。+ 工：们一兀0 k = lm = l 结论成立。 命题3 1 ：从定理3 1 可知 一( 而+ x o ) ) | l ：= 琴 i z i ( 1 一九心) 2 上= lm = l p 灯如茸 3 1 3 松弛参数为变化时r i c h a r d s o n 迭代算法收敛性分析 定理3 4 ：对于任意的6 r ( 彳) 和初始值工( 。) k ，b ( “) ) 收敛的充分必要 条件是! 鳃兀( 1 一九以) ，k - i ，s 存在。 对于任意的6 尺( 彳) 和任意的初始值x ( 0 ) k ，k n 收敛到而+ 是。的充分必要 条件是煅驵( 1 2 , 1 沪。扣1 ，一，s 6 灯 “ 村 p 爿 七 乒 元 一 可 ” 灯 c 闰 七 户 糊 抄 一 0 司 以 、 一 0 。兀 氖 i + 闩以 纠， 3 2l a n d w e b e r 迭代算法 3 2 1 最小二乘问题 我们已知正交直和分解为： k 盯= r ( a ) e 尺( 彳) 上，k = r ( a r ) o n ( a r ) 上 对于任意的6 k m ，b = b l + b 2 ，b l 尺( 彳) ，b 2 尺( 彳) 上 命题3 2 ： r ( a r a ) = r ( 彳) ，n ( a7 a ) = n ( a ) 命题3 3 ： 尺( 彳) 上= n ( a7 ) ，r ( a7 ) 上= n ( a ) 从以上可知 k = 尺( 彳7 a ) or ( a r 彳) 上 以下引入最小二乘问题的概念 定义3 1 ：给定矩阵a k 肌及b k 村确定x k 使得 a x i | 2 = ) 1 1 2 = 剜m i n 旷i b 纠i ： 该问题称为最小二乘问题，其中j 为二乘解，r ( x ) 称为残向量。 记最d - - - 乘问题的解集为 工岱= 讧k ：工是最小二乘问题的解 定理3 5 ：线性最小二乘问题的最小二乘解总是存在的。 证明：因为k m = r ( a ) o 尺( 彳) 上所以对于任意的向量b 可以唯一的表示为 b = 6 1 + 6 2 ，6 l r ( 。4 ) ，6 2 尺( 彳) 上于是对任意的x k 6 l a x r ( a ) 而且与也正 交，从而 忆x ) 眨= b - 刮仨= l l ( b 。一血) + 6 2 i | 慨一纠仨+ i b ：1 1 2 由此即知l r ( 工) 眨达到极小当且仅当0 b l 一纠e 达到极小；而且6 l 尺( 彳) 又蕴含着 l i b , 一纠坛达到极小的充分与必要条件是出= 岛 这样可以推出定理的结论成立。 定理3 6 ： j r ，g 当且仅当a r a x = a r b 3 2 2l a n d w e b e r 算法的奇异值分解的表达式 不同于r i c h a r d s o n 迭代算法，l a n d w e b e r 算法适用于不定适线性系统中，在很 7 多情形下b 仨r ( a ) ，且系数矩阵彳为任何矩阵，这个时候用l a n d w e b e r 算法求解线 性方程组。l a n d w e b e r 迭代算法的公式为 x ( n + 1 ) = x o + 2 , a r ( 6 一a x ( n ) ) ，力= o ，1 ， 名是松弛参数，工( o 是初始值，么r 为彳的转置，l a n d w e b e r 算法求解是求解方程 组的最小二乘解即求解a r a x = a7 b 的解的过程，分析方程组a r a x = a7 b ，由于 彳r a 为半正定矩阵，存在正交矩阵u 使得u r a r 彳u = d i a g ( i t l lj 口l ，i t ，i ，0 ，0 ) ， m i t ， 0 是a7 a 的特征值，i k 是后阶单位矩阵，每个段的代数重度为p i ， 任意6 k m y b = b l + b 2 ，岛凡( 彳) ，b 2 月( 彳) 上，a7 b = a r b l r ( a7 彳) ，b 2 n ( a r a ) ， a 7 b 2 = 0 ，因此爿7 a x = a r b = a7 b l 存在解，如果方程组存在解x ，当且仅当x 是 a x = 6 l 的解。 由奇异值分解可知： ( 1 ) 设u = ( u l l , - - , 毋，”s is 印，“i ，“叮) 材杉是以，k = 1 ，s 相应的特征相量， “i ，k = l ，q 是0 相应的特征相量，因此“l l ，n ，”m “眠，“i ，- 一，“g 构成 k 肘的正交基。 ( 2 ) 向量“材：l j p t ，l k s 构成l v ( a ) 上的正交基 ( 3 ) 向量缸t ：l k g ) 构成n ( a ) 的正交基 ( 4 ) 线性方程组的最d , - 乘解工+ 在( 彳) 上的子空间可记为 工+ = c 村“茸c 分k l kss l p i k = li = 1 a r b = a r b l = a r a x + = t c 村 村 一。“厶一v 初始值可以分解为： 扣1 户1 工) - “茸+ 六“七= + x p 1 k sl j p i k = l 户l i = l 从以上分析可知l a n d w e b e r 算法是r i c h a r d s o n 迭代算法的一个特殊形式，它 们的奇异值分解表达公式一样。因此r i c h a r d s o n 迭代算法的收敛性定理也适用于 l a n d w e b e l 算法 3 3a r t 算法 3 3 1 6 旧算法 自1 9 7 0 年以来，众多学者对a r t 算法进行了大量的研究和实践，分析了a r t 算法并予以改进。影响a r t 算法的因素有： ( 1 ) 松弛因子的选择， ( 2 ) 最优迭代次数的估计， ( 3 ) 初值的选取， ( 4 ) 先验知识的多少。 解线性方程组的a r t 方法是迭代过程，即他们产生一系列向量一们，工( ，工孙， 使得序列收敛于，。这就意味着，对l ，如果k 选得足够大，工保证 任意趋近于x ：。a r t 的第足步迭代能用函数口。来描述，它的变量是两个维向 量和一个实数，它的值是一个维向量。于是， z 纠= ( x 翩，胤) 其中工x 和7 陆是两个维向量，儿是一个实数值。不同的a r t 方法所选用的吼 各不相同。 3 3 2a r t 算法一般步骤 解线性方程组，a r t 算法的一般步骤： 1 ，对x 的各个分量设初值， 工，= 工夕，( - = l ，2 ，j ) ； 2 ，计算第f 个方程的估计值， 即一= 勺矽； 3 ，计算 色= 咒一万； 尸1 4 ，计算第；个方程的修正值： q = ，i 吩( 勺) 2l 5 ，对各个、，值进行修正， x 严“) - x 严+ 掣 6 ，将对第一个方程修正后的各工，= 3 c ( j 0 + g ，代入第二个方程求p ：，重复2 5 步骤，即由第二条射线对各个x j 值进行修正，然后再带入第三个方程求 反，如此下去，直到第，个方程； 7 ，经过第1 到，个方程的修正，得到的各x ，值完成了第一轮迭代。一般经过足 轮迭代，各x ，的值和前一轮中各x s 的值之间的误差均小于指定的正数占， 则可以认为迭代达到了收敛的要求，可以接受最后的迭代值。否则，继续 迭代。 对于a r t 算法，在迭代过程中，为了得到第( k + 1 ) 次迭代值，我们应用吼到 第k 次迭代值x ，系数矩阵a 的k 行及测量向量y 的第k 个分量上。这种算法只 需要存储上次迭代得到的x x 的值，一次迭代完毕，可以用原来存储工k 的存储位 9 来存储最新得到的n d 的值，所以a r t 算法被称为存储器效率较高的算法。 1 0 4 松弛参数的选取问题 在使用迭代算法过程中，最重要的技巧之一有松弛参数的选取。如何选取最 恰当的松弛参数以得到最优的结果，是非常关键的。但是由于对松弛参数的选择 没有理论根据，只有一些实践的经验值，因此松弛参数的选择主要是通过试验的 方法来证明其合理性。我们有必要对松弛参数的选取从理论上作进一步的研究。 4 1 松弛参数选取的一般方法 我们司以用形如 1 乙r t o x i q j = l 的不等式组来代替方程( 前面要解的线性方程组，p 个方程) ，改写为内积形式 ( n i ，x ) q i( 1 f p ) 其中啊是给定的j 向量，q i 是给定的实数。 我们假定珥中至少有一个元素为非零向量，如果吩的所有元素都为零，那么， 其对应方程对重建结果不影响。 引入某个向量集i 和 m = x i ( 吩，x ) - - q i ( 1 a i a p ) n = ( q n i f f i l 寻找的一个元素。给出一个a r t 型的方法，它由下面函数序列定义，称为 不等式松弛法：义o 任意 jr(k+”=_f。k，+五。丘，(主一l”(,刀(kni，kj,rx。f(，k)(刀qkik，力k)力k，其t三c4-， 其中五k 是一个实数，即通常被称为松弛参数，= e k ( m o d p ) + 1 ，即 乇- 1 ，= 2 ，i 。一l = p ，i p = 1 ， 定理4 1 ：如果松弛参数对所有k 满足弱条件o q 元足岛 2 那么，不等式松弛参数法产生一个序列工( 们，j ，x 扪，仅当是非空时， 这个序列收敛于中的一个向量。 注意1 由公式可知a r t 方法就是松弛参数五选取为l 时的一种等式松弛 算法，有不等式收敛性定理，可知a r t 算法是收敛的。 注意2a r t 算法中，我们可以利用松弛参数的选取来改善收敛速度。一般情 况下，选取小松弛参数会得到好的重建结果。 松弛参数的选取是一个复杂的过程，如文献【9 】所述，现在我们没有任何好的 方法去选择松弛参数，仅仅可靠的方法是通过实验验证，这个问题在理论方面需 要进一步的研究。 一般，选取松弛参数五的方法有： l 五= 2 + 几。，其中层。和成抽分别是系数矩阵的最大和最小特征值。 2 五= 五( 1 ) ，其中是系数矩阵的最大特征值，五是0 五 2 的实数。 3 五= 2 + 成；。一( 一) c o s l 刀( 2 p ( k ) - o 8i ，当我们知道迭代的 总次数时适用。 4 2 松弛参数选取的一些观点 通过对松弛参数的恰当选取可以大大改善收敛速度，但是我们至今还没有确 切的方式去选择合适的松弛参数，大多数只是在经验上、实践上证明如何选取松 弛参数会更理想。所以说，如何从理论上选取恰当的松弛参数成了松弛参数选取 的基本问题。 迭代算法实际上是一个解超大规模线性方程组的带松弛参数的迭代过程，松 弛参数的选择对算法的执行速度有很大影响，松弛参数选择的一个基本标准为式 ( 4 2 ) 。在这个区间内a r t 算法才能按照某种标准保持其收敛性。一些学者认为松 弛参数的选择可以根据不同的目的，通过试验的方法来选择最佳的松弛参数。其 基本做法是：根据不同的重建任务，用实验的方法来模拟实际环境，选取不同的松 弛参数重建图像，从重建结果中选择被认为最好的松弛参数，然后在实际的医疗 科研中采用这个松弛参数进行运算。 在本论文中，我们首先找到系数矩阵的最大的特征值，然后选取 五= 名( 1 ) ( 其中0 0 ，由2 范数定义可知i = p ，口i 。= m i n ( 2 p ，2 - 2 p ) ， 对于七。 0 ，松弛参数选取为0 以p 2 且以段，刀0 , 1 k s 对于任意的6 尺( 么) 和任意的初始值j 。k ，由r i c h a r d s o n 算法产生的备( 月 收 敛到a x = b 得解x l + 4 0 ，当且仅当 口1 ，。= 佃 n = o ( 4 6 ) 证明： 充分条件： 当0 以l = p 1 ，t l = p ，口l 。= m i n ( 2 p ，2 - 2 p ) ，口l 。= 2 p ，0 口1 。1 ( 多当1 i 0 ，0 以t 丸p 2 ，1 0 ，1 k s 以l 心 0 口i 一 l由( 4 5 ) ，( 4 6 ) 得口如= 佃且由命题4 1 可知 ! 骢骚( 1 一厶以) o ，j 必要条件仁：由声理( 3 4 ) 可知。l i + m 。驵( 1 一九段) = 0 ，尼= l ，s 因为a l , n 满足命题4 1 中的口。的条件，因此可证明q 。= + o o n - 0 推论4 1 ：如果松弛参数选取为以= l 以，k = l ，2 ，s 经过s 次迭代之后工4 收 敛于而+ 掣 4 4 数值实验结果 我们用r i c h a r d s o n 算法对一些系数矩阵为正定对称方程组在微机上用m a t l a b 语言编程计算，算例表明用r i c h a r d s o n 算法都可以得到相应方程组的解，且适当 选取松弛参数，r i c h a r d s o n 算法可以求得更高精度的解( 采用血一地来度量) 这里系数矩阵最大特征值分之一为k 部分算例如下。 例l 求解线性方程组止= 6 ，其中 a = 蜀c l a ib 2c 2 a 州吃一lc m l a 。一lb 。 6 = ( b l ) r k ”工o = ( 0 ，0 ，0 ) e = 主三 ，彳，= 三： ，e = 三? ，魂= 主 当n 较大时，不妨取，甩= 3 0 ，其条件数为c o n d ( a ) = 8 2 5 0 6 松驰参数的选取有两种情况： ( 1 ) 松驰参数是无变化固定：精度为( e = l o 4 ) 图1 不同松弛参数和迭代次数的关系图 图l 给出了不同松弛参数的迭代次数的情况，从图上可知当松弛参数选取为 1 4 入( 0 入2 ，入r ) 乘以线性方程组系数矩阵的最大特征值分之一，且入接近1 2 时迭代次数最少。 透代次瓤 图2 不同松弛参数的收敛比较 图2 给出了选用不同的松弛参数的收敛情况。可以看出选择适当的松弛参数 不但可以提高收敛速度，而且可以使误差较小。实验表明入接近1 1 1 2 时候相对 误差比较小，且当迭代次数少时可取较小的松驰参数使得误差最小，当迭代次数 比较大时候可适当选用高松弛参数松弛参数入使得误差最小。 ( 2 ) 松驰参数是变化的 当松弛参数变化区间为1 k 一2 “。 图3 松驰参数变化时不同步长的选取的收敛比较 通过实验可知当迭代次数比较少时选择比较大的步长使得误差最小，迭代次 数多时候选比较小的步长使得误差最小。 值后随迭代次数的增加误差将逐渐变大。 松驰参数为1 九；寸1 k 从实验可知当松弛参数为从= 1 丑 精确等于五+ 石 例2求解块三对角方程组血= 6 ，其中 a = b ic l a lb 2c 2 a 。一2b 一lc m l a 。一1 b 。 且不管取的步长为多少当误差达到最小 i = l ，2 ，n 经过n 次迭代之后x ”几乎 b = ( 6 l k ) r k 4 工o = ( o ，0 ，0 ) 曰，= 詈三 兰4 = c ：= 一l 一一。岛= i 当r 较大时，不妨取，n = 3 0 ，其条件数为c o n d ( a ) = 1 1 2 9 0 松驰参数的选取有两种情况： ( 1 ) 松驰参数是无变化固定：精度为( e = 1 0 4 ) 图4 不同松弛参数和迭代次数的关系图 图4 给出了不同松弛参数的迭代次数的情况，从图上可知当松弛参数选取为 入( o 入2 ，入r ) 乘以线性方程组系数矩阵的最大特征值分之一，且入接近1 2 1 6 时迭代次数最少。 图5 不同松弛参数的收敛比较 图5 给出了选用不同的松弛参数的收敛情况。可以看出选择适当的松弛参数 不但可以提高收敛速度，而且可以使误差较小。实验表明入接近1 1 时候相对误差 比较小。 ( 2 ) 松驰参数是变化的 当松弛参数变化区间为1 一2 k 图6 松驰参数变化时不同步长的选取的收敛比较 通过实验可知当迭代次数比较少时选择比较大的步长使得误差最小，迭代次 数多时候选比较小的步长使得误差最小。且不管取的步长为多少当误差达到最小 值后随迭代次数的增加误差将逐渐变大。 1 7 2 4 o ， 例3 求解方程组血= 6 ，其中 a = 2 0一l l2 0 一1o 一1o ol 一1 一lo o ol 2 0 01 o2 0 一l 一1 一12 0 b = 一4 2 1 8 1 8 4 2 工) - ( o ，o ，0 ) 当n 较大时，不妨取，力= 6 4 ，其条件数为c o n d ( a ) = 3 5 1 2 4 松驰参数的选取有两种情况： ( 1 ) 松驰参数是无变化固定： 巅 嚣 缎 图7 不同松弛参数和迭代次数的关系图 图7 给出了不同松弛参数的迭代次数的情况，从图上可知当松弛参数选取为 入( o 入2 ，入r ) 乘以线性方程组系数矩阵的最大特征值分之一，且入接近1 4 时迭代次数最少。 z 1忍z 3z 42 5西z 7碣羽加 迭代次数 图8 不同松弛参数的收敛比较 图8 给出了选用不同的松弛参数的收敛情况。可以看出选择适当的松弛参数 不但可以提高收敛速度，而且可以使误差较小。实验表明入接近1 5 时候相对误差 比较小。 ( 2 ) 松驰参数是变化的 当松弛参数变化区间为1 k 一2 乙 刺 账 迭代次数 图9 松驰参数变化时不同步长的选取的收敛比较 通过实验可知当迭代次数比较少时选择比较大的步长使得误差最小，迭代次 数多时候选比较小的步长使得误差最小。且不管取的步长为多少当误差达到最小 1 9 值后随迭代次数的增加误差将逐渐变大。 例4h i l b e r t 病态方程组出= b a = l 二 2 1 1 23 11 刀拧+ l ，为方便起见取6 = 彳( 1 ，l ，1 ) 7 ，x o = ( 0 ，0 ，0 ) 当刀较大时，不妨取，刀= 3 0 ，其条件数为c o n d ( a ) = 2 11 7 3 1 0 1 9 松驰参数的选取有两种情况： ( 1 ) 松驰参数是无变化固定： 图l o 不同松弛参数和迭代次数的关系图 图1 0 给出了不同松弛参数的迭代次数的情况，从图上可知当松弛参数选取为 入( o 入2 ，入r ) 乘以线性方程组系数矩阵的最大特征值分之一，且入接近1 6 时迭代次数最少。 。一n。一州；。一 迭代次数 图ll 不同松弛参数的收敛比较 从图上可知入接近1 6 - 1 7 时候相对的误差比较小。且当迭代次数少时选择 比较小的松驰参数使得误差最小，当迭代次数比较大时候选比较大的松弛参数使 得误差最小。 ( 2 ) 松驰参数是变化的 当松弛参数变化区间为1 五麟一2 五一 迭代次数 图1 2 松驰参数变化时不同步长的选取的收敛比较 通过实验可知当迭代次数比较少时选择比较大的步长使得误差最小，迭代次 2 1 数多时候选比较小的步长使得误差最小。且不管取的步长为多少当误差达到最小 值后随迭代次数的增加误差将逐渐变大。 5 结论 病态线性方程在实际工程中经常会遇到，但用什么方法求解才能使方程的解 更好的逼近精确解呢从实际问题出发，我们必须对提出的问题进行分析，知道其 类型、适用状况及其收敛性等等当遇到较为小型的病态线性方程组时，我们没有 必要使用精确度较高，但其计算量较大的方法求解，我们一般可以采用g s 迭代法或 者s i 迭代法解方程组，这样能够较为节省时间：当我们遇到大型病态线性方程组时， 应采用适合其类型的解法，例如当方程组的系数矩阵为正定时用r i c h a r d s o n 法等， 虽然在时间上有些延长，但若单单用g s 迭代法或者s i 迭代法，因为在求解过程中 有局限，不能够很好的收敛或者收敛速度很慢，从而得不到满意的结果 本文着重进行了r i c h a r d s o n 迭代算法中松弛参数选取的研究，通过对松弛参 数的选取研究其迭代的收敛性和收敛速度。松弛参数的选取是不变或是复杂的， 在某一区间上变化时的情形建立算法收敛的充分必要条件。通过数值实验得出结 论：当松弛参数选取为系数矩阵的特征值分之一时，在有限步迭代之后r i c h a r d s o n 算法收敛。当松弛参数的选取是变化的，且变化区间为1 五一专2 九缸时可通过调 整步长来提高收敛速度。并且选择松弛参数仅仅可靠的方法是通过实验验证。 近年来，随着c t 技术在各个学科领域内的广泛应用，其成像理论和算法也在 不断地完善，针对不同测量目的和测量方式的新算法也不断出现。由投影重建图 像是c t 成像技术的理论基础，本文着重介绍了迭代算法中松弛参数的改进和创