第三章線性代數(shù)方程組ppt課件

1、第三章第三章 線性代數(shù)方程組線性代數(shù)方程組 3.1 問題概述問題概述 3.2 直接法直接法 3.3 迭代法迭代法 3.4 稀疏矩陣稀疏矩陣 3.5 其他特殊方式的矩陣其他特殊方式的矩陣 3.1 問題概述 3.1.1 問題提出 線性代數(shù)方程組231322112222212111212111bAxbxaxaxabxaxaxabxaxaxaMNMNMMNNNN用矩陣形式表示：33,2121212222111211mnmnmmnnbbbbxxxxaaaaaaaaaA系數(shù)矩陣系數(shù)矩陣未知向量未知向量右頂端右頂端 當M=N時，假設A非奇特，那么方程組3-1 存在獨一解。 3.1.2 矩陣的存儲與構造 1.

2、 存儲方式 a.滿存方式 N2個實數(shù) b.部分存儲方式 非零元素個數(shù) 稀疏矩陣、對稱矩陣、塊狀矩陣 2. 存儲構造 數(shù)組在計算機內存中總是一維存放的 但是它的順序在不同的高級言語中不 一定一樣。3.1.2 例如，F(xiàn)ORTRAN言語中的矩陣是按列 存放的：,11a,21a,1na,12a,22a,2na,1na,2na,nna 3. 存儲方式與存儲構造是不同的兩個概念 4. 矩陣的邏輯維數(shù)與物理維數(shù) 邏輯維數(shù)：實踐參與計算的矩陣階數(shù) 物理維數(shù)：該矩陣能夠出現(xiàn)的最大階數(shù) 例如，調用一個子程序，計算一個44矩陣 的轉置，調用方式為： CALL MATINVA, AI, NL, NP 這里，NL是邏輯

3、維數(shù)，=4。而NP是物理 維數(shù)，即數(shù)組A的實踐定義維數(shù)。3.1.2 假定NP=6，那么44矩陣存放于66矩陣中：7(1)5(7)1(13)2(19)X(25)X(31)2(2)3(8)1(14)1(20)X(26)X(32)4(3)9(9)0(15)5(21)X(27)X(33)8(4)1(10)2(16)4(22)X(28)X(34)X(5)X(11)X(17)X(23)X(29)X(35)X(6)X(12)X(18)X(24)X(30)X(36)NLNP NL=4, NP=6 NP,NP Dimension A(6,6) A內存放 44矩陣 NLNL 求A( i,j ) 1 i,j 4 但

4、地址是： j-1NP +i 3.1.3 向量范數(shù)、矩陣范數(shù)向量范數(shù)、矩陣范數(shù) 定義定義1. 對于任一向量是對于任一向量是 ，按照一定，按照一定 規(guī)那么確定一個實數(shù)與它對應。規(guī)那么確定一個實數(shù)與它對應。 該實數(shù)記為該實數(shù)記為 ， 假設假設 滿足下面三個性質：滿足下面三個性質： 那么實數(shù)那么實數(shù) 稱為向量稱為向量x的范數(shù)。的范數(shù)。 設設 ，那么它常用的幾，那么它常用的幾 種范數(shù)有：種范數(shù)有：nRx 。對，對任意實數(shù)，yxyxRyxxxxxn,3;2; 0001x,21Tnxxxxxx3.1.363,max53432112112112222212nniinniinxxxxxxxxxxxxxx 可以驗

5、證，以上定義的幾種范數(shù)均滿足 三個范數(shù)的性質。它們的幾何意義見圖3.1 從向量范數(shù)出發(fā)可以定義矩陣范數(shù)。 定義2：設A為nn階矩陣。定義AxxAxAnnRxxRxx10maxmax3.1.35 . 5124 . 712xxx321,xxxx2x1x3x0 . 25 . 55 . 4|x|2 圖3.1 向量范數(shù)的幾何意義3.1.3 這樣定義的矩陣范數(shù)具有性質： 。對有對，對BABARRBxAAxRxBABARRBAARAAAnnnnn,5;,4;,3;2; 00, 01 顯然，這樣定義的矩陣范數(shù)與向量范數(shù) 的定義方法有關。 前面三種常用的向量范數(shù)相應的矩陣范數(shù)是的最大特征值是AAAT112733

6、.1.393max83max11111njijniniijnjaAaA 另外，關于范數(shù)有一個很重要的等價定理： 定理：有窮線性空間上的一切范數(shù)都是 等價的。即對恣意兩種范數(shù) 有關系式： ,有關的常數(shù)，是與其中MmMm, 3.1.4 線性代數(shù)方程組的性態(tài) 線性方程組(3-2) 的解完全由A和b確定。 在實踐問題中: 由于各種緣由，A和b是有誤差 研討A和b的微小攝動對解x的影響非常重要的 這種影響的大小反映了問題的“性態(tài)。 在3-2中，假設A-1存在，那么解可表示為 x=A-1b 又設 為A,b的微小攝動，而 是由 此而使x產(chǎn)生的誤差。即bA,x bbAAAx13.1.3 例如 在4位字長的計算

7、機上解方程組 的。）是“壞條件”象（微小攝動而得?？梢韵胪ㄟ^只是則方程組矛盾。事實上改成：如果把誤差很大作為主元的消元法解得而取此方程組的真解是103103113113147. 5374. 1000. 141.15122. 4000. 3103500. 3,951. 9:000. 32 . 6,6658.13:103147. 5374. 1000. 141.15127. 4000. 321212111212121xxxxxxaxxxxxx3.1.3 現(xiàn)給出普通情形的估計式 設 那么可以證明以下估計式 其中 可見，k(A)近似表示了方程組求解的誤差的 相對放大率11AA 12321bbAAAkx

8、x 111AAAAAk3.1.3 換言之， 的大小 表示問題的病態(tài)程度 k(A)稱為計算問題3-2的條件數(shù) Condition Number 如今再看前例： 2 .78426 .1425501. 5max0 .6000 .2006 .8258 .274347. 1000. 1127. 4000. 31111111111AAAkACondAaAAAniijnj1 AA3.1.3 可見計算對象3-10是病態(tài)的。 該當指出： 1. det(A)的值小未必會引起A病態(tài) 例如： det(A)=0.02，而A是好條件的。 2. 嚴厲來說，估計式只給出了好條件 的充分條件，但不是必要條件。 3. 由于數(shù)據(jù)誤

9、差在線性系統(tǒng)中引起 的固有的不可靠的使得任何過分 精度要求的企圖都是徒勞的。2 . 010. 00 . 010. 0A3.2 3.2 直接法直接法3.2.1 3.2.1 直接三角分解法直接三角分解法LULU分解分解 思索思索 AX=b AAX=b A非奇特非奇特 在在 Gauss Gauss 消去法中，每一步消元過程消去法中，每一步消元過程 相當于對相當于對A A作一次初等變換。即左乘一個初作一次初等變換。即左乘一個初 等變換矩陣等變換矩陣T T。 第一步：第一步：1331001011131211nlllT03.2.1 第k步)143(11111, 1nkkkkllT000 到k步以后A化為

10、當k=n-1時，A化為上三角陣U，即 因此)153(11ATTTkk)163(121UATTTnn)173(111211LUUTTTAn3.2.1 其中 為下三角矩陣，稱3-17為A的三角分解。 由Ti性質，可以知1111, 11iniiillT)183(111211nTTTL1111121323121111211nnnnnllllllTTTL003.2.1 Gauss 消去法的根本步驟435311612294321xxx 75. 25 . 055 . 225. 1055 . 00294:1413,1422321xxx 5 . 15 . 05100055 . 00294:25 . 025. 1

11、3321xxx3.2.1 所作的初等變換為5 . 225. 1055 . 0029431164229410410142001 T1 * A = A1100055 . 002945 . 225. 1055 . 0029415 . 025. 10010001 T2 * A1 = A2 u 例：設記084162122A3.2.1 那么，它的LU分解為： 1120110011100100011020110012000401222400401221101012400401220841621221021111211122112121TTLATAATAuAAATT左乘左乘3.2.1 假設有了LU分解。那么解

12、方程組就 變得非常容易了。由于bLYUXYbLUXAXLUA則令 由于L,U都是三角矩陣，那么Y,X 都可以很 容易從上面兩式中求得。 假設預先知道A存在LU分解，那么我 們可以直接把這種分解求出來。3.2.115. 0105 . 15 . 05 . 055 . 005. 049255 . 15 . 05100055 . 002945 . 15 . 05 . 254145 . 05423, 543515 . 2410142001100055 . 0029415 . 2410142001311642294435332231321321321xxxxxxxxxyyyyyyULAbT解：解：前例：3

13、.2.1 但是 Gauss 消去法并不是對任何 非奇特矩陣都能順利進展。如 我們有這樣的結果： 任何非奇特的nn階矩陣A，總存 在一個陳列矩陣P，使PA能進展LU分 解。 上述結果闡明，非奇特矩陣總是 能進展選主元的Gauss消去法。0110A3.2.1 331421642100010642010100642331421642行變換選主元消元消去法：選主元的Gauss021423.2.1 為使 LU 分解規(guī)范化。把 U 改換成 DU 是可行的。其中 D 是非奇特對角矩陣。而 U 那么為單位上三角矩陣。如1000102111200040002200040122 稱 A=LDU 為矩陣 A 的 L

14、DU 分解。 定理：設 nkaaaaaaAnnaAkkkkkkij, 2 , 12111211階矩陣。是一個3.2.1 表示 A 的各階主子矩陣。那么，A 存在 獨一的 LDU 分解的充分必要條件是： Ak k=1,2,.,n都是非奇特。 如 A 為對稱正定，或者對角占優(yōu)，那么 A 的各階主子矩陣均非奇特。 如今我們直接從 A 求 LU 分解： 設矩陣 A 有 LDU 分解。記 LD=L。那么 A=LU，L為下三角矩陣，U為單位上三角。 這種LU分解稱為 Crout 分解。 3.2.1LUAuuuuuullllllllllaaaaaaaaaaaaaaaajnnjnjnnnjnnijiinnnj

15、nninijiinjnj1000100101000000221112212122211121212222211112113.2.1 行已得到。的前列和的前假定故時，時，特別，所以，因為，顯然，令：11)213(, 21203, 2 , 11193, 2 , 1, 2 , 1,1,1111111111111,min1kukLnjlauulainilulajnjiulaLUAnjiuuUlLjjjjiiijirrjirijiiijij3.2.1233, 1223,193, 1111111nkjlulaunkiulalnkiullaukkkrrjkrkjkjkrrkirikikkrrkirikikk

16、k類似地，有，故有所以根據(jù)由于關于關于L, U元素的存放元素的存放 從從3-22，3-23可以看出?？梢钥闯?。A的的元素元素aij在計算出在計算出 或或 以后就不再有用了。以后就不再有用了。ijliju3.2.1 故L,U的非零元素便可以存放在矩陣A中的相應位置上了。 最后， A所存放的元素是：nnnnnnlllulluul212222111211 容易證明： 1. 即是Gauss消去法中各次的主元素。nnll,113.2.1 2. 假設 A 的各階主子矩陣均非奇特， 上述過程可以不斷進展究竟。 矩陣 A 除了以上引見的 LU 分解以外， 還有一種重要的分解方法可以用于求解 線性方程組。即 Q

17、R 分解。 定理：恣意矩陣 A，總是以分解成正交 矩陣 Q 與上三角矩陣 R 的乘積： 假設 A 是非奇特的，那么在規(guī)定R的對角元 素的符號下，分解式是獨一的。 假設 ， 那么 Q 是正交矩陣RQATQQ13.2.1 常見的有 Householder 正交三角分解 有了正交三角分解以后，解方程組 就變得非常簡單：bQRXbQRXbAXT 用 Householder 變換進展分解。從而 求解線性方程組的過程是非常穩(wěn)定的。也 不用選主元。特別在方程性質不太好時， 更顯其優(yōu)越性，但計算量大。 Householder 正交三角分解還有其他用途。3.2.1 PROGRAM EXAMPLE DIMENSI

18、ON A(5,5),B(3),IND(3),C(3) DATA B /5.0,3.0,4.0/ A(1,1)=4.0 A(3,3)=3.0 N=3 NP=5 CALL LUDCMP(A,N,NP,IND,D) CALL LUBKSB(A,N,NP,IND,B) WRITE(*,*) B C(1)=1. C(2)=2. C(3)=3. CALL LUBKSB(A,N,NP,IND,C) WRITE (*,*) C STOP END3.2.115. 05 . 005. 0435000000000000105 . 225. 00055 . 05 . 0002940000000000003110064

19、200294LUBKSBLUBKSBLUDCMPBA的變化：前同的變化：3210 . 1DIND的值：3.2.1程序手稿原程序文件目的程序執(zhí)行程序輸出結果編輯WS編譯F77連結LINK執(zhí)行程序名庫修正圖3.2 程序調試流程圖3.2.2 迭代改良 由前面討論，我們知道，由于各種緣由， 特別是方程組本身的病態(tài)，將會導致解與真 解之間的誤差不能到達令人稱心的程度。有 各種處置病態(tài)方程組的方法。這里引見一種 簡單適用的方法。它還可以用于普通方程組 的高精度求解。該方法的根本思想是利用迭 代逐漸改善解的精度關鍵在于在迭代過程 中有些運算需用雙精度進展 迭代改善過程的框圖如下：3.2.2LUAA的三角分解

20、作 bxLUxx011：求三角方程組的解 AXb用雙精度計算殘向量： LUZZ ：求出解的改善量 Zxx1求改善解： ?Z 11xxxx1結束是否圖 3.3 迭代改善過程3.2.2 由上圖可知，迭代改良的計算，只需 在開場時作一次三角分解。以后只是反復 求解三角方程組就可以獲得解的改善。 關于解的改善的程度有以下結論： 假設在浮點數(shù)的尾數(shù)是 t 位二進制的 計算機上用消去法計算。A 的條件數(shù)為 普通可設 那么：經(jīng)過一次迭代，解的精度近似地改善 了 t-p 位。因此迭代次數(shù) k 滿足 k(t-p)t 就夠了。 或近似地用估算式： pACond2tp 0 112logZxtk3.2.3 奇特值分解

21、SVD 解方程組時，經(jīng)常會出現(xiàn)奇特或非常 接近于奇特的情況。用通常的Gauss消去法 或者LDU分解法難以得到稱心的解。對這 類問題，我們有一個有效的方法，它叫奇 異值分解法 Singular Value Decomposition 它不但可以診斷出問題所在，而且有時能 給出一個有用的數(shù)值結果。 SVD方法基于下面這個線性代數(shù)定理， 由于定理本身不是我們研討的重點，這里 不加證明。3.2.3 定理：對恣意MN矩陣A，這里MN，它都可以分解成以下方式： A=UWVT其中：U是MN列正交矩陣； V是NN 正交矩陣； W是NN對角矩陣。且對角元素非負。即： NlkuuVwwwUAklMiilikTn

22、,1121且3.2.3IVVUUNlkvvTTNjkljljk用矩陣表示：,1,1 由于V是方陣，故它還是行正交即 不論矩陣A能否奇特。SVD分解都能做到。而且它“幾乎是獨一的。即允許U，V的列進展變換并進展W相應交換的前提下是獨一的。 假設A是NN方陣，那么U，V，W都是方陣。且分解式可寫為：. IVVT3.2.3TjTjUwdiagVAVwdiagUA11由此但是，假設其中有一些 或非常接近于0，即A奇特或接近奇特，那么A-1就難以求得。因此，SVD分解可以經(jīng)過判別 的大小來分析A的性態(tài)。 當A是奇特時，我們就思索0jwjw jjwwACondminmax243bAxnn在某種意義下的解。

23、3.2.3 由代數(shù)知識，有 當 rank(A)0; 秩N; 但可以證明：零度秩。如今再看看分解的意義。3.2.3分解現(xiàn)實上分別構造了的零空間和域的各一組正交基。由一切 對應的的第j列向量是張成域的一組正交基。由一切對應的的第j列向量是張成零空間的一組正交組。如今思索3-24的解。假設 的域， 那么方程有無窮解。由于零空間的任何向量的0jw0jwAbbxVwwwuuuuTnjnj121,3.2.3buxvwuxvwxvwxvwxvwxvwuuuxVwwwwuuuxAkwnkkTkkniiTiiTnnTjjTTnjTnjn011221112121, 故恣意的域中向量b可以由 線性表示， 即這樣的

24、張成域的一組基。0kkwu0kkwu10122112121, 0,0), 2 , 1(00, 2 , 1000000kwnkkkjjjnnkjTjjTkkTnTTnTTvxvjwvvvXnkvxvxxvwnkxvwxvxvxvwwwXWVUUWVAAxAx于是內積即得上式兩邊與的下標對應于的線性組合時表示成由此若令向量正交與即時當故即是非奇異陣，得及由的零空間，即設3.2.323.2.3 xxxxxxbbUUbUwdiagUWbUwVdiagUWVxUWVAxwwbUwdiagVxbAxxxbbAxxAxxAbxAxxAxTTjTjTTjjTj現(xiàn)在要證明：。之和：的向量及零空間中表示為特解因為

25、任何解向量都可以的所有解向量中長度最小式還是事實上，的解。式是問題故則時，取當令的解仍然是方程所以的解時，是當是零空間中的向量。即設解上，仍是方程的解：解的線性組合加在某個)243(24311010,10, 00, 10, 0jjjjww令對角陣0jwijubAb的域，是屬于因為3.2.3 的解。是所有解中，長度最小中的特解的長度最?。换蛘哒f，換言之，當，故綜合以上兩點：時，自然當上式長度更小，又才能使分量時，最好取這些下標所以取分量時，由于當因為xxxxxVxvwxvjbuwwxvxvxvbuwbuwbuwxVbUWxVxVxxVxxxTTjjTjTjjjnTnTTTnnTTTTTTT000

26、00, 0, 0101112211221113.2.3 的大小控制。誤差值被“零化”；多少大小的奇異值可以較小。但應注意掌握倒可能會使問題求最小長度解此時，把方程作為奇異可能很大差分解直接求解將會使誤分解或用時，件數(shù)對病態(tài)方程組，即使條最小的解。即使向量長度最小二乘意義下的解，式給出了無解，但的域時，當說明：rrAXbrSVDLUwwAxbrAbii21:1minmax. 2243. 13.2.3以上討論用圖表示如下：xbAbAx 零空間的解dAx 解的SVDdAx 的域Ad c的解 cAx 最小二乘解的SVDcAx 零空間c圖圖 3.4 解空間表示圖解空間表示圖3.2.3 TvTTVWUUW

27、VASVDAbAXbArankArankbAbAX33162031612131612100003000232231213123403223121,3, 2001,231316161321232232322313161613212，其中分解：進行把最小長度解?，F(xiàn)求最小二乘意義下的為矛盾方程組，無解所以因為，是矛盾方程組。例：下列線性代數(shù)方程1u2u3.2.3 3219191361221031212012312342312102123162012221133213bUVxukukAxRxkvAuuvArankAT：原方程組的最小長度解即有，且域的一組基為：域的維數(shù)為，且零空間的一組基為零度為奇異，

28、且由此，3.3 迭代法迭代法 迭代法適用于解高階稀疏非迭代法適用于解高階稀疏非病病 態(tài)方程組。它只需求存儲非零元態(tài)方程組。它只需求存儲非零元素。素。 但對有些問題，迭代能夠發(fā)但對有些問題，迭代能夠發(fā)散散 或收斂很慢?；蚴諗亢苈?.3.1 Jacobi 迭代法迭代法 設有方程組設有方程組 其中其中A是是NN非奇特矩陣。故有非奇特矩陣。故有獨一解。獨一解。 把把3-26改寫成迭代方式改寫成迭代方式bAX 263273gBXX 于是設X(0)是一個恣意的初始迭代向量。 代入3-27的右邊，得到新的向量記為X(1)： 普通地有： 我們得到向量序列 假設 收斂于 X ，即： 那么向量 X 是3-27的

29、解。 現(xiàn)討論解的求法及收斂性gBXX)0()1()283(, 2 , 11)(kgBXXkk , 1 , 0,kXk kX XXkklim.1 設矩陣A的對角元素 。記 那么D非 奇特。將A表示成和式 其中：0iiannaaadiagD,2211293uLCCDA方法的定義是：唯一確定。述矩陣迭代法都可以用上我們會看到，JacobiCCDSORSGJacobiaaaaaaCaaaaaCuLnnnunnL,0000000000,000000000032231131221323121 303, 2 , 1,11nibxaxanijjikjijkiii3.3.1 利用3-29式的矩陣

30、符號。Jacobi 法可以 表示成： 這里B 是 Jacobi 迭代矩陣。其定義為 gBxxkk1 333,323,3132112111TnTknkkkuLbbbDgxxxxADICCDB Jacobi 方法收斂的充要條件是： 迭代矩陣B的譜半徑1)(B3.3.1 利用這個判斷標準。，故較多的計算可以較方便檢驗由這是由于法收斂方法的一個充分條件：給出為此，的條件較難檢驗由于的特征值。是這里模最大者：譜半徑定義為特征值的BBBJacobiBJacobiBBniBiini1,1, 2 , 1max1 1,maxiiiiB即為設單位長度的特征向量BBBBBiiiiiiiii于是則3.3.1 如今討論

31、一下Jacobi方法的收斂速度 的快慢及影響速度的要素。 的精確解。是方程組其中，方法成立，則定理：若273353134311101xxxBBxxxxBBxxJacobiBkkkkkBBI111示：其證明作為思考題，提3.3.1 3-34式可作為誤差估計式，并且說 明|B|越小，x(k) 收斂越快。3-35式說 明了只需|B|不是很小，當相鄰兩次迭代向 量x(k) 和 x(k-1) 很接近時，解 x* 和 x(k) 也是很 接近的。因此，可以用 | x(k)- x(k-1)| 作為 迭代終止的判別式。這個結論對逐次逼 近法也成立。 特別，應該指出，以上討論的收斂性 及收斂速度均是對普通迭代式3

32、-27而 言。因此，其結論對以后要討論的G-S迭 代法和SOR法也成立。3.3.1 Jacobi 迭代法的計算步驟： )1, 2 , 13;2;111011akkxxbgBxxakxbDgADIBkkkk，轉則結束，否則若計算對和初始迭代向量給出精度小量，計算 nknknknknnkkknnkkkikjkjkikinknknknknnkkknnkkgxbxbxgxbxbxgxbxbxxxijxxxgxbxbxgxbxbxgxbxbxJacobi000:1, 10002211212121211112121111221112121121211112121來求代替故可考慮用已求出。時，由上可知當計算

33、迭代格式：仔細寫出3.3.2 Gauss-Seidel 迭代法。 G-S迭代法的根本思想來自Jacobi 迭代法。只是迭代矩陣B不同。3.3.2 這就是 Gauss-Seidel 迭代格式，它 也可寫為： 假設用3-29式記號，那么G-S迭代式可 表示為： 或 其中 ), 1(1111nigxbxbxinijkjijijkjijki bxCxCDkukL1 3631hxLxkkULCDUCDLbDLIhULIL11111373， 有關收斂性和收斂速度的討論完全 與 Jacobi 方法一樣，只是迭代陣為L。3.3.3 逐次超松弛SOR法 SOR法定義為： 法可寫成：的矩陣記號利用法。法退化為時，

34、當。是實數(shù)，稱為松弛因子其中SORSeidelGaussSORnixgxbxbxkiinijkjijijkjijki,2931, 2 , 11111113.3.3 1)(,3931383111111111LSORJacobiCDUCDLbDLIhIULILhxLxDxbxCxCDxULkkkkLkLk法收斂的充要條件是法類似，與其中：或2.3.131)(12:403403201)(LSORSORASORLoptopt，可以證明對某些特殊類型的矩陣。為稱為最佳松弛因子，記因子法收斂速度最快的松弛使收斂的充分條件。也是是對稱正定矩陣，則另外，若收斂的必要條件是，因此可以證明曹志浩等求根參考矩陣計算

35、與方程3.3.3 三種迭代法的比較： 1. 普通情況下，J方法與G-S方法比較 并無優(yōu)劣。收斂情況與速度均不一定。 例：01120211002210122019 . 09 . 09 . 019 . 09 . 09 . 01BBA法收斂方法不收斂SGJ 法不收斂方法收斂SGLJB, 1, 1 1, 1LB3.3.3 2. 但是具有相容次序的矩陣，在一樣 精度要求下，迭代次數(shù)分別為： Jacobi 方法：1154 G-S 方法：578 SOR 方法：59 可見對這類矩陣，G-S 法比J方法快一倍， 而 SOR 法的收斂速度可提高一個數(shù)量級。 最后引見一類對于三種方法都收斂的 矩陣。先定義可約矩陣和

36、對角占優(yōu)矩陣：opt3.3.3 (1). 稱n階方陣為可約矩陣，假設存在n階 陳列陣P，使得 其中A11為r階方陣，A22為n-r階方陣 不是可約矩陣就是不可約矩陣 (2). 稱 n 階方陣A是對角占優(yōu)矩陣，假設 假設上式嚴厲不等號成立，那么稱A為嚴厲對角 占優(yōu)矩陣。4130221211AAAPAPT42311niaanijjijii，3.3.3 (3). 稱A是不可約對角占優(yōu)矩陣。假設A是不可 約的且對角占優(yōu)，而3-42式中至少對一 個 i 有嚴厲不等號成立。 我們有如下結論： 1. 假設A是嚴厲對角占優(yōu)或不可約對角占優(yōu) 矩陣，那么A非奇特。 2. 假設線性方程組系數(shù)A是上述矩陣，那么： 1

37、J方程和G-S方法都收斂。 2當 SOR方法收斂。10 3.4 稀疏矩陣 前面引見了直接法和迭代法。但是實 踐中如何選擇計算方法是一個很復雜的問 題。需求思索的要素很多，主要有： 1.方程組的性質；病態(tài)、對角占優(yōu)、正定等 2.相類似問題出現(xiàn)的次數(shù)； 3.方程組的階數(shù)； 4.計算機的容量、字長、運算速度等； 5.系數(shù)矩陣的構造；稀疏、三對角等 6.對結果的精度要求。3.4 迭代法是解超高階線性代數(shù)方程組 的重要方法之一，但是它也有缺陷： 不適宜解病態(tài)問題； 精度不高； 收斂速度依賴于加速因子的選?。?收斂性不能保證； 所需乘除運算量大。 在這些方面，相對來說，直接法運算 步驟一定，運算次數(shù)有限，

38、精度高。對解 大型稀疏矩陣問題可以利用和堅持系數(shù)矩 陣的稀疏性來降低存儲容量和縮短計算時 間。3.4.3 但是，為了堅持系數(shù)矩陣的稀疏性。必需 運用特殊的計算方法和高級程序設計技術。 近年來在這方面有較大的開展。其優(yōu)越性 大大超越了迭代法。 在這一節(jié)里，不詳細引見計算方法， 只給出一些常用的規(guī)范稀疏矩陣方式。同 時給出一種普通稀疏矩陣的存儲構造。這 一節(jié)里還給出一個有效的計算公式。 3.4.1 稀疏矩陣的構造和存儲 從本質上講，解稀疏問題的方法與 普通Gausss消去法LU分解法并沒有什么 不同，只不過前者更注重于運算過程中 對零元素填入量的控制。 稀疏系數(shù)矩陣問題的直接法必定依 賴于矩陣的稀

39、疏外形，下面列舉的是常 見的規(guī)范的稀疏矩陣。 1.稀疏矩陣的構造3.4.1帶 對 角塊三角陣塊三角陣單邊塊對角雙邊塊對角eacdb單邊塊三角f圖圖 3.5 ?3.4.1雙邊帶三角單邊帶對角雙邊帶對角其他其他kgijh圖圖 3.6 稀疏矩陣的方式稀疏矩陣的方式3.4.1 2. 稀疏矩陣的存儲 普通矩陣的存儲方式有兩種：滿存和 部分存儲。稀疏矩陣那么采用后一種方式。 稀疏矩陣的種類不同，所采用的存儲 方法也不一樣，但是不論采用什么方法，它 的規(guī)范有兩條： 1節(jié)省存儲空間 ； 2存取方便，即節(jié)省存取時間。 存儲方法的選擇普通要根據(jù)矩陣的 種類和對程序的要求在上述兩個規(guī)范之間 權衡。3.4.1(1)

40、帶對角矩陣的存儲 imjkmjibmjiammjiakiijij10,0,，這里當當為半帶寬。稱當圖圖 3.7 帶對角矩陣的存儲方式帶對角矩陣的存儲方式nnijaA)()12()(mnijbB3.4.1(2)塊三角型矩陣的存儲 H1i1iLil+1N1H2 N2 Hl+1aijHl Nli1i2il-1ilN1N2NLbbID2Lb1b2bM12111llllllHHNiiH11lMNMB 110,0,llklijllijnnijnnijibijaiiiijaaA則設時當 1211lllhllhijiiiiiiNk這里：iL圖圖 3.8 塊三角型矩陣的存儲方式塊三角型矩陣的存儲方式3.4.1(

41、3) 普通稀疏矩陣的存儲B：一維存儲非零元素按行mmJA：B中相應元素所在的列號A中IA：每行第一個非零元素在B中的下標。kijbelsea0 jkJAiIAkiIAk）使得如果211:,n3.4.1 例如：8706005040030210A12345678231421341356IAJAB圖圖 3.9 矩陣矩陣A非零元素存放的普通方式非零元素存放的普通方式3.4.1 (4) 對稱矩陣的存儲 由于 故只需存儲 即可。 任何外形的矩陣，包括稀疏的 和非稀疏的，只需是對稱的。 均可節(jié)省將近一半的存儲量。njiaajiij, 2 , 1,njiijaij, 2 , 1, 3.4.2 Sherman-

42、Morrison & Woodburg 公式 我們知道，矩陣求逆問題等價于解 一個線性方程組。假設我們曾經(jīng)得到矩 陣A 的逆矩陣A-1。如今想在A上作個小 小變動。如：一個元素、一行、一列， 或者部分元素，那么能否可以不再做復 雜的求逆運算，而只是在原來的A-1的基 礎上作些適當?shù)倪\算就可得到變動后的 矩陣的逆呢？回答是一定的。 假定矩陣變化為：433VUAA3.4.2 附帶復習一下內積，外積的定義： TnnnnnnjiijnnTniiiTnnuvvuvuvuvuvuvuvuvuvuvunjivuAAuvvuuvvuvuvuvvvvuuuu21222121211112121, 2 ,

43、1,即其中：外積：內積：內積、外積均有結合律叉積點積(或：uv)3.4.2 這里 uv 是外積，它表示A的變動。 Sherman-Morrison公式給出了一個計算 的方法：1vuA 44311111211111111111AvuAAAvuAAAvuAvuAvuAIAvuAIvuA 這里 從3-443-45式可以看出，給了 A-1和u，v只需作矩陣的乘積運算和一 個向量的加法：4531uAv3.4.2 4731463,1111WzAAzvvAWuAzT則：令： Sherman-Morrison公式可以直接運用 于一類稀疏線性方程組上。假設我們曾經(jīng) 有一個有效的算法得到矩陣A的逆如A 是三對角陣

44、。或者其他規(guī)范稀疏外形的 矩陣，那么要解A的稍作變動的矩陣 決議的方程組，只需運用一次或多次 Sherman-Morrison 公式即可。 但對有些稀疏問題，這個公式并不能 直接運用。理由很簡單，由于A-1不能夠在 機器內部全部都儲存著。在實踐運用中這 個公式還有變化。A3.4.2 變化一：求解求解線性系統(tǒng)問題： 首先可以對A用有效的方法解兩個輔助 問題： 得到了向量y和z后，3-48的解既是：483bXvuA493,uAzbAy5031zzvyvyx3.4.2zzvyvyxuAzbAyuAzbAyzbAvbzWbzWbWzzvbWzbAbzvWzAbvuAXTT1,11111111有時故當由

45、于證明3.4.18 變化二. 即Woodbury 公式 當在規(guī)范稀疏矩陣上添加的元素不只 是一行或一列時，我們就不能簡單地反復 上述過程。由于新的 A-1 并沒有存儲下來。 這時要用 Woodbury 公式：.,513111111NPPNVUNNAAVUAVIUAAVUATTT矩陣，是陣，是這里， 3-51式主要是計算 因此可以看到，3-51式把一個NN陣求 逆問題轉化為一個P P陣的有求逆問題。由 于 PN, 故問題得以大大簡化。11)(PPTUAVI3.4.2 。的右邊式子也同樣計算左乘用均為單位陣即可：右乘和左乘的右邊用只要證公式：證明51351311111111111111111TTT

46、TTTTTTTTTTTTUVAIUVAUVAIVUAVIUAVIUAUVAIUVAIVUAVIUAUVAIUVAAVUAVIUAAbVUAWoodbury Woodbury公式和延續(xù)地運用Sherman- Morrison公式的聯(lián)絡在于： 假設記PPvvVuuuU,1215231PkkkTVUAVUA那么那么有有3.4.2 上式闡明，假設曾經(jīng)求得A-1，計算 的方法有兩種： 1利用3-51，計算一個 PP 的逆矩陣。 2利用3-47，執(zhí)行P次。 假設A-1沒有存儲，那么解以下問題 的步驟是 (1) 解P個輔助方程組： 得矩陣1TUVA5331bxvuAPkkk543, 2 , 1PiuAzii

47、PzzzZ,213.4.21 (2) 計算PP矩陣的逆 (3) 再解輔助方程組 (4) 得方程組3-53的解 由于：5531ZVIHT563 bAy573yVHZyxTbAVHUAbAbAVUAVIUAAbVUAxTTTT111111111yVHZyT2.5 特殊矩陣 在很多問題中，我們會遇到特殊類型 的矩陣。對于這些具有特殊性質的矩陣， 不僅存儲方式上應予研討并很好利用其性 質以節(jié)省存儲，在計算方法上也要利用它 們的好的性質以減少運算量和提高算法穩(wěn) 定性。 在這一節(jié)里，我們研討幾種特殊矩陣， 對稱、正定、帶狀，和三對角矩陣。 由第二節(jié)的定理知，假設 的各階主子式 nnijaA。則LDUA , 03.5 同樣我們可以證明，假設對稱矩陣的各階主子式其中是單位下三角陣，為對角矩陣。這個分解叫做對稱矩陣的分解。對普通非奇特對稱矩陣，那么存在陳列矩陣，使故可經(jīng)過選主元方式到達分解。解線性問題可轉化為解三個簡單的線性問題：。則TLDLA , 0TLDLTLDLTLDLPAbAX zxLyDzPbLyT3.5假設是正定矩陣，那么是對稱的并且的各階主子式不等于。因此