（计算数学专业论文）一类非奇异线性方程组的快速解法.pdf

一类非奇异线性方程组的快速解法 摘要随着电子计算机的出现和迅速发展，在各门自然科学和工程技术科 学的发展中，科学计算已经成为平行于理论分析和科学实验的第三种科学手段 数值计算是科学计算中的一个不可缺少的环节，而在数值计算中，一类很重要的 问题就是线性方程组的求解另外，数学和物理以及力学等学科和工程技术中许 多问题的最终解决都归结为解一个或一些大型系数矩阵的线性方程组所以，大 型线性方程组的求解是大规模科学与计算的核心，许多作者都对此作了研究( 见 【1 】- 1 1 ) 对线性方程组a x = b 的求解，主要有直接求解法和迭代法求解对于阶数 不太高的线性方程组，用直接法比较方便，高斯消元法和克兰姆法则是直接解法 里面最重要的解法但是，随着科学技术的飞速发展，需要求解的问题的规模越 来越大，迭代法已取代直接法成为求解大型线性组的最重要的一类方法此时。 迭代格式的收敛性和收敛速度成为一个很重要的问题，成为人们关注的焦点( 见 【1 2 一【17 】) 不收敛的格式当然不能用，虽然收敛但是收敛的很慢的格式，不仅是人 工和机器的时间比较浪费，而且还不一定能解出结果，实际应用价值太小 通常用的迭代法有j a c o b i ，g a u s s s e i d e l 等古典迭代法，还有s o r ，a o r 以及 s a o r ，s s o r 等迭代法这些迭代法的提出对大型线性方程组的求解提供了一条 快速有效的途径但是这些迭代法相对来说使用条件很苛刻，或者很繁琐此外 当迭代矩阵的谱半径比较大，尤其接近1 时，迭代速度将会很慢，极大的影响了 方程组求解的时效性，从而使它们的应用受到了一定的限制故本文在前人的基 础上，通过大量的查阅文献和思考，寻找一类线性方程组的快速解法 在本文中约定a = d c ，j = d c ，a = ( a 。f ) r n “为对角线不为零的非 奇异矩阵，z ，b p 分别为待求的和已知的列向量正文内容部分从第一章到 第四章，详细内容说明如下： 第一章，概述了线性方程组求解主要方法，同时介绍了近年来一些迭代法的 发展概况 第二章，主要讨论当线性方程组的系数矩阵为非奇异m 阵时，利用交替方 向法，使得它的迭代矩阵的谱半径可以任意小；同时利用矩阵级数理论简化了常 数向量，找出了一条快速有效的解决系数矩阵为非奇异m 阵的迭代方法 第三章，主要讨论了当线性方程组为一般的非奇异线性方程组时，如果它满 足所给的条件，把系数矩阵的逆通过级数的形式表示，从而找到了一条快速解 决一类线性方程组的直接接法，即它的解可以表示为z = a _ 1 b = d b ，或者 z = a - l b = 6 ，从而大大提高了计算速度 第四章，应用举例本章主要是为了应用第二章和第三章的结果解决一些问 题，同时和其他的解法作比较，说明本文的定理在应用上具有广泛性 关键词：非奇异m 阵交替方向法收敛速度 谱半径j a c o b i 分 裂 i i q u i c ks o l v i n gm e t h o df o rat y p eo fn o n s i n g u l a rl i n e a re q u a t i o n l i ux i a o - g a n g a b s t r a c t f o l l o w i n gt h ee l e c t r o n i cc o m p u t e ri n v e n t i o na n dq u i c kd e v e l o p - m e n t ，c a l c u l a t i o no fs c i e n c eh a sb e c o m et h et h i r dm e t h o d ，p a r a l l e dt oa n a l y s i so f t h e o r ya n de x p e r i m e n to fs c i e n c ei na l lk i n d so fn a t u r es c i e n c ea n de n g i n e e r i n gt e c h n i q u es c i e n c e a tt h es a m et i m en u m e r i c a lc a l c u l a t i o ni san e c e s s a r yl i n ks o l v i n g t h el i n e a rs y s e t e mo fe q u a t i o n s ，w h i c hi sav e r yi m p o r t a n tq u e s t i o ni nn u m e r i c a lc a l c u l a t i o n o nt h eo t h e rh a n d ，i nm a t ha n dp h y s i c a ld e p a r t m e n tm a n yq u e s t i o n sh a d b e e ns o l v e db yo n eo raf e wl a r g e s c a l ea n ds p a r s em a t r i x so fl i n e a re q u a t i o n s o ，h o w t os o l v et h el a r g el i n e a re q u a t i o ni st h ec o r eo fl a r g e - s c a l es c i e n c ea n de n g i n e e r i n g p r o j e c tc o m p u t i o n m a n ya u t h o r sh a v es t u d i e di t ( s e e 1 l - 【1 1 】) t h e r ea r et w om e t h o d st os o l v et h el i n e o rs y s t e mo fe q u a t i o n s t h e ya r ed i r e c t s o l v i n gm e t h o da n di t e r a t i v em e t h o d i ft h es t e po ft h el i n e a rs y s t e mq u e s t i o ni s n o tv e r yh i g h ，d i r e c ts o l v i n gm e t h o di sb e t t e r w i t ht h er a p i dd e v e l o p m e n to f c o m p u t e r ，t h es c a l eo ft h ep r o b l e mb e c o m e sl a r g e ra n dl a r g e r d i r e c tm e t h o dh a s b e e ns n b s t i t u t e db yi t e r a t i v em e t h o da n di t e r a t i v em e t h o dh a sb e c o m eo n ek i n do f t h ei m p o r t a n tm e t h o d sf o rs o l v i n gl a r g el i n e a re q u a t i o n s a tt h i st i m e ，t h er u l eo f t h ei t e r a t i o nb e c o m e sai m p o r t a n tq u e s t i o na n dac o r eq u e s t i o n ( s e e 【1 2 一 1 7 1 ) u s u a l l y , w eu s et h ei t e r a t i v em e t h o d ，w h i c ho r ej a c o b i ，g a u s s - s e i d e l ，s o r ，a o r ， s a o r ，s s o ra n ds oo n t h e s ei t e r a t i v em e t h o d si sag o o dw a yt os o l v et h el i n e o r e q u a t i o n s h o w e v e r ，t h e s ei t e r a t i v em e t h o d sw i l lb ev e r ys l o w ，w h e nt h es p e c t r a lr a - d i u sg ot oo n e s o w ea r en e c e s s a r yt of i n daq u i c ks o l v i n gm e t h o do ft h el i n e a r e q u a t i o n s t h ef o l l o w i n g sa r et h ec o n s t r u c t i o na n dm a i nc o n t e n t so ft h i sp a p e r ： i nc h a p t e ro n e ，w ee x p l a i nt h a tt h ei t e r a t i v es o l v i n gm e t h o dh a sm u c hs u p e r i o r i t yi ns o l v i n gt h el i n e a rs y s t e mo fe q u a t i o n sa n di n t r o d u c e st h ed e v e l o p m e n ti n p r e c o n d i t i o n e dt h e r o yi nr e c e n ty e a r s i nc h a p t e rt w o ，w ep r o v es o m er e s u l t sc o n c e r i n gt h ec o n v e r g e n c eo f t h ep e a c e m a n - p a c h o r di t e r a t i v em e t h o d ，w h e nai sn o n s i n g u l a rm m a t r i xf o rt h ec o e f f i c i e n tm a t r i x o ft h el i n e a rs y s t e ma x = 6 t h es p e c t r a lr a d i u sc a nb ev e r ys m a l l i nc h a p t e rt h r e e ，w ep r o v i d ean e ws o l v i n gm e t h o df o ras i z eo fl i n e a rs y s t e m s e q u a t i o n ，w h i c hc a nm a k et h ec a l c u l a t i o ns p e e db ef a s t i nc h a p t e rf o u r ，n u m e r i c a le x a m p l e sm a i n l yv e r f yt h er e s u l t s i i i k e yw o r d s ： n o n s i n g u l a rm m a t r i x j a c o b im e t h o d p e a c e m a n r a c h f o r d i t e r a t i v em e t h o d s p e c t r a lr a d i u s c o n v e r g e n c er a t e i v 学位论文独创性声明 本人声明所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研 究成果。尽我所知，除文中已经注明弓| 用的内容外，论文中不包含其他个人已经 发表或撰写过的研究成果，也不包含为获得陕西师范大学或其它教育机构的学位 或证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均已在文中 作了明确说明并表示谢意。 作者签名： 日期：型她 学位论文使用授权声明 本人同意研究生在校攻读学位期间论文工作的知识产权单位属陕西师范大 学。本人保证毕业离校后，发表本论文或使用本论文成果时署名单位仍为陕西师 范大学。学校有权保留学位论文并向国家主管部门或其它指定机构送交论文的电 子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文进入学校 图书馆、院系资料室被查阅；有权将学位论文的内容编入有关数据库进行检索； 有权将学位论文的标题和摘要汇编出版。 作者签名：壶l1 3 = ! 堂1 日期：遮l 墨塾 第一章概论 在数学，物理学中的许多问题以及偏微分方程的数值求解常常都归结为解线 性方程组 a x = b ，( 1 1 ) 其中a 是n n 方阵，z 和b 分别是未知向量和已知向量在现在的研究领域， 解决这类问题的方法有两种：直接法和迭代法直接法求解是经过有限步的运算 就可得到方程精确解的方法，它是以矩阵分解为基础，将稀疏矩阵对应的线性方 程的求解化为三角线性方程组的求解对于阶数不太高的线性方程组，用直接解 法较好，很快就可以得到理想的结果而对于一般阶数比较高的线性方程组，在 进行矩阵分解时将引入填入元，待别是对从三维离散得到的系数线性方程组，由 于填入元的大量增加，存储需求与计算量一般相当大，直接解法很难克服这个存 储的问题此外，利用直接解法时，由于在实际中有舍入误差的影响，这类方法 实际上只能求近似解 为了毹决这个问题，人们就引入了迭代法。迭代法求解是构造适当的近似解 向量序列，用某种极限过程去逐步逼近精确解的方法，在实际计算中根据精度要 求控制计算到有限步骤终至，获得满足精度的近似解但迭代法不能通过有限步 求得精确解，只能逐步的逼近它因此，迭代法都存在收敛性与收敛速度及误差 估计的问题判断迭代法好坏的标准通常是通过迭代法的收敛速度来刻画的，从 而迭代法的收敛速度成为一个很重要的问题因此收敛速度比较快的迭代法才可 能有实际的价值故许多工作者千辛万苦地去寻求各种加快迭代法收敛速度的技 术在很多情况下，迭代的收敛速度是通过它的迭代矩阵的谱半径来刻画的 对于( 1 ，1 ) 中的系数矩阵a ，作任意一个分裂a = m n ，m 是非奇异的， 求解线性方程组( 1 1 ) 的基本迭代格式是： z ( + 1 ) = m 一1 n x ( + m b ，k = 1 ，2 ，3 ， ( 1 2 ) 其中m 。称为迭代矩阵，它的收敛性直接关系到方程组的求解收敛性和迭代 矩阵m - 1 的谱半径有关，谱半径小于1 就收敛，而且越是比1 小，收敛的就越 快，否则就发散我们在求解过程中，通常假设a dlu ，其中d ，一厶一u 分别是矩阵a 的对角矩阵，严格下三角矩阵和严格上三角矩阵 j a c o b i 在1 8 4 6 年，首先提出了求解对称矩阵的近似特征值的2 个迭代法， 也就是我们所熟悉的j a c o b i 迭代法 其基本迭代矩阵为； j = d - 1 十c ，) ( 1 3 ) l 后来，人们又提出了g a u s s - s e i d e l 迭代法 其基本迭代矩阵为： g = ( d 一目。1 矿( 1 4 ) 由迭代法收敛的定义，我们知道上述迭代法收敛的充要条件是p ( a ) p ( b ) 时，称a 为非奇 异m 阵 定义2 【2 5 】称矩阵a 的特征值的集合为谱，其中它的特征值的模最大的，被称 之为谱半径，即p ( a ) = m a 队| 定义3 1 2 6 1 设a = h + v ，则解方程组a x = b 的迭代格式： 即为一交替方向格式，此格式称为p e a c e m a n r a c h f o r d 格式 定义4 1 2 9 】设p ( a ) 为迭代矩阵a 的谱半径，称r ( a ) = 一i n p ( a ) 为迭代法的 收敛速度 注1 由r ( a ) = 一i n p ( a ) 知当p ( a ) 蚓，j = 1 川2 一，n ( 2 7 ) j = a j i 若对所有的i = 1 ，2 ，n 均为严格不等式，则称a 为强对角占优矩阵 定义1 0 1 4 】设方阵a = ( a i j ) 的阶n 2 ，若对集合w = 1 ，2 ，3 ，n ) 的任 意两个非空不相交的子集s 和? ，s + t = w ，都有i 和j 满足i s ，j t ，且 a i j 0 ，则称a 不可约，否则称a 可约 定义1 1 2 8 】记所有n n 实阵a = ( a 巧) 所成集合为r n ”，胛。“的子集为 群“= a = ( a i j ) l a r n “，a i i o ，v i ， ( 2 8 ) z “= a = ( a i j ) l a r “，a i j 0 ，v i ，j ，i j ) ( 2 9 ) 当a z n , n , a “ o ( v i ) ，称a 为l 阵 定义1 2 2 8 】矩阵a 称为逆保序的，如果当a x a y ，则有x 2y 成立 引理1 【2 8 】设a 是一个竹仃的非负矩阵，则 1 ) a 有一个非负的特征值等于它的谱半径p ( a ) 2 ) a 有一个非负的特征向量z 且石0 ，与p ( a ) 相对应 3 ) a 的任意元素增加时，p ( a ) 不减 引理2 【2 8 】定义6 和定义7 所定义的两种矩阵是等价的 引理3 【2 8 】设a 为( g ，r ) 相容次序矩阵，( g ，r ) = 1 ，p = g + r ，则 1 ) 若对d 。c 的特征值弘与a 满足 则a 为s o r 迭代矩阵 ( ) 、+ “，一1 ) 9 = a 7 u 9 矿，( 2 1 0 ) 乙= ( i u 厶) 一1 【( 1 一u ) l + w u 】( 2 1 1 ) 的特征值， 2 ) 若a 为乙的特征值，则有d - 1 g 的特征值p ，使a 和p 满足上式 引理驴】若a 为( 1 ，1 ) 相容次序矩阵，当u = 1 时，那么a = 矿此时s o r 迭代变为g a u s s - s e i d e l 迭代，即g a u s s - s e i d e l 的收敛速度是j a c o b i 收敛速度的2 倍 证明：由( 2 1 0 ) 式知， ( a + u 一1 ) = a 扩矿 6 又因为p = r = 1 ，所以芹= a 矿 当a = 0 时，a 2 = a 旷显然成立 当a 0 时，得a = p 2 又当u = 1 时，厶，= ( d l ) - 1 u 为g a u s s - s e i d e l 迭代矩阵 即有p ( a ) = p ( c ，) 2 所以命题成立 引理5 【4 】若a 为严格对优或不可约对优矩阵，则j a c o b i 迭代收敛 引理6 【4 】若a 是( 1 ，1 ) 相容次序矩阵，当0 u 2 时，j a c o b i 迭代矩阵的 特征值都为实数时，s o r 迭代法收敛的充要条件是p ( d - 1 c ) l ，并且最优参数 最优谱半径 = 百南， ( 2 1 2 ) 他) = 而蹁 ( 2 1 3 ) 引理7 1 2 s 1 若4 为非负不可约方阵，则当a 的行和恒为常数时， p ( a ) = 玎， j 当行和不为常数时，p ( a ) 在最大行和和最小行和之间， r a i n p ( a ) m 凹 ji 引理8 f 4 】若4 为非负方阵，则 r a i n 。玎p ( a ) m n z j j 引理9 【4 】若a z n 。n , a 可逆且a 一0 ，则称a 为非奇异m 阵 引理1 0 1 3 0 】如果4 是严格对角占优的三阵，则a 是非奇异肘阵 引理1 1 4 设a 为l 阵，则a 是非奇异m 阵的充要条件是p ( j ) 1 ，其中 j = d 一1 c d = d i a g a a = d c 引理1 2 1 4 a 是非奇异m 阵，则a 是逆保序的；反之，a 是逆保序矩阵且 a i ，o ( i j ) ，则a 是非奇异m 阵 引理1 3 p i a 为非奇异m 阵，当0 u p ( a ) ，故当胁为a 的特征值时，8 一胁0 否则，8 = 胁，而胁p ) ，这与8 r ( a ) 矛盾 设矩阵( s ，一a ) _ 1 ( s ，+ 4 ) 的特征值为九，对应的特征向量为z ，那么有 ( s ，一a ) 一1 ( s i + a ) x = k i x 此即( s ，+ a ) x = a i ( s l a ) x ，即8 x + a x = a i 8 x 一九a x 又a x = # i x ，所以有s 茹+ # i x = 九s z 一九肛芦 由于z 是特征向量，故其为非零向量，那么必存在一个非零列向量y 使得 x y = 1 所以给上式两边乘以向量y 得 s + 胁= a i s 一九m ， 即 s + 胁= a i ( s 一胁) 所以九= 业s - - l * i 定理2 设a 是非奇异的m 阵，即a = s i b 且s p ( b ) ，则当b 是实对称矩 阵且r s 时，迭代矩阵耳收敛，即p ( 乃) r ( b ) 且b 0 又显然h = s l ，v = 一b 因而，由( 2 2 式) 得： 正= ( r i + y ) 1 ( r i h ) ( r i + 日) 1 ( r l v ) = ( r i b ) 一1 ( r i s j ) ( r j + s ) 一1 ( r i + b ) = ( r i b ) _ 1 【( r s ) 卅【( r + s ) - 1 叫( r j + b ) = 【( r s ) 明【( r + s ) i ( r l 一口) 一1 ( r l + b ) y n 为a = s i b 且s p ( b ) ，则当r 8 时，迭代矩阵 8 z = 鬲r - 8 ( r j b ) 一1 ( r ，+ b ) 令九为耳的特征值，地为b 的特征值且为实数，因为b 是实对称的且b 为非负矩阵，由定理1 则有 、( r s ) ( r + 胁) 凡2f 啊确 又由于r s p ( b ) ，并令 m ) = 邕， m = 盟业等等丛型 ：! 二些! ! 幽 2 匆 “引2 鳓趟。 眨 = 警南 一 掣8 ，南rp 8 时， 迭代矩阵正收敛，即p ( 耳) p ( b ) 且b20 又显然h = s i ，v = 一b 因而，由( 2 2 式) 得； 露= ( r i + y ) 一1 ( r i h ) ( r i + 日) 一1 ( r l v ) 9 = ( r i b ) 一1 ( r i s j ) ( r j + s ，) 一1 ( r l + b ) = ( r i b ) 一1 【( r s ) 卅i ( r + s ) 一1 卅( r ，+ b ) = 【( r s ) i i ( r + s ) 一1 i ( r i b ) 一1 ( r l + b ) 又因为a = s l b 且s p ( b ) ，则当r s 时，迭代矩阵 矸= r r 十- s s ( r j b ) 一1 ( r ，+ b ) 令a 为耳的特征值，地为b 的特征值，并且b 为非负矩阵，故由定理1 则 有 讧筹警岩 所以 队h 筹渊| 又因为r 8 p ( b ) f m | ，故有 悱渊 又 i a + b lsi a l + 1 6 i ，l o b i i a i l b l 所以 于是有 r + 弘，i r + l p i ，i r p f i r i p ；l o p 8 p ( b ) ) 队i = 鲁希锱 s p ( b ) a i ，所以，( 啦) 0 即( a i ) 是增函数 而又由于b 为非负矩阵，故由引理1 知，p ( b ) 是b 的一个非负特征值 所以 队i = 将箫刿 ：尘二型! 丝! j ( r + s ) l ( r 一胁) l s p ( b ) ，我们可以得到 掣 ，南pb ， r + s r 一【l 故有j s 时，迭代矩阵z 的谱半径可以任意小但不为零 证明：由( 2 1 4 ) 式知 解，= 鲁耙锱 不妨令 m ，= 高糕矧， 即，( r ) 是关于r 的函敦 则 价) = 1 + 万面2 r 两p ( b 石) - 丽2 s r 于是有 ，( r ) ：”瓦篙r = 【万器】7 = 2 ( p ( b ) 一s ) 万砑可高j 丽】 一寺篙黼警帮 一苇箸蒜鬻 。 由于r 8 p ( 口) ，所以，协) 0 即，( r ) 是关于r 的增函数 于是令r = 8 + e ，其中为任意小的正数且 8 时，迭代矩阵乃的谱半径可以任意小但不为零 证明：由( 2 1 5 式) 知 肥，s 旨靶篇 1 2 倚，= 鲁糊， 即，( r ) 是关于r 的函数 则 ，( r ) = 1 + 万面2 r 面p ( b i ) - 丽2 s r 于是有 ，( r ) = 【1 + 万葡2 r p 巧( b 鬲) - 2 i s r 厕】 = 【；巧2 p r ( p b ( ) b + ) - s r 2 一s r s p ( b ) ， = 2 ( p ( b ) 一s ) 万面两云丽1 一毒筹粉祟端铲 一苇筹紫鬻 。 由于r s p ( 口) ，所以，r ) 0 即，( r ) 是关于r 的增函数 于是令r = s - t - ，其中为任意小的正数且 s p ( b ) 于是 肥，鲁靼锱 ：! 兰尘! 丛星卫 ( 2 s + e ) x ( 8 + e p ( b ) ) s p ( b ) ，所以由引理1 5 可得 肌= 志妒6肌2 丽【( j 7 ) 】“6 = 南c 亨+ 菩叫。2 石_ f 万( o + 7 + i + ) 6 = 丽2 熙圭( ( r + s ) 拦瓷刍、7 ，“ 例1 系数矩阵 2 4 数值例子 a = 1 0 - 9 8 0 ) 由引理1 0 得a 为非奇异m 阵，显然a 可以表示为4 ：1 0 1 一b ，其中 b=0 9 8 o ) 若作a 的分裂a = d c ，可以得d = d i a g ( 1 0 ，1 0 ，1 0 ) ，c = b 由引理7 和引理8 易求得p ( j ) = o 9 8 ，此表明j a c o b i 迭代法虽然收敛，但收 敛得很慢，这是无多大实际意义的 又显然它是( 1 ，1 ) 相容次序矩阵， 故由引理4 知 p ( 妒) = p ( j ) 2 = 0 9 8 2 = 0 9 5 5 6 这里= ( d l ) u ，其中令a d l u ，d = d i a g a ，一l 和一u 分别为 a 的严格下三角形和严格上三角形 即g a u s s - s e i d e l 迭代法是收敛的，它的收敛速度是比j a c o b i 迭代法的收敛速 度快，但是仍然很慢，改进后的速度并不快 由引理6 ，我们再来看s o r 迭代在0 2 时的最优参数 “j ：。兰一圭】7 f j = ! = = = = = = = = = = = 1 ， 。 1 + 1 一p ( ，) 2 最优谱半径 低) = 而倦丽划朋 比起j a c o b i 迭代法和g a u s s s e i d e l 迭代法虽然改善了许多，收敛速度有所加 快但仍然偏大，距离我们的要求还比较远 这里k = ( d w i ) 。【( 1 一u ) d + w u 为实参数 下面用交替方向法，设r = 1 0 + 且s = 1 0 ，p ( b ) = 9 8 由( 2 1 5 ) 式则有 肥，鲁靼蚓 ( 1 0 + s 一1 0 ) ( 1 0 + + 9 8 ) 2 面干i 可汉万五厕 e ( 1 0 9 8 + ) 、 ( 2 0 + ) ( o 2 + e ) 。 令e = 0 0 1 ，则p ( b ) 0 0 0 5 8 显然，这大大提高了收敛速度，减少了迭代次数，使线性方程组a x = b 的求 解更加快速，方便，简洁 例2 考虑系数矩阵为 a 书1 赫- - 0 2 - - 二黼0 2 - - 0 ： b=0 0 20 2 0 5 ) + 肥，s 海格锱 令r = s + ，其中s = 1 ，p ( b ) = o 9 8 所以 解) 鲁糊 一( 1 + 一1 ) ( 1 + e + 0 9 ) ( 1 + e + 1 ) ( 1 + 一0 9 ) 一x ( 1 9 + ) ( 2 + ) ( o 1 + e ) 。 令= 0 0 1 ，则p ( 霉) 0 0 8 9 这比起j a c o b i 方法来说，它确实大大提高了收敛速度，而且迭代次数可以控 制，这是我们所乐意看到的 通过以上的例子说明，若系数矩阵为非奇异m 阵，j a c o b i 迭代收敛的很慢， 或者说j a c o b i 的特征值不易求，甚至g a u s s - s e i d e l 迭代矩阵的特征值不容易计算 时，交替方向法是一个行之有效的方法，它不仅加快了收敛速度，减少了迭代次 数，而且运算的精度是可以控制的 1 6 第三章满足条件的线性方程组的直接解法 本章通过对可逆系数矩阵4 的j a c o b i 分裂，利用j a c o b i 分裂收敛的条件， 把线性方程组的系数矩阵的逆通过级数的形式表示，从而找到了一条快速解决满 足条件的线性方程组的方法，即当系数矩阵a 的j a c o b i 收敛时，使得线性方程 组的解x = a - 1 b = d b ，或者z = a - 1 b = ；6 大大提高了计算速度，而且得到 的解是线性方程组的精确解 3 1 预备知识 考虑线性方程组 a x = b ， ( 3 ，1 ) 这里a = ( a i j ) 是n x n 阶方阵，本章总假设a i l o ( i = 1 ，2 ，n ) ，z 和b 是n 阶列向量，a dlu ，这里d ，一三和一u 分别是a 的对角，严格下三角和 严格上三角矩阵 定义1 3 2 8 】设a c “，d = d i a g a ，a = d c ，称i d l i c l 为a 的比较矩 阵，且记为f l ( a ) 若q ( a ) 为m 阵，则称a 为日阵 定义1 4 4 设a c “”，若a 的比较矩阵为非奇异m 阵，则称4 为非奇异 日矩阵 定义1 5 【2 8 】称向量序列 舻) 收敛于为如果的各分量z ；收敛于石的相应 分量钆，i = 1 ，2 ，n ，记为1 i m = z ； 称矩阵序列小收敛于a ，如果小的各元素吨收敛于a 的相应元素。材，i ，j = 1 ，2 ，几，记为l i ma = a 定义1 6 1 2 8 】对于任意nxn 阶矩阵a ，若有非负实数”| | 满足条件 1 ) i a i i = 0 ，当且仅当a = o ； 2 ) i a a i l = h i i a i i ，对任何实数o ； 3 ) i i a + b i l i i a i + i i b i i ，对任何n n 阶矩阵b ； 4 ) l i a b i l l i a i b m 对任何几x 佗阶矩阵b 则称i i a i i 为矩阵a 的范数 定义1 7 【2 8 】设a 为矩阵a 的任意特征值，则有p ( a ) i a 1 1 定义1 8 2 8 】方阵a 称为可约的，如果存在置换矩阵p ，使得 p a p t = ( a a 。1 三) ， 1 7 其中a 1 ，a 3 也是方阵；否则，称a 是不可约的 引理1 3 2 8 】l i m 扩= z 的充要条件是对任意向量范数有l i m0 一一z 0 = 0 ； 1 i ma = a 的充要条件是对任意矩阵范数有 一 = 引理设a 为任意n 阶矩阵，a 七1 i m 的i a 充k 要a 条t 件是0 1 4 2 8 0p ( a ) 1 引理1 5 2 s 对任意阶矩阵b ，当且仅当p ( b ) 1 时，矩阵级数 收敛，此时有 ，+ b + b 2 + b 3 + + b 女+ ( j b ) 一1 = j + bd - b 2 + b 3 + + b 七+ 引理1 6 1 1 8 】若a = ( a i j ) 不可约，a c ：一，则有正对角阵q = d i a g ( q l ，q 2 ，) ， 使对于a = 嘞= a q ，有 矧= 七 这里k 是常数，v i ，i j 且除常数因子外，这种q 是唯一的，亦即这种a 是唯 一的，称a 为a 的最优尺度矩阵 引理1 7 4 在引理1 6 的条件下，下列各条等价： 1 ) p ( k d i - 1l c i ) 1 ； 2 ) p ( t d i _ 1l c i ) l ； 3 ) a 为日阵； 4 ) a 严格对优； 5 ) a 为日阵 引理1 8 1 2 8 设a c ”，若有正对角阵q ，使a = a q ( q a ) 为行( 列) 严格对 优，则称a 为行( 列) 广义对优 引理1 9 2 8 la 为广义行对优等价于a 为非奇异日阵 引理2 0 2 8 】若a 和b 为同阶的方阵，i b l a ，贝4p ( a ) p ( b ) 引理2 1 1 2 s 若a 为严格行对优或不可约对优，则j a c o b i 迭代收敛 引理2 2 2 s 若a 为严格行对优或不可约对优，则a 为非奇异矩阵 引理2 3 4 若矩阵a 为强对角占优矩阵或不可约对角占优矩阵，则a 为非奇 异矩阵 引理2 4 【2 8 】若a = ( a ，) 是实对称对角占优矩阵且对角元素非负，则a 是正 半定的；如果a 还是不可约或非奇异的，则其为正定阵 1 8 3 2 主要的结果及证明 定理7 若p ( j ) 1 , a d = d a ，c b = 0 ，则有 a b = ( i d - 1 g ) - 1 d b = d 一1 b 证明：由于p ( j ) 1 ，故有引理1 5 知 ( ，一d 一1 g ) 一1 = ，+ d 一1 c + ( d 一1 e ) 2 + ( d 一1 c ) 3 + 又因为。4 d = d a ，即d - 1 a = a d 于是有 d 一1 c d 1 = ，i d 一1 a ) d 一1 = d 一d 一1 a d 一1 = d - 1 ( ，一a d - 1 ) = d 一1 d 一1 d 所以 a b = ( d c ) - 1 b = 【d ( i d - 1 g ) 】一b = ( i d - 1 c ) “d - 1 b = 口+ d 一1 c + ( d 一1 g ) 2 + ( d 一1 c ) 3 + ) d 一1 b = ( d - 1 + d _ 1 c d - 1 + ( d _ 1 c ) 2 d 1 + ) b = ( d 一1 + d 一1 d 一1 c + d 一1 c d 一1 d 一1 c + ) b = d 一1 b + d 一1 d 一1 c b + d 一1 c d 一1 d 一1 c b + = d b 所以命题成立 推论1 若d i a g d = a i ( a o ) ，c b = 0 ，则有a b = ：6 证明：由于d i a g d = a i ( a o ) ，所以a d = d a ，且c b = 0 由定理7 得a 1 b = d _ 1 b = ( o ，) - 1 b = ：6 定理8 若p ( j ) p ( b ) ，所以有a = 4 1 一；b ) 又s p ( b ) ，故p c b ) 1 由引理1 5 知 于是有 ( i - j 1 矿- = ，+ 兰8 b + 万b 2 + - + 菩+ a - - 1 b = ：；( hi b + 晏2 + + 菩+ ) 6 ：如i b 。+ ；2 b + 菩。+ - ) 又b b = 0 ，所以a - l b = ；( ，+ 7 b + 尝2 + ) 6 = ；b 所以命题成立 椰 帅 豺，卿， 一 一 r ， m l 例3 线性方程组a x = b 其中 3 3 数值例子 a = 巨n 舡- 111 1 1 = i 。1 所以由定理7 得a 一1 b = d 一1 b = 6 = ( j 1 ，一i i ，。i - ) t 6 = ( _ l ，一；，j 5 ) t ， a = ( 一i i 二i ) 2 1 汀忙( o 2 2 ) ( 0 o o ) - 1 ) = o 0 0 ) - 1 ) 埘 z = a 一