（计算数学专业论文）几类特殊分块矩阵及结构矩阵有关快速算法的研究.pdf

西北t 业大学坝 学位论文 几类特殊分块矩阵及结构矩阵 有关快速算法的研究 摘要 本文对工程与科学计算中经常遇到的一些特殊矩阵，如分块循环三对角矩 阵、分块三对角矩阵、分块五对角矩阵、分块拟三对角矩阵、h a n k e l 型矩阵、 v 觚d e r i l l o n d e 型矩阵、l o e w n e r 型矩阵、对称l o e w n e r 型矩阵等进行研究，给出 了求解线性方程组、三角分解、逆矩阵等的若干快速算法这些算法中，有些是 新的，而有些是对原有算法的改进或推广 首先，对于分块循环三对角、分块三( 五) 对角矩阵，根据这类矩阵的特殊分 解，给出了一种新的算法该算法含有可以选择的参数矩阵，适当选择这些参数 矩阵，可以使得计算精度较著名的追赶法高，甚至当追赶法失效时，由该算法仍 可得到一定精度的解 其次，建立了求解分块拟三对角方程组的三种直接算法：追赶法、三参数组 法和线性插值法，分析了算法的稳定性，通过算例比较了算法的优劣算例表明， 对于某个算法失效的情形，利用其它算法可以求解，因此这三种直接算法是互为 补充的同时，还给出了求解分块拟三对角方程组的一种迭代算法呻既方法， 分析了算法的可行性和收敛性，数值算例表明此方法要优于现有的一些迭代方 法 再次，利用h a n k e l 矩阵的特殊结构，给出了求解h a n k e l 矩阵及其逆矩阵的 快速三角分解算法，所需计算量为0 ( 疗2 ) ，并与经典算法c h u n k a i l a t l l 算法进行 了比较 最后，利用d e r m o n d e 型矩阵、l o e w l l e r 型矩阵、对称l o e w n e r 型矩阵的 特殊结构和性质。给出了求其逆矩阵的快速算法该算法所需计算量为0 ( n 2 ) ， 而通常的求逆方法的计算量为d ( ) 并通过数值算例将本文所给的算法与求逆 矩阵的全选主元高斯一约当消去法进行了比较 两北t 业大学硕l 学位论文 关键词：分块五对角矩阵，分块拟三对角矩阵，h a n k e l 矩阵，v a _ 1 1 d e 矾o n d e 型矩阵，l o e w n e r 型矩阵，线性方程组，三角分解，逆矩阵，快速算法 i i 西北t 业大学硕f 。学位论文 f a s ta i g o r i t h mf o rs o m es p e c i a ib l o c km a t r i c e s a n ds t r u c t u r em a t ric e s b s t r a c t s o m es p e c i a lm 枷c e s 也a ta r i s ei r is c i e n c ea n de n g i n e e r i n ga r er e s e a r c h e di nt h i s p a p c ls u c h 硒b l o c kc i r c u l a t et r i d i a g o n a lm a t r i x ，b 1 0 c kt r i d i a g o n a lm a 啊x ，b l o c k p e n t a n d i a g o n a l m a t r i x ， b l o c k q u a s i t r i d i a g o n a l m a t r i x ， h a n k e l - t y p em a t r i x ， v a n d e 肌o n d e t y p em a t r i x ，l o e w n e r - t y p em 砌。i x a i l ds y m m e t r i c a l l o e 、v n e r t y p e m a t r i x a 1 9 0 r i t h m so fs o l v i n gl i n e a rs y s t e m s ，t r i a n g u l a rf a c t o r i z a t i o na i l di n v e r s ea r e p r e s e n t e d ，锄o n g 、v h i c hs o m ea r en e w ；s o m ea r ei m p r o v e m e m sa 1 1 dc x t e n s i o 璐o f e x i s t i n go n e s f i r s t l y ， n e wa l g o r i t l l m so fs o l v i n gb l o c kc i r c u l a t et r i d i a g o n a ls y s t e m s ，b l o c k 仃i d i a g o n a l s y s t e m sa n db l o c kp e m a l l d i a g o n a ls y s t e ma r ep r o p o s e d ，w h i c ha r eb 嬲e d o nt l l es p e c i a lf a c t o r i z a t i o no ft h e s eb l o c km a t r i c e s t h en e wa l g o r i t h m si n c l u d e s e l e c t i v ep a r a r n e t e 卜m a t r i c e s p r o p e r l ys e l e c t e dp a r 踟e t e r - m a m c e sc a nm a k en e w a l g o r i m m sh i g h e ri np r e c i s i o nt h a nt h ef a m o u st h o m a sa l g o r i t h r n w h i l et h et h o m 硒 a l g o r i t l l 】 i li n v a l i d a t ef o rs o m en u m e r i c a le x 锄p l e s ，t h en e wa l g o r i t h r n sc a ns o l v e s e c o n d l y t h r e ed i r e c tm e t l l o d sf o rs o l v i f i gl i n e a rs y s t e mw h o s ec o e m c i e mm a t r i x i sb l o c kc i r c u l a t e 伍d i a g o n a lm a t r i xa r ep r e n t c d ，w h i c ha r et h o m a sm e t l l o d ， t h r e e p a m m e t r i cm e m o d a n d l i n e 盯i m e 巾0 1 a t i o nm e m o d t h es 协b 1 1 i t ya n da d v a l l t a g e s o fa l g 嘶m m sa r ea l s oa r i a l y z e d n u m e r i c a le x a t l l p l e si 1 1 u s t r a t et i l a tt l l ep r o b l e m s w h i c ho n co ft 1 1 e s ea l g o r i u n sc a l l ts o l v e ，也eo m e r sc a l l s ot h e ya r es u p p l e m e n tt o e a c ho t h e lb e s i d e ，t h ep e im e t h o do fs o l v i n gb l o c kc i r c u l a t et r i d i a g o n a li sg i v e n ，t h e p o s s t i b l i t y a i l dc o n v e r g e n c eo fp 匕m e t l l o da r ed i s c u s s e d 嬲w e l l ，a n ds o m e n 岫e r i c a le x a m p l e sa r eg i v e nt oi l l u s t r a t et h a tt h em e t h o di sb e t t e rt h a l ls o m ee x i s t i n g m e t h o d s 1 i i 一 塑韭三些叁兰堡兰竺些丝皇 a d d i t i o n a l l y an e w 触a l g 耐t 1 1 1 1 1f o rt r i a i l g u l 盯f 如t o r i z a f i o no fh a l l k e l m 砌x 锄di t si n v e r s ei sp r e s e m e d ，w h i c hi sb a s e do nt i l es p e c i a ls 仃u c t u r eo f h a i 她lm 州x n ec o m p l e x 时o fn c wa l g o 劬mi sd ( 矿) ，n 啪e r i c a le x 锄p l e s p r o v et h a tm el g o r i t l l m i sl e s si n c o m p u t a t i o nt i m et l l a f it h ec h u n k a i l a m a l g o r i t l l ma n d i sm o r eh i g h e ri np r e c i s i o nf o rs o m eh a n k e lm a t r i x l a s t l y ，s o m ed ( 行2 ) a l g o r i t h r n sf o rt h ei n v e r s eo f a 肛甩v a n d e m o n d e t y p e m a t r i x ，l o e w n e r t y p em a t r i xa n ds y m m e 研c a ll o e w n e 卜t y p em a m xa r eg i v e l l w h i c ha r eb 嬲e do nm es p e c i a ls t m c t u r eo ft h e s e s p i c i a 王m a t r i x ，a 1 1 ds o m e e x a i l l p l e si l l u s 缸龇et h en u m e r i c a lb e h a v i o ro fo u ra l g o r i t h m s 1 ( e y w o r d s ：b l o c kp e n t a n d i a g o n a lm 矾晤x ，b l o c kq u 嬲i m d i a g o n a lm a t r i x ，h a r 出e l m 枷x ，v 撕d e 珊0 n d e t y p em a t r j x ，l o e w n e r t y p em a 啊x ，l i n e a rs y s t e m s ，t r i a n g u l a r f a c t o r i z a t i o n ，i n v e r s em a t r i x ，f a s ta l g o r i t t l r i l i v 西北工业大学 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读 学位期间论文工作的知识产权单位属于西北工业大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电予版。本人允许论文被查 阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文j 同时本人保证，毕业后结合学位论文研究课题再撰写的文章一律注明作 者单位为西北工业大学。 保密论文待解密后适用本声明。 学位论文作者签名 如潍 指导教师签名 2o 口、7 年 ；月27 臼 西北工业大学 学位论文原创性声明 秉承学校严谨的学风和优良的科学道德，本人郑重声明：所呈交的 学位论文，是本人在导师的指导下进行研究工作所取得的成果。尽我所 知，除文中已经注明引用的内容和致谢的地方外，本沦文不包含任何其 他个人或集体已经公开发表或撰写过的研究成果，不包含本人或他人已 申请学位或其它用途使用过的成果。对本文的研究做出重要贡献的个人 和集体，均已在文中以明确方式标明。 本人学位论文与资料若有不实，愿意承担一切相关的法律责任。 学位论文作者签名： 叼年弓月哆日 西北工业大学硕士学位论文 第一章绪论 1 1引言 一研究意义 计算机技术的迅速发展，使得科学计算作为科学研究的有效手段，上升为与 科学理论和科学实验相并重的三大科学方法之一近十几年来，科学技术突飞 猛进的发展，国防科技和国民经济建设的许多领域不断提出许多大型和超大型 的计算问题这些问题要求计算机系统有更高的速度和更大的信息吞吐量，从而 促使计算机体系结构向巨型化和并行化方向发展然而，巨型机与并行机的发展 受限于一个国家的综合国力因此，如何利用现有的计算机处理尽可能大型的问 题是很实际的一个课题 在科学技术和工程应用中要遇到大量的矩阵计算问题众所周知，对于一般 的h 阶矩阵，求解相应的计算问题如线性方程组、逆矩阵、三角分解等的计算量 为0 ( ) 但实际计算中所遇到的许多矩阵往往具有一些特殊的结构，因此利用 这些矩阵的特殊结构和技巧性的处理，使矩阵的计算量降低一个数量级，即由一 般的0 0 3 ) 降低到o ( h 2 ) 或更低，这一问题的研究具有理论意义和现实意义 求解分块三对角、循环分块三对角、循环分块t o e p l 配三对角线性方程组是 科学与工程计算中的重要问题，而这三类方程组都是拟分块三对角线性方程组的 特例因此，拟分块三对角线性方程组的求解是诸多应用问题的重要组成部分例 如用差分法或有限元法解活动边界条件下的微分方程的边值问题或初一边值问 题，常需要求解拟分块三对角线性方程组；周期的样条插值就导致求解循环分块 三对角线性方程组；而在热传导与扩散过程、船体数学放样中建立的三次样条插 值函数的求解、线性规划、网络分析、结构分析等问题，时常会遇到一种特殊的 线性代数方程组，其系数矩阵为对角占优的分块三对角矩阵，且阶数一般较高从 而研究它们的解法具有实际意义 h a n k e l 矩阵，l o e 砌e r 矩阵，对称l o e w n e r 矩阵和d e n i l o n d e 矩阵都属于 西北t 业人学硕j 学位论义 特殊的结构矩阵而h a t l k e l 矩阵在代数领域、可靠性理论、随机过程、数字滤 波、多项式拟合与逼近，插值理论及系统理论中都有广泛应用“”棚在最优化 理论、控制理论、计算数学、数理统计等领域中，l o e w n e r 矩阵和对称l o e w l l e r 矩阵往往扮演着重要的角色另外插值多项式的存在性和惟一性的问题，线性泛 函逼近问题及状态方程的线性变换等实际问题往往转化为以d e 锄o n d c 矩阵 为系数矩阵的线性方程组的求解或求逆矩阵问题“儿对于这些特殊类型矩阵的 研究一直是人们关注的焦点，而且已有大量的文献问世，从而解决了相关的很多 问题因此，对于以上四类特殊矩阵的研究具有重要的理论意义和实际意义 本文将对这些问题进行系统的研究 二研究现状 求解以分块三( 五) 对角矩阵和分块循环三对角矩阵为系数矩阵的大型线性 方程组最经典的方法是追赶法它是利用分块三( 五) 对角矩阵的l u 分解的特殊 形式而得到的一种快速算法在1 9 9 4 年王纪林，周钢给出了把较大方程组化为 较小方程组的初参数方法，并将三对角方程组作为特例给出了相应的算法”继 而在1 9 9 7 年，周钢，胡芬兰，王纪林给出了复系数线性带状方程组的初参数追 赶法m 循环三对角方程组最早由r d r i d l t m y 髓和k w m o r t a l l 研究的， 他们在1 9 6 7 年提出了类似于追赶法的解法2 0 0 5 年陈芳，袁志杰在其硕士学位 论文”中分别给出了求解分块三对角方程组、分块循环三对角方程组和分块五 对角方程组的变参数追赶法最近人们主要是在讨论循环三对角方程组的并行算 法对于拟三对角矩阵为系数的线性方程组的研究却很少，在2 0 0 2 年李青给出 了求解拟三对角方程组的追赶法及其二分算法“，而对拟三对角矩阵方程组的其 它解法并未给出 h a n k e l 矩阵，l o e w n e r 矩阵，对称l o e w n e r 矩阵和v a n d c m l o n d e 矩阵的研究 一直被人们所关注 1 9 6 5 年t h n c h 1 。1 9 6 8 年b e r l e k a m p f l ”，1 9 7 4 年鼬s s a l l e n ”，1 9 8 3 年g r a g g 和l i n d q u i “m ，1 9 8 4 年h e n g 和r o s t 分别给出了h a n k e l 矩阵的逆矩阵的快 速三角分解算法；1 9 7 1 年p h i l l i p s m l ，1 9 7 4 年g r a g g c l ”，1 9 8 9 年c h u n “，1 9 9 0 年l a b a l l l l “”，1 9 9 1 年c h 啪和k a i l a t l l 汹1 提出了h 妣k e l 矩阵的快速三角分解算 法1 9 7 3 年r i s s a i l e n 阶，1 9 8 6 年c i 仃o n 分别给出h a n k e l 矩阵及逆矩阵的快速 2 两北t 业大学硕卜学位论文 三角分解算法1 9 9 4 年p a l ，k a i l a l h “”分别给出求h a l l k e l 矩阵的快速三角分解算 法本文利用h a n k e l 矩阵的特殊结构，给出了h a n k e l 矩阵及其逆矩阵快速分解 的种新的算法，与c h u n k a i l a t h 算法相比，减少了原算法的计算量，算例表明 对有的矩阵还提高了计算精度 l o e w n e r 矩阵是由k l o e w n e r 于1 9 3 4 年首先研究的，他通过单调矩阵函数 的特征及有理插值问题研究了各种l o e w n e r 矩阵之间的关系这些问题后来又被 b e l e v i t c h ，d o n o 曲u c ，f i e d l e r “蚓矧等做过更深的研究其中f i e d l e r 给出了h a i l k e l 矩阵和l o e w n e r 矩阵之间的紧密联系从这些可以看到l o e w n e r 矩阵的各种性质 及其在有理插值中的应用 1 9 8 4 年，z 、r a v r in ”7 3 给出了l o e w n e r 矩阵求逆的快速算法，1 9 9 5 1 9 9 6 年，k r o s t 和z v a v r i n 呻m 1 给出了求l o e w n e r - v a n d c m o n d e 矩阵为系数阵的方程 组的快速算法2 0 0 4 年安晓虹”在她的硕士论文中研究了l o e w n e r 矩阵为系数矩 阵的线性方程组的极小范数最小二乘解的一种快速算法：2 0 0 5 年仝秋娟“在她 的毕业论文中给出了求以埘x 摊的l o e w n e r 型矩阵为系数阵的线性方程组和对称 l 0 e 聃懈型矩阵为系数矩阵的线性方程组极小范数最小二乘解快速算法的研究 结果关于对称l o e w n e r 型矩阵的研究结果较少2 0 0 3 年陆全”2 1 给出了对称 l o e w n c r 型矩阵三角分解的快速算法同年，徐猛等人“”给出了对称l o e w n 盯型矩 阵的逆矩阵的快速三角分解算法本文给出了l o e w n e r 型矩阵和对称l o e w n e r 型 矩阵逆矩阵的快速算法 人们从研究d e n n o n d e 矩阵求逆算法开始h ”3 1 9 7 0 年，b j o r c k 提出了 求解以v 飙d e m o n d e 矩阵为系数矩阵的线性方程组的递进算法，1 9 8 3 年，张壶“7 1 得到了v 锄d e m o n d e 矩阵逆矩阵三角分解的快速算法；1 9 9 1 年c h 吼，k a i l a t l l “” 给出了v 觚d e 锄o n d e 型矩阵的三角分解的快速算法；2 0 0 0 年h a l i lo m c 等基于 完全对称函数提出了d e r n l o n d e 矩阵的三角分解的快速算法；而徐猛啪1 在其毕 业论文中用构造高阶矩阵的方法得到了另一种求d e 肌o n d e 型逆矩阵三角分 解的快速算法本文给出了求解d e r n l o n d e 型矩阵逆矩阵的快速算法 三研究内容及安排 本文主要研究几类特殊分块线性方程组的求解以及几种特殊结构矩阵的快 速算法第二章首先给出了系数矩阵分别以块循环三对角，块三对角及块五对角 西北。【业人学硕i 学位论文 方程组的快速算法，并通过数值算例验证了算法的精度第三章给出了求解分块 拟三对角方程组的几种算法，并相互进行了比较第四章给出了求解h a n k e l 矩 阵及其逆矩阵的快速三角分解算法，并与经典的c h u n k a i l a t h 算法进行了比 较第五章主要给出了d e m o n d c 型矩阵，l o e w n e r 型矩阵及其对称l o e w n e r 型矩阵逆矩阵的快速算法 1 2 几类特殊矩阵的定义 本部分给出了论文中所涉及到的几种特殊矩阵的定义 定义1 1 若分块矩阵_ = 。l 。具有如下形式 一= 4 ，置，c 】= 置c i 爿2 垦c 2 玩一lc l a ，b ， 其中4 。，丑，c 。均为，阶方阵，则称爿为分块三对角矩阵 定义1 2 若分块矩阵4 = 0 ，) 胍。具有如下形式 爿= 【4 。，e ，c 】= 马c l a丑2 爿。 e c ， 月m 丑c 4 丑。 ( 1 2 ) 其中，4 ：，丑，c 。，均为r 阶方阵，则称a 为分块循环三对角矩阵或分块周期三对角 矩阵 定义1 3 若分块矩阵4 = 0 ，l 。具有如下形式 西北工业大学硕士学位论文 彳= b 、c 2e 3 如b lc ，e 4 d ，a ，b lc e s 见一：以一：蜀一：e 一e 见一。以一。e 。g d ，a nb n 其中4 ，置，e ，p ，e ，x ，f 均为，阶方阵，则称a 为分块五对角矩阵 定义1 4 若分块矩阵4 = 0 ，l 。具有如下形式 爿= 这里爿。，丑，e ，d l ，e ，x 。，f 均为，阶方阵，则称4 为分块拟三对角矩阵 定义1 5 形如 日= 如廿。l = 的对称矩阵称为h a n k e l 矩阵 定义1 6 设吼，口。c ，矩阵 矿= 啊红 鸭。 吃+ 。如。 ( 1 3 ) ( 1 4 ) ( 1 5 ) ( 1 6 ) 称为v a n d e m o n d e 矩阵 定义 1 7 给定四组数口，色，玑( = 1 ，2 ，玎) ，且设 口，只( f ，= 1 ，2 ，疗) ，称矩阵 肼仍舭助历 五 q o 峨e f = i o 之 峨4 e e 靠 c 邑 甄 呸 。誓：盯 两北t 业大学硕土一学位论文 础乙_ ( 等l ， 为l o e w n e r 矩阵 定义1 8 给定两组数q ，参o ，_ ，= l ，2 ，n ) ，若q 口，( f ，) ，称矩阵 工= 色 ! ：川为对称l 。唧n e r 矩阵其中 勺- | 等一( 1 。) 勺2 协一q ”1 ( 1 8 ) 1 3 问题的提出 下面引入一些( 分块) 循环三对角矩阵、三对角矩阵、五对角矩阵的例子 问题i 定义于球面上的浅水方程能够很好的描述浅齐次的不可压缩非黏滞 流体层的性状，它在全球大气模型、海洋数字模型和天气预报的数值计算中都有 广泛的应用“浅水方程的一般形式如下： 孚+ v v “一( 厂+ 兰t a n 目h + 上竺：o 扰n口c o s 口觑 罢+ v 聊+ ( 厂十兰诅n 日m + 墨关：o 警v 肌去c 詈+ 等m d r 口c o s6 d 兄d 6 ， 利用n i h e i 和i s h i i 提出的拟谱组合紧致差分格式“”离散浅水方程，上述差分格式 可写为大型分块循环三对角线性方程组： 占c d 丑 c d c d 占 工l x 2 ： x _ z 厶 ： l 。= 巴恐篡警 ，c = a 乡鹜：笼。割 d = i 一啦出 6 2一c 2 出l ，c = l 口2 瓜6 2c 2 出i 【口，( 出) 2 一岛出qj【口3 ( 2 岛出c ，j 6 ( 1 1 0 ) 孤北丁业大学硕_ = 学位论史 j 窘芬螂矶以虬哪 k = 伊g ，y ) 其中是区域g ：o 工，j ，1 的边界，妒0 ，y ) 为定义在上的已知函数 由于难于找出其解的解析表达式。因此常求其数值解将区域划分为有限个 正方形单元，交点为网点令 一= 历，y ，= 力，= “b ，y ，) ，乃= b ，y ，) ，= 妒b 。，) ，) ，矗= l 珂 用差商代替偏导数 ( 现* 芈，z 串 代入偏微分方程得到差分方程 竺竺l l ! = l ! ；笋上垫+ g “，= ( 1 蔓l _ ，疗一1 ) 矗2 。1 ” 。” l 蔓f ，疗一1 ) 【“o = ，甜w = 口，“，o = 仍o ，“，h = 妒” 引入向量与矩阵记号 v = ( l l ，“2 i ，“n 一1 1 ，甜1 2 ，“h l ，2 ，“i ， 一1 ，“ 一i 一一1 ) t r ：三 是2 式中j r 是盯一l 阶单位矩阵，而 厂= fi lf 。，j 一4 + 矗2 q l 1 1 于是差分方程可改写为 n = 6 4 + 矗2 口j ( 。一l n ( 。一i ) 方程组( 1 1 1 ) 的系数矩阵r 是分块三对角矩阵 问题考虑双调和方程边值问题“” 彳 ( x ，y ) = g ( 工，y )( x ，y ) r ：! z 羔：2 ，c 斌 【“。( x ，y ) = 9 3 ( 工，y ) 利用五点差分格式离敖上述边值问题就得到大型块五对角方程组 瓜= ，( 1 1 2 ) 7 西北1 = 业大学颈十学位论文 其中爿= s 2 + 胃+ 2 冠r 7 ，j i = d i a g ( 2 ，d ，d ，2 ，) ，足= d i a g ( - ，) s = 爿。 一f j 4 一j r ja ，爿o = 4一l l4 一l l4 方程组( 1 1 2 ) 的系数矩阵a 就是分块五对角矩阵 1 4 追赶法 ，= 1o 0 0 ： o 1 j m 本节介绍求解分块循环三对角、三对角和分块五对角方程组的追赶法 考虑求解线性方程组 似= f ( 1 1 3 ) 其中爿= ( 一。) ，x = ( x j ，x j ) 7 ，= ( 7 ，群) 7 这里月。，x 。，e 均 为，阶方阵 一、分块循环三对角方程组的追赶法 将式( 1 2 ) 的分块循环三对角矩阵爿分解为 爿= 工矽 ( 1 1 4 ) 其中 三= l lj 厶一2 ， s t s ，tl “+ s i ，【，= qql ，2 i c 一2 l 一2 玑，l e 1 + l j 以 比较式( 1 1 4 ) 两边的元素可得 墨= a 。u i ，厶= 爿，u i l ，u 。= 四，正= c 。 u ，= 丑，一厶一l c 一i ，z = 一上。i i ，s ，= 一墨一i c i 町1 ，= 月町1 ( f = 2 ，h 1 ) n 一2 玑= 风一( 厶一l + 鼠，) ( g i + 瓦一。) 一s ，z - - i 从而方程组( 1 1 3 ) 可转化为求解 工y = f ，= y 西北丁业大学硕e 学位论文 其中l r = ( 耳，玎) 7 ，f 为，阶方阵故得到如下算法 算法1 1 ( 求解分块循环三对角方程组的追赶法) 墨= 4 ，w 1 ，厶= 爿。町1 ，z = 正，“= 蜀，五= e 对f - 2 ，3 ，”一l r = f 一工。i 一。，u ，= e 一三。e 一。，z = 一厶一，z 一， 置= 一s 。c i l 1 ，厶= 爿，町1 玑= 色一( l 一。+ 瓯一) ( g 一，+ l 一。) l = e l 一。l 一 对f - l ，2 ，九一2 玑= ( ，。一墨z ，l ：= 匕一s z l = 匕一e 一，l = ，：1 e 对f _ 厅一l ，2 ，1 x = ( ，i 1 ( e c ，x + l z x 。) 求解分块循环三对角方程组的追赶法需要盯次r 阶方阵求逆运算，1 1 疗一1 3 次 r 阶方阵的乘除运算，锄一5 次r 阶方阵的加减运算特别地，当，= l 时，4 就 是循环三对角矩阵 二、分块三对角方程组的追赶法 将式( 1 1 ) 的分块三对角矩阵4 分解为 4 = 上u ( 1 1 5 ) 其中 上= 厶 彳2 爿。厶 ，= 弘f ， 这里，u ，均为，阶方阵，j r 为，阶单位矩阵 比较式( 1 1 5 ) 两边的元素可得 厶= 丑。，u + = c f ( f = l ，九一1 ) ，爿，p + = e ( f = 2 ，竹) 从而解方程组( 1 1 5 ) 转化为解 工y = ，j ：y = y 9 两北_ 业人学硕t 学位论文 其中】，= ( 印，玎) 7 ，z 为r 阶方阵故得到如下算法 算法1 2( 求解分块三对角方程组的追赶法) 工i = b ，k = e 1 e ，【厂：= c 。 对f = 2 ，厅一l l l = b ? 一a j u t ，u m = e 1 c i t l ，= b n a ， 对扛2 ，。以 i = 1 一爿，y 。) x n = y ， 对f = 打一l ，l 置= y 一以+ 。x + 求解分块三对角方程组的追赶法需进行”次，阶方阵求逆运算，5 一4 次r 阶 方阵的乘法运算，3 疗一3 次，阶方阵的加减运算特别地，当，= l 时，4 就是三 对角矩阵 三、分块五对角方程组的追赶法 将式( 1 3 ) 的分块五对角矩阵4 分解为 一= 三 ( 1 1 6 ) 其中 工= l 5 2 厶 见 s ，l ， 厂= j u 2 乏 j 瓦 玑 i 这里丘，u ，s ，z 均为，阶方阵，为，阶单位矩阵 比较式( 1 1 6 ) 两边的元素可得 厶= 4 l ，s 2 = 见，厶u 2 = c 2 ，s 2 u 2 + 2 = 4 2 s ，霉+ l + u ，+ l = c 。+ l ，s j + 1 u ，+ l + 三f + l = 川【j = 2 ，h 一1 ) p + 2 q + l + 墨+ 2 = e + 2 厶z + 2 = e + 2 ( f = l ，2 ，玎一2 ) 从而解方程组( i 1 6 ) 转化为解 1 0 西北工业人学硕十学位论文 工y = f 。= l r 其中l ，= ( k 7 ，玎) 7 ，t 为r 阶方阵故得到如下算法 算法1 3 ( 求解分块五对角方程组的追赶法) 厶= 4 ，是= b ：，【，：= 彳1 c 2 ，五= f 毛 工2 = 4 2 一s 2 u 2 ，u 3 = e 1 ( c 3 一s 2 毛) 对f _ 3 ， 一1 z + l = 上# i e f + 1 ，s ，= 占，一e u i - i 工，= 4 一d ，z s ，u ，u i + 1 = 1 ( c ，+ l s ，z + 1 ) s n = bn d ，l j 。 l n = a 。一d l n s p ， 一= 断1 e ，y 2 = 与1 佤一s ：k ) 对f _ 3 ，玎 l 】：= 1 f p f 一：一s ，r 一，) x 。= l ，x = l - l u 。鼍 对f = 胛一2 ，1 x i = y j u | “x l h t | n x 。n 求解分块五对角矩阵方程组的追赶法需进行 次，阶方阵的求逆运算， 1 1 疗一1 6 次r 阶方阵的乘法运算，8 n 1 3 次，阶方阵的加减运算 两北丁业人学硕士学位论文 第二章几类特殊分块方程组的多参数追赶法 本章给出了求解以分块循环三对角，分块三对角和分块五对角矩阵为系数矩 阵的线性方程组的新算法一多参数追赶法并通过数值算例将这些算法与经典 的追赶法作了比较所做的工作改进了陈芳、袁志杰等给出的求解相应方程组的 变参数追赶法嗍【9 】 2 1 分块循环三对角方程组的双参数追赶法 考虑求解以分块循环三对角矩阵 4 = 彳，曰，c 】_ 口ic lc 。 4 召：g 以一2 且g i 爿。 a 既 x 廿，= 这里爿。，曰，c 。，x 。f 均为r 阶方阵 将式( 2 1 ) 的分块循环三对角矩阵爿分解为 爿= 工， 其中是力+ 1 ) 阶分块矩阵，为+ 1 ) 盯阶分块矩阵。即 = 厶 ， 2 ， 厶“ l l ，l ，u = 1 2 玑+ 玑一。c 一。 玑 ( 2 1 ) 两北t 业大学硕i ：学位论文 这里上。，e ，c 均为，阶方阵，为，阶单位矩阵 比较式( 2 2 ) 两边元素，得 工l 玑+ t = c ，k t c o = 4 ，既= l + ，玑+ ，+ k c i + 玑 4 = + l 以， 墨= 厶c ，- l + qg = 1 ，2 ，以一1 ) 选取可逆的，阶矩阵厶，g 使“可逆，并假设”o = 2 ，3 ，国均可逆则厶厂的 元素可由下式递推求得 够三：笺芘乏嚣。冀蠹鼍邓i 。 ， 【u 。= e l + 【，。一厶c ，u 。= e 。c ，l 。= 以c 一 、7 于是，求解分块循环三对角方程组a x = f 可转化为求解 工y = f ，【= i ， 其中l ，= ( 瑶，e 7 ，球；，球) 7 ，影为，阶方阵由y = f 得 ，f i + z = f ( f = l ，2 ，。，l 1 ) ，l “k + 上。k i + l = e ( 2 4 ) 而由职= j ，得 c 0 墨+ 以+ l x 。= ，p 墨+ c x 。= z “= 1 ，2 ，甩一1 ) 。玑x 。= e( 2 5 ) 于是，由式( 2 4 ) 得 一= e 一厶k = 只一q ，k 其中墨= 曩，q 。= 厶假设l 】：一。= 只一。一q i 一。k 成立，其中 z t = f 一，一厶一t z 一：，2 。- = - 三。q j 2 则由式( 2 4 ) 得 鬈= 鼻一厶z 一一= f 一( p 一- 一q ，一t k ) = ( f 一只，) 一( 一厶q 一。) k = 只一q k 其中 只= f 一厶p + q j = 一厶q j 一，( f = l ，2 ，h 1 ) 又由厶+ ；y 。+ l e 一，+ l = 只得 e ：e 一+ t k 一厶( 只一- 一幺一。k ) = ( e l 只一。) 一( 厶。一l q 一。) k = 只一q k 其中只= e 一乙只+ q = 。一厶幺，故有 1 3 西北工业丈学硕j 学位论文 f = 只一q ，k ( f = l ，2 ，- - ，以) ( 2 6 ) 其中 ：2 乏孑，2 ，一馈捌t 一心。( f 。2 ，3 ，川。) ) 【只= e 一厶只+ 幺= 厶。一l q 。 。 再由式( 2 5 ) 和式( 2 ，6 ) 得 鼍= w 1 e = “1 ( 只一q 。k ) = “1 只一“1 9y 0 = 瓯一日。k 其中瓯= “1 只，巩= “1 幺假设x ，= g j 一日，k ，其中 则 e = u 只一e e 。) ，日，= 町1 ( q l c 日，+ ) x 。= ，二( f 一；一c 一，x ；) = c 厂二【( 只一，一q 一，k ) 一c 。( g ，一日，k ) 】 = c ，二( 匕，一c 一。e ) 一瞄( q 一。一c 。日，) k = g 。一日。k 其中g 。= 喝( 只一。一e 一，q ) ，日。= 瑶( q l 一。一e 一只) 故有 置= e 一日( f = 以，h l ，2 ，1 )( 2 8 ) 其中 悟三鬻一瓮黯叫。巩一，2 。， 【g l = ，l - 1 ( 只一c q “) ，只= 町1 ( q ，一c ，e + ) ( f = 力一i ，2 ，1 ) 、。 最后，将x l = g l 一日jy 0 代入c o x i + u 以= y 0 解得 k = ( ，+ c o 日1 + u 日。) 一i ( c o g j + ，g 。)( 2 1 0 ) 结合式( 2 3 ) ，( 2 7 ) - ( 2 1 0 ) 得求解分块循环三对角方程组a y = f 的双参数追赶 法 算法2 ，1 ( 求解分块循环三对角方程组的双参数追赶法) 选取可逆的，阶矩阵厶，g 且使得玑可逆 j = e ，q i = 厶，u = 矗。一上i c 0 ，l + 。= 4 。g 1 ，玑+ 。= e 对f = 2 ，3 ，盯一l 厶= _ 一u 矗，矿= 置一c 一。，p = f 一工，只一。，q ，= 一厶q 一 1 4 西北工业大学硕十学位论文 = 4 一。它，玩= 玩一厶+ ，。一厶e 一。 只= e 一厶只一- ，幺= 厶“一厶g 一- 6 ，= u - 1 。hn = u i 、q n 对f = 门一1 ，l 一2 ，l e = w 1 ( 只一c ，q + 。) ，日，= 矿1 ( q c ，日。) k = ( ，+ c o 日l + u 。日。) - 1 ( c 0 g l + 玑+ l g 。) 对f = l ，2 ，以 x ，= g ，一j j r ，k 该算法需要疗+ 3 次，阶方阵求逆运算，9 胛+ 3 次r 阶方阵的乘法运算5 肝+ 2 次，阶方阵的加减运算可见，其计算量比追赶法少 特别地，当r = l 时便得到循环三对角方程组的双参数追赶法 算法2 2 ( 求解循环三对角方程组的双参数追赶法) 任取，且使得0 胪石，g l 却铲轨一“2 卺，2 鲁 对f - 2 ，3 ，n l = 纽，虬= 6 f t c 一，p ，= ，一p 川，g ，= g 一 “j i = 纽，“。= 钆一+ 。“。一l c 。 w - l p 。= 厶一p 。一l ，g 。= “一，。q 。一l g 。= 盟，= 盟 “” 对i = 珂一l ， 一2 ，一，l g = 默量n ， “。 豇= 鱼二生塾土! 群 西北工业大学硕士学位论文 2 器 对f - 1 ，2 ，珂 x = g t h y o 该算法需要锄+ 3 次乘除运算5 一+ 2 次加减运算 当矩阵4 非奇异时，一定可以找到适当的参数f 1 ，岛，使得算法2 r 2 可行，证 明如下 定理2 1 设循环三对角矩阵彳= 岛c le q6 2c 2 以一2 以一1 一l n ，1吒 可逆，必存在不 为零的数，。，c 。，使得算法2 2 可行。 证明将三对角矩阵一进行如式( 2 2 ) 的分解爿= 三( ，得到算法2 2 ，则算法2 2 可行的充要条件是m o ( f ；l ，2 ，| ) 由一的分解知 一= o 厶) ( 夏) = 肠7 + 厶以 其中，= “，o ，o ，+ i ) 7 ，n 1 = ( 岛，o ，o ，。) ，而 厶= ，。= 于是 o 砘“2 “。= d e t 玑= d e t ( l 玑) = d e t ( 爿一缸7 ) 根据s h e h n a n - m o r r i s o n w j o 曲u r y 公式得 d e t ( 爿一加t ) o 臼l h t 4 一f o 曹l 一印t = l 一4 + f o d e t a c o 南州毛以+ 。忐吨+ ，彘o t 一白南t 专志等一q 南一彘。 1 6 ( c o ) 2 4 l 一( c o ( c 。4 h + 以1 一d e t 爿) + c 。4 。o ( 2 1 1 ) hc l 。i 口。 屯 ，2 i- i l 4 。_ 2 c 一2 i 可见，只要选取参数f 。，c 。使得( 2 1 1 ) 成立，则算法2 2 可行证毕 2 2 分块三对角方程组的双参数追赶法 考虑求解以分块三对角矩阵 4 = 【4 ，召，e 】= 丑lc l 爿2口2c 2 4 h l 层。一ic 。一l 4