（计算数学专业论文）解对称循环五对角线性方程组的一种方法.pdf

摘要 众所周知，在工程计算和实际应用中有许多问题最终都归结为矩阵计算问 题，而且不同的应用会导出一些具有特殊稀疏结构的矩阵计算在处理与这些稀 疏结构矩阵有关的矩阵计算问题( 例如计算特征值、求解线性方程组等) 过程中， 若矩阵的阶数较小时，通常的经典算法是可行的( 例如l u 分解算法、q r 算法 等) 然而，在许多实际应用当中，稀疏矩阵的阶数很大，或某个线性方程组 需要多次计算直到得到一个满意的结果( 例如迭代法时) ，此时这些经典的算法由 于代价太大而失去了实际意义因此，针对这些稀疏结构矩阵的特点而设计一 些能利用它们的结构的，数值稳定的快速算法，具有非常重要的意义 该方法利用了l u 分解，并且算法的计算复杂度为d ( 拧) 该方法在计算量上 和存储量上比高斯消元法更有优势理论和数值实验显示，这个快速算法是行之 有效的 第一节，我们简单介绍了研究求解实对称五对角循环线性方程组的现实意 义和文章结构，同时也给出了与本论文有关的引理 第二节，我们探讨含有三个参数的线性方程组的求解方法，并针对不同的情 况进行讨论分析 第三节，我们利用第二节的结果和w 的d b u d ，公式，提出求解五对角对称 1 o e p l i t z 线性方程组的一种方法并给出一般五对角线性方程组含参追赶法算 法 第四节，利用引理的w r o o d b u r y 公式，我们提出一种求解五对角对称循环线 性方程组 第五节，通过利用最优的l u 分解，数值实验显示这是一种有效，稳定的算 法与其它算法相比较，我们的方法在解循环线性方程组上具有较大的优势。 a b s t r a c t ni sw e nb o mt 1 1 a tm 锄yp r o b l 锄s 洫c n 西n e e r i n gc 0 m p u t a t i o n 跚dp r a c t i c a l a p p l i c a t i o na r et h ep r o b l e i t lo fm a t r i xc a l c u l u si i ln a t u r e a s w ea l lk n o w ，t l l e r ea r em a i l yi s 销i i le n 百n e e r i n gc o m p u t a t i o na 1 1 dp r a c t i c a l 印p l i c a t i o nt l l a tu l t i m a t c l yb o i ld o w nt 0am a t r i xc o m p u t a t i o n a n dd i 行e r e n t a p p l i c a t i o n s w i l ll e a dt 0s o m eo fm es p e d a l s p a r s es 咖c t l l r c o ft h em 撕x c o m p u 协o n h lm ep r o c e s so fd e a l i n g 丽mt l l e s p a r s em a t r i xs 缸u c t u r eo fm em a t r i x c o m p u t a t l o n ( 士 0 re x 锄p l e ，e i g e i l v a l u e 咖c u l a t i o n ，s o l v i n gl i l l e a re q u a t i o n s ，a n ds oo n ) ， i ft 1 1 em 枷xi s s m a l l ，u s u a l l yt l l ec l 舔s i cm 甜l o di sf e a s i b l e ( f o re x 锄p l e ，l u d e c o m p o s i t i o 玛q ra l g o 订t l i i l ，e t c ) h o w e v i i lm 孤yp r a c t i c a la p p l i c a t i o l l s ，m e m 咖c 髓a r el a r g e 锄ds p a r s e r o ras ) r s t e i i lo fl i i l e a re q u a t i o n sn e e dt 0c a l c u l a t e s e v 酬t i m e su n t i lt 0g e tas a t i s f a 鼬d 珂r c s u l t ( f o re x 锄p l e ，w h e ni t e r a t i o n ) ，w h i c hw i l l g e tt l l el a 昭el o s so f 旅t ls i 嘶丘c a i l c cb e c a 晒eo ft l l ec o s to ft h ec l 弱s i ca 1 9 0 f i t s a s ar e s u i t t 0d e s i g n l er a p i d 锄ds t a b i em m l 舐c a la l g o r i t l l mb ym a k i i l gu s eo fs o m eo f t h c l r 昀n j c t u r ca c c o r d i n gt ot l l e s es p a r s em a t r i xs t r u c t u r cf e a t u r c sw i l lb eo fg r e a t s i 嘶f i 啪c e s o m er e s e 砌e r sp r o p o s e d 锄e 行e c t i v ew a yt os 0 1 v er e a ls w n m e t d c 仃i d i a 2 i d n a l c y c l eo fi i n e a re q u a t i o n s l ea r t i c l ei i l 仃o i i u c e san e ws t a b l ea i l de 丘e c t i v ew a vt os o l v e r e a ls 舯咖c p e n t a d i a g o n a lc i r c u l a i l to fl i n e a re q u a t i o n s o u rm e t i l o da p p l yt l l el u d e c o m p o s i t i o n ，a 1 1 【di t sc o m p u t i i l gc o m p l e x i t yi sd ( 万) t h em e l o dh 鹤m o r e a d v a i l t a g e si nt l l ec 0 s to fc a l c u l a t i n g 锄ds t o r a g et h a ng a u s se l i m i i l a t i o n t h e o r y 觚d 肌m 嘶c a le x p 鲥m e 鹏s h o wt t l a to l l rm g o r i t h mi se 疏c t i v e i n 廿l ef i r s tc h 印t w eb r i e n y 砷d u c e dm er e s 黜hs i 印i f i c 孤c et 0s o l v er e a l s y l l 瑚硎cp 髓t a d i a g o n a lc i r c u l a n to fl i l l e a re q u a t i o n s ，s t r u 曲鹏o ft h ea r t i d e ，a sw e l l a st l l el a 【i l ：m ao fm ea r t i c l e i i lt h es e c 0 n dc h a p t e f ，w ee x p l o 谢n l 廿l e 廿l f e ep a r 锄e t e f so fl i n e a re q u a t i o i l so f 廿l es o l u t i o 玛a n da i l m y z e 也ed i 丑i 锄ts i t u a t i o i l s i i it l l e 1 i r dc h a p t w e 啷en l er e s u l t so f m es e c o n dc h 印t c r 锄dt h ew b o d b u 巧 f o m m l at op u tf 0 刑a r dm ew a yo fs o l v i n gf i v e1 e p l i t za l l 酉es 脚e 仃j cl i n e a r e q u a t i o i 塔 i nt h ef b r t hc h a p t w ep f o p o s e daw a yt 0s o l v et h ep 铋t a d i a g o n a lc i r c u l a i l t s 舯e 扫哆o f l i i l e a re q 【u a t i o i l sb yu s i i 培m el e m m aw b o d b u 巧f 0 肌u l a i i lm ef i f u lc h a p t 吼o u 曲u s i n g 廿l eo p t i m a ll ud e c 0 m p o s i t i o n ，n u m 耐c a l e x p 鲥m e n t ss h o wt h a tt h i si s 锄e 行e c t i v ea i l ds t a b l ea l g o r i t h m c o m p a r e dw i t ho t h e r m e t l l o d s ，0 1 1 rm e t l l o do fs o l u t i o ni nt l l ec i r c u l a t i o ns y s t e mo fl i n e a re q u a t i o n sh a sa l a l ? g e ra d v a n t a g e 2 厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下，独立完成的研究成 果。本人在论文写作中参考其他个人或集体已经发表的研究成果，均 在文中以适当方式明确标明，并符合法律规范和厦门大学研究生学 术活动规范( 试行) 。 另外，该学位论文为() 课题( 组) 的研究成果，获得() 课题( 组) 经费或实验室的 资助，在() 实验室完成。( 请在以上括号内填写 课题或课题组负责人或实验室名称，未有此项声明内容的，可以不作 特别声明。) 声明人( 签名) ：苡善夏 。7 年厂月7 日 厦门大学学位论文著作权使用声明 本人同意厦门大学根据中华人民共和国学位条例暂行实施办 法等规定保留和使用此学位论文，并向主管部门或其指定机构送交 学位论文( 包括纸质版和电子版) ，允许学位论文进入厦门大学图书 馆及其数据库被查阅、借阅。本人同意厦门大学将学位论文加入全国 博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和 摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于： ) 1 经厦门大学保密委员会审查核定的保密学位论文， 于年月日解密，解密后适用上述授权。 () 2 不保密，适用上述授权。 ( 请在以上相应括号内打“ 或填上相应内容。保密学位论文 应是已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密 委员会审定的学位论文均为公开学位论文。此声明栏不填写的，默认 为公开学位论文，均适用上述授权。) 声明人c 签名，：多旌畈 a7 年衫月夕日 第一节绪论 1 1 引言 众所周知，在工程计算和实际应用中有许多问题最终都归结为矩阵计算的问 题，而且许多的应用会导出一些具有特殊结构的稀疏线性方程组计算问题，比如 样条逼近，有限元方法，插值法等等这些线性方程组常常可以转化为对称循环 五对角矩阵通常我们将其分解为两个简单的循环矩阵，然后得用w b o d 岍 公式求解因直接法计算的解是非常精确有效的进而受到广大科技工作者的注 目，因而利用直接法求解带有特殊带宽的线性方程组是非常有效的，比如基于 l u 分解算法，或者快速傅里叶变换来计算等 本文介绍了一种新的有效稳定的方法来求解实对称五对角循环线性方程 组我们的方法利用了l u 分解，并且算法的计算复杂度为d 伽) 该方法在计算 量上和存储量上比高斯消元法更有优势理论和数值实验显示，这个快速算法是 行之有效的 本文分为五节第一节，我们简单介绍了研究求解实对称五对角循环线性方 程组的现实意义和文章结构，同时也给出了与本论文有关的引理 第二节，我们探讨含有三个参数的线性方程组的求解方法，并针对不同的情 况进行讨论分析 第三节，我们利用第二章的结果和w | 0 0 d b u 巧公式，提出求解五对角对称 1 o e p l i t z 线性方程组的一种方法并给出一般五对角线性方程组含参追赶法算 法 第四节，利用引理的w o o d b u r y 公式，我们提出一种求解五对角对称循环线 性方程组 第五节，通过利用最优的l u 分解，数值实验显示这是一种有效，稳定的算 法与其它方法相比，我们的方法在解循环线性方程组上具有较大的优势。该算 法计算复杂度仅为d ( n ) 1 2问题的提出和主要引理 本节不加证明地引入一个引理和介绍一些相关的定义其中引理中的公式是 一个由秩一m 矩阵修改过的矩阵的求逆的w o o d b u r y 公式 引理1 ( w o o d b u r y 公式) 设a 是，l 阶可逆方阵，x ，y 均是万掰矩阵，且埘，l ， 则当且仅当j 。+ y t a _ 1 x 可逆时，a + ) ( y t 是可逆的，且 ( a + x y t ) 一1 = a 一a 一1 x ( ，。+ y t a 一1 x ) 一1 y t a 一 定义l 设矩阵彳= ( 口“) 尺，若对所有的f ( 1 f ，1 ) 都有 3 矿 口 。茄 一 ” 口 并且式中至少对一个f 有严格不等成立，则称彳为弱严格对角占优的：如果对所 有f 都有严格不等号成立，则称彳为严格对角占优的 定义2 刀阶t o e p l i t z 矩阵定义如下： r = 气f l f o f l 一詹f 2 一村 即丁= ( “) ，“= f h ，七= 0 ，1 ，以一1 显然t o e p l i t z 矩阵完全由它的第一行和第 一列元素确定( 共有2 玎一1 个元素) 定义3 万阶对称t o e p l i t z 矩阵定义如下： b = 即瓦= ( f ，i ) ，乙，i = f 1 ，- ，z ，后= 0 l ，刀一1 显然对称t o e p l i t z 矩阵完全由它的第一 行或第一列元素确定( 共有刀个元素) 定义4 ( l u 分解) 将系数矩阵彳转变成等价两个矩阵和u 的乘积，其中 和u 分别是下三角和上三角矩阵，而且要求l 的对角元素都是1 解线性方程组的方法一般是，假定我们能把矩阵彳写成下列两个矩阵相 乘的形式 彳= 三u ， 其中三为下三角矩阵，u 为上三角矩阵这样我们可以把线性方程组血= 6 写成 出= ( 三u ) x = ( 己k ) = 6 ， 令阮= y ，则原线性方程组出= 6 可转化为 l y = b ，u x = y ， 于是可首先求解向量j ，使 l y = b ， 然后求解 u x = y 从而达到求解线性方程组a x = b 的目的 在工程计算和实际应用中有许多问题最终会导出一些具有特殊结构的稀疏 线性方程组计算问题，我们考虑如下特殊的大型线性方程组 肠= ， ( 1 1 ) 其中 4 l 2 一 一 o o o ；b i 2 一 一 o o o ；“ m = c6 c cc6 口6 6cc6 口 = ，( 口，6 ，c ，o ，0 ，c ，6 ) ( 1 2 ) 称m 为对称循环五对角矩阵，这里假定矩阵m 是个n ( 刀5 ) 阶严格对角占优 矩阵，即满足有 h 2 h + 2 ( 1 3 ) 其中c 0 对m 可通过矩阵变换为口 0 c = 一1 ，或者口 0 ，c = 1 ，则( 1 3 ) 式可写成 口 2 聊+ 2 ， 其中朋= 1 6 1 我们主要讨论这种形式下的对称循环五对角线性方程组的解。 5 c c 6 c 6 口6 口6 口6 c 第二节含三参数的对称五对角线性方程组 2 1 引言 在解对称循环五对角线性方程组之前，我们先在这节里探讨含有三个参数的 对称五对角线性方程组的求解方法 妙= ， ( 2 1 ) 其中 = ( 口，6 ，c ；口，y ) = 为咒刀阶矩阵，即 飞2 2 口， f = j 2 l ，f = l ，_ ，= 2 y ，扛= 2 口， f = 歹 2 6 ， f j = l ，_ ， 1 d ， l 一，= l ，_ ， l c ， f j f = 2 ， 2 0 ，其它 求解这个问题思路就是求解三个参数口，届 n = l u ，使得矩阵n 有实的l u 分解，即 ( 2 2 ) 2 2 问题解决( 一) 对于一般的c ，我们可通过矩阵变换，把c 变成最简单的形式，即c = l ，或 者c = 一l ，首先我们考虑含有三个参数的线性方程组问题的第一种类型，即 ( 1 )c = 1 0 2 m + 2 ，所 0 ) 我们可导出矩阵n 有如下的l u 分解形式，其中可推出 使得 三= l b 、 一l 口 l o 口 o 1 ， 一一l 口口 6 u = 口1 o o1 b 口 6口 0 口6 6 c c c 6 c 6口 y6 o q 矗c n ：侥l g ：u t u 口 在这个类型中，我们可导出含有参数似，y ) 的非线性方程组 l 7 + 一2 口， 口 + 曼：6 ， 口 口+ 丝： 若( 口，y ) 是( 2 3 ) 式的实数解，则有 口m 一( 1 + 口) 2 2 = 口( 1 + 口) 2 万2 o 故 口 0 消去参数，7 得 令 口+ 吉+ 禹一。 口+ 一+ 一口= u 口( 1 + 口) 2 1 则可把( 2 4 ) 式化成关于x 的一个二元二次方程，则可解得 ( 2 3 ) ( 2 4 ) 玉：丝孕舻丝唑孚互， 泣5 ) 对于每个五，我们有两个解嘞， ：半 r 一砸t j 绣j2 武 k j 氇一鼍， 当哆 i q ，2 是实数，我们假设q ，l q ，2 ， ：学一华产啦 若玉2 ，固定f ，则为对应于我们问题的一个解的分量故口共有4 个 解事实上五4 7 故有 五：竺业墅二堡 1 2 兰竺! 兰竺垡二兰生 2 = ，力+ 4 ，竹+ l ，”+ 4 4 ( 2 6 ) 争2 一赤 1 8 ，m f 2 以五，( 口一2 ) 2 ，则我们可推得而2 ( 2 7 ) 因此n 在这些范围内实的l u 分解 定理l ：在( 2 6 ) ( 2 7 ) 条件下有 ( i ) 3 ， l ， 4 ，所以：半 竿：3 ：芏业：； 2 ，所以吃1 = 吃22尘振了一 2 22 4 一瓦i 7 雯葡 2 而 2 ，所以有 一詹i 一擂j o 卮j 眉j 故五一彳一4 而一专一4 即q ，2 吃2 而+ 一4 ，l 吃。2 口l ，2 即q z2 职堡哆， 2 3问题解决( 二) 其次我们考虑含有三个参数的线性方程组问题的第二种类型，即： ( 2 ) c = 一l ( 口 2 ，l + 2 ，朋 o ) 在这个类型中，我们可导出矩阵n 有如下式的l u 分解形式，其中可推出 8 三= l 里1 口 一三o 口 u = 口一1 o 使得 n ：o c l 口：l u f u ， 上式等价于下列非线性方程组 l 7 + 一= 口， 一旦：6 ， 。 口+ 丝： 我们在实数范围内求解由( 2 6 ) 式消去，7 解得 口+ 三+ 罢一口：o 口缸一1 ) 2 令口+ 三：工，则( 2 7 ) 式变为，一x ( 2 + 口) + 所2 + 2 口：o 口 解得 0一1 9 口 工：堡坐巫巫j 五巫 由( 2 6 ) ( 2 8 ) 可解得 q ：垫乒， 届= 鲁， 乃：+ 丝， ( 2 6 ) ( 2 7 ) ( 2 8 ) ( 2 9 ) 综述，对含三参数的对称五对角矩阵是可以进行实数范围内的l u 分解，从而 达到求解含有三个参数对称五对角线性方程组的目的 9 1 一口一口 一 0 第三节解五对角对称t o e p u t z 线性方程组 3 1 解五对角对称t o e p l i t z 线性方程组 五对角对称t o 印l 沱矩阵的特征值问题在科学与工程计算、图像和信号处理领 域中有着重要的应用，已引起不少学者的关注然而对于具体计算五对角对称 t o 印l 沱矩阵的算法研究，相应的数值算法涉及不多 现在前面的基础上，介绍种求解对称t o e p l 沱矩阵线性方程组的快速算法利 用第二节的结果来求解对称t o e p l i t z 线性方程组 砌= 厂， ( 3 1 ) 其中 p = 箸尸i ( 口，6 ，c ；口，6 ，口) 为n 阶对称t o 印l 沱矩阵，并且c = 一1 ，或c = l ，口 2 研+ 2 妙= 厂的解为( 3 1 ) 式求解提供了准备，其中= ( 口，6 ，c ；口，y ) 由第二节知，设矩阵 q = ( g 二茗等) = 吉1 。) ， 利用分解 q = s s t ， 其中 12 + 1 o s = ( + 1 ) ， ( 3 2 ) 也士了雨了两 因而可得p 的关系如下， p = + u u r ， ( 3 3 ) 这里u = ( 吾) ，o 为。一2 ) 2 零矩阵 利用( 3 3 ) 式和引理l 的w r o o d b u r y 公式可得 善鬻荔嬲荔 4 ) “= p 1 厂= y 一 r 1 u ( ，+ u 了_ u ) 1 u r 陟 则“可由下列的式子进行连续计算得到： y = - 1 ，一1 u ，u7 一1 u ，u ( ，+ u r 一1 u ) ， u r y ，z = ( ，+ u7 一1 u ) 1 ( u r y ) ，( 一1 【，) z ，“= r 1 厂 故解五对角对称t o e p l i t z 线性方程组就转为含三个参数的对称五对角线 性方程组的求解方法 10 o c c 6 c 6 口6 口6 口6 c c 6 口6 c 0 3 2 五对角含参数追赶法算法 对于更一般的五对角矩阵，也可用l u 分解的方法来求解 设彳= 为系数矩阵的线性方程组 其中 其中 j 2 l ：l ， l j ( 3 5 ) 现我们推导五对角含参数追赶法算法证明将五对角矩阵分解为 彳= 歹缈 ( 3 6 ) 矿= m v 2 屹 ，三= 岛 乏 1 乞 1 晶 ，u = l l if 2 l 心 。 1 乙 。 材“ l 注意：注意在分解式三是玎加+ 2 ) 矩阵，【，是伽+ 2 ) ，l 矩阵 比较式( 3 5 ) 两边元素，得 喀= k 一2 ，马= 墨( f = 3 ，刀) ， q = 一( 墨+ + 1 ) ( f = 1 ，2 ，力) ， 岛= h i ( 一l + 坼) ，q = h ( 墨坼一i + ) ( f = 2 ，3 ，1 ) 于是巧厶u 的元素可以递推求得 4 包吒 i - - j 一即磊 喀以 以， 喀岛，阼 吃吒巳 q 吃以 ， 船砂 = ， 任取s l ， ，z l ，“l ，s 2 ，乞，使得s f + ，“+ l o 1 ，l = 口l ( s l + ，l “1 + 1 ) ，“2 = 1 ，l 一1 6 2 一，l f 2 ， y 2 = ( 口2 一c 2 ”2 ) ( s 2 f 2 一s 2 “l “2 + 1 ) 一1 ，z 2 = ，2 1 c 2 一s 2 l ， 对f = 3 ，力 = 1 ，= 饥一一l t ，v f = 口f 一p f 一( c f p l “f 1 ) “f ， 1 ，f l c f s f “f 1 求解五对角线性方程组出= 转化为求解 砂= g ，孤= y 其中 墨乃+ 乃+ l + 乃+ 2 = 蜀，( f = l ，2 ，：，刀) ， 而2m ， 甜l 五+ f 2 恐2 奶， 五+ 吩+ 1 h 1 + 0 2 矗2 = 咒+ 2 ，( f = 1 ，2 ，刀一2 ) ， 毛一l + 毛2 只+ l ， 毛2 儿+ 2 令 咒= g f + g ：五+ g ? 而，o = l ，2 ，靠+ 2 ) 由咒= f i 五，奶= “l 五+ 乞而得 = o ，g 孑= o ，= ，g ：2 = “。，= o ，= 乞 由式( 3 8 ) 得 将式( 3 9 ) y t2g 卜2 一s 一2 y t 一2 一l t - 2 y 。_ l 带入该式，并整理得到 ( 3 7 ) ( 3 8 ) ( 3 9 ) ( 3 1 0 ) ( 3 1 1 ) 乃= ( 岛一2 一墨一2 9 分一一一2 9 ? - 1 ) 一( 墨一2 9 r _ 2 + 一2 9 ：卜1 ) 毛一( 岛一2 9 ，- 2 + 一2 9 _ 1 ) 屯 故 f9 0 = g ，一2 一s 9 了一舢一乃一2 9 ? 一n ， g ：o = 一岛一2 9 ：卜孙一2 ：f 一2 9 ：卜n ，( f = 3 ，刀+ 2 ) ， ig ? = 一墨一2 9 ：卜孙一一2 9 - 1 再令 五= w + 叫o + 硝屯，( f = 刀，2 ，1 ) 由于毛= 只+ 2 = g 扩2 + g f 肘2 五+ g + 2 而且 而一l = 以+ 。一甜。= ( g 扩n 一 。g p ) + ( g r 一”。g ：肿2 ) 而+ ( g ，n 一“。g p 2 ) 而 12 = p d ： 一 p 2 l 一 一， 屹y = = & 于是 j 以町2 9 驴+ 2 ，叫町2 9 r ，以帕2 9 扩舶，( 3 1 2 ) i 以”= g 扩+ 1 一“。卵+ 2 ，q ”= g ：叶n 一“。g p + 2 ，谚q = g ：”+ 1 一“。g ：肿孙 又由式( 3 1 0 ) 得 玉= 乃+ 2 一坼+ l 五+ t 一+ 2 五+ 2 ，o = 刀一2 ，2 ，1 ) 将式( 3 1 2 ) 代入上式，并整理得 五= ( g 了+ 孙一吩+ 。坩+ 1 一0 2 w + 2 ) + ( g ：“舶一咋+ 。嘶“一+ 2 硝“2 ) 而+ ( g + 2 一“洲皑+ 1 一0 2 硝+ 2 ) 屯 于是有 ( 3 1 3 ) 由式( 4 1 0 ) 有 = 坩+ 嘶1 k + 以1 而，恐= “2 + 叫2 五+ 以2 屯 联立解得到 饿二荽，嚣l 鬻厂飞w _ 皑飞1 。蟛。_ x b 【屯= ( 1 一以2 ) _ 1 ( w f 2 五+ 以2 ) 、。 求出x ，x 后，即可由式( 4 6 ) 递推求出y ，石，如下 i 乃= f i 而， 咒= 嵋五+ 乞恐， 【m = & 一2 一墨一2 乃一2 一一2 乃一l ，( f = 3 ，l + 2 ) i 2 虼+ 2 ， 毛一l = + l 一， l 【而2 乃+ 2 一+ l 五+ i 一+ 2 薯+ 2 式( 3 8 ) ，( 3 9 )( 3 1 0 ) ，( 3 1 1 ) ，( 3 1 2 ) ( 3 1 5 ) ( 3 1 6 ) ( 3 1 3 ) ，( 3 1 4 ) ，( 3 1 5 ) 和( 3 1 6 ) 即构成了求解五对角方程组瓜= 厂的一种新的算法 13 、， i 22一靠 = ，t 2 2 2 + + + |：龟：|f2坩衅蟛 0 0 0 一 一 一 + + + “o舢舢2w 衅硝 + + +坼吩咋 一 一 一 2 2 2 + + + “o u u 2酣甜醴 = = = o盯1”2w 皑皑 ，cl 第四节解对称五对角循环线性方程组 有了前面几个部分的准备工作，我们现在可利用第二、三节的结论来求解对 称五对角循环线性方程组 我们这里c = l ，口 2 聊+ 2 ，引入记号 ，7 = = ( 。7 ：，7 ：，厶：) ，。7 ：= = ( 厶- ，7 ：。) 2 ，。7 7 = = ( ：；，) ， 量= ( 五，屯，一：) r ，j = ( 一t ，) r ，工2 【至j ， q = ( 占气) ， y r = c q r ，0 7 ，q ， 么= ( z2 ) 其中0 是伽一6 ) 2 矩阵 根据( 1 1 ) 、( 1 2 ) 式可写成 ( 乒羽= ( 多) ， t ) 其中p 为0 2 ) ( 力一2 ) 阶，记尸= p ( 口，6 ，l ，口，6 ，口) ，( 4 1 ) 式等价于 戌+ 玢= ( 4 2 ) v t 孓七觚= f 从( 4 2 ) 式消去j 可得 g 未= ， 其中 g = p 一黝- 1 y r ，= 厂一蹦1 厂 ( 4 3 ) 应用引理1 的w - o o d b u r y 公式，则由( 4 3 ) 得 g 一1 = p 1 + p 1 y ( 彳+ y r p l y ) 一1 y r p l ， ( 4 4 ) 舅= g - 1 ，= ”+ ，1 y ( 么+ y r ，1 y ) q y 7 “， 其中“= p 1 ， 因此解对称五对角循环线性方程组转换为解对称t 0 e p l 池矩阵线性方程组的 求解方法 由( 4 4 ) 计算出舅，再从( 4 2 ) 式中解出j ，其中j = 彳一1 ( 夕一y r 殳) 则x = i 舌l 即为对称五对角循环线性方程组的解。 l4 第五节数值实验 利用前面的求解方法，我们来计算n 阶对称五对角循环线性方程组尬= 厂， 这里我们取工= ( 1 ，1 ，1 ) r ，并且矩阵m 分别取以下三种矩阵： j ：m = m ( 玎+ l ，刀2 + l ，1 ，o ，l ，刀2 + 1 ) 口：m = m ( 刀+ 2 0 ，刀2 + l ，1 ，o ，1 ，刀2 + 1 ) 刃z ：m = m ( 咒+ 5 0 ，甩2 + l ，l ，o ，l ，刀2 + 1 ) 其中取占= 忙一龇，我们运用本文的算法，对数值实验结果与经典的g m r e s 算 法作了比较假设m a l r l a b 的g m i 也s 函数计算矩阵的特征值是精确的则三 类矩阵的数值实验结果比较如下： n s = 0 石一j 0 。 ii ii i i 2 01 2 9 1 1 e 1 14 2 7 4 2e 1 l7 0 9 5 1e 1 2 5 06 0 9 4 9e 1 1 5 1 8 1 6e 1 l3 2 4 3 3e l l 1 0 01 9 0 0 6e 1 02 9 3 8 1e 1 07 5 8 1 6e 一1 l 2 0 0 3 5 8 2 9e 一93 1 5 6 8e 1 03 4 7 1 2e 1 0 4 0 02 5 7 5 6e 9 2 2 9 6 3e 9 2 2 8 4 9e 1 0 8 0 03 7 1 5 5e 一82 7 8 3 1e 93 4 5 0 l e 一1 0 1 0 0 0 1 6 3 7 2e 一93 6 9 4 3e 9 3 2 8 6 0e 1 0 表1三种矩阵的g m r e s 算法与本文算法的计算结果的误差 我们再对矩阵i 、矩阵i i 、矩阵i i i 运用本文算法和g m r e s 算法，它们相应的程 序运行时间作了比较，如下图 15 通过利用最优的l u 分解，数值实验结果( 见表1 和图1 3 ) 显示这是一种 有效，稳定的算法与经典的g m r e s 算法相比，我们的算法在解循环线性方程 组上具有较大的优势 16 参考文献 【1 】y i i i l i nw e i ，h u a i a i ld i ，o ng r o u po fs i g u l a rt 0 印l 池m a t r i c 鼯l i n e a ra l g e b r a a p p l ，3 9 9 ( 2 0 0 5 ) ，l 0 9 一l2 3 【2 】m s e i - s a y e d ，t h es t u d y o ns p e c i a lm a t r i c 盥觚d 删【m e f i c a lm e t l l o d s 矗ws p e c i a l ma _ t r i xe qu a _ t i o n s ，p h d t h e s i s ，s o f i 如( 19 9 6 ) 3 】r b e v i l a c q u a ，b c o d 酣i 锄df r o m a n i p a r a l l e ls o l u t i o no f b l o c kt r i d i a g o n a l l i l l e a rs y s t e m s l i n e a ra l g e b ma p p l ，l0 4 ( 19 8 8 ) ，p p 3 9 - 5 7 【4 】m a l f - a r oa l l dj m m o n t a i l e r o n6 v e d i a g o n a lt o 印l 沱m a t r i c e sa 1 1 do m l o g o n a l p o l y n o m i a l so n l eu i l i tc i r c l e n u m e r a l g o r i m m s1 0 ( 1 9 9 5 ) ，1 3 7 一1 5 3 5 】o r 0 j o ，a n e w m e 廿1 0 d f o r s 0 1 v i n g s y m m 嘶c c i r c u l a n t t r i d i a g o n a l s y s t e m s o n i n e a r s y s t 锄s c o r n p u t e f s m a m a p p l i c 2 06l - 6 7 ( 19 9 0 ) 6 】s m e i - s a y e d i g i v 猢v 觚dm g p e 墩o v ，an e w m o d i f i c a t i o no f m er 0 j o m 砒o df o r s o l 啊n gs y m m “cc 讯m l m l t6 v e - d i a g o n a ls y s t e m so fl i i l e 盯 e q u a t i o n s ，c o l i l l m t e r sm a m a p p l ，v 0 1 3 5 ，1 0 ( 1 9 9 8 ) ，3 5 4 4 7 】r f b o i s v e n ，a