第三章線性代數(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ù)矩陣未知向量未知向量右頂端右頂端 當(dāng)M=N時(shí)，假設(shè)A非奇特，那么方程組3-1 存在獨(dú)一解。 3.1.2 矩陣的存儲(chǔ)與構(gòu)造 1.

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

3、維數(shù)，=4。而NP是物理 維數(shù)，即數(shù)組A的實(shí)踐定義維數(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內(nèi)存放 44矩陣 NLNL 求A( i,j ) 1 i,j 4 但

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

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

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

7、機(jī)上解方程組 的。）是“壞條件”象（微小攝動(dòng)而得?？梢韵胪ㄟ^只是則方程組矛盾。事實(shí)上改成：如果把誤差很大作為主元的消元法解得而取此方程組的真解是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)給出普通情形的估計(jì)式 設(shè) 那么可以證明以下估計(jì)式 其中 可見，k(A)近似表示了方程組求解的誤差的 相對放大率11AA 12321bbAAAkx

8、x 111AAAAAk3.1.3 換言之， 的大小 表示問題的病態(tài)程度 k(A)稱為計(jì)算問題3-2的條件數(shù) Condition Number 如今再看前例： 2 .78426 .1425501. 5max0 .6000 .2006 .8258 .274347. 1000. 1127. 4000. 31111111111AAAkACondAaAAAniijnj1 AA3.1.3 可見計(jì)算對象3-10是病態(tài)的。 該當(dāng)指出： 1. det(A)的值小未必會(huì)引起A病態(tài) 例如： det(A)=0.02，而A是好條件的。 2. 嚴(yán)厲來說，估計(jì)式只給出了好條件 的充分條件，但不是必要條件。 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 消去法中，每一步消元過程消去法中，每一步消元過程 相當(dāng)于對相當(dāng)于對A A作一次初等變換。即左乘一個(gè)初作一次初等變換。即左乘一個(gè)初 等變換矩陣等變換矩陣T T。 第一步：第一步：1331001011131211nlllT03.2.1 第k步)143(11111, 1nkkkkllT000 到k步以后A化為

10、當(dāng)k=n-1時(shí)，A化為上三角陣U，即 因此)153(11ATTTkk)163(121UATTTnn)173(111211LUUTTTAn3.2.1 其中 為下三角矩陣，稱3-17為A的三角分解。 由Ti性質(zhì)，可以知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 例：設(shè)記084162122A3.2.1 那么，它的LU分解為： 1120110011100100011020110012000401222400401221101012400401220841621221021111211122112121TTLATAATAuAAATT左乘左乘3.2.1 假設(shè)有了LU分解。那么解

12、方程組就 變得非常容易了。由于bLYUXYbLUXAXLUA則令 由于L,U都是三角矩陣，那么Y,X 都可以很 容易從上面兩式中求得。 假設(shè)預(yù)先知道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 消去法并不是對任何 非奇特矩陣都能順利進(jìn)展。如 我們有這樣的結(jié)果： 任何非奇特的nn階矩陣A，總存 在一個(gè)陳列矩陣P，使PA能進(jìn)展LU分 解。 上述結(jié)果闡明，非奇特矩陣總是 能進(jìn)展選主元的Gauss消去法。0110A3.2.1 331421642100010642010100642331421642行變換選主元消元消去法：選主元的Gauss021423.2.1 為使 LU 分解規(guī)范化。把 U 改換成 DU 是可行的。其中 D 是非奇特對角矩陣。而 U 那么為單位上三角矩陣。如1000102111200040002200040122 稱 A=LDU 為矩陣 A 的 L

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

15、nninijiinjnj1000100101000000221112212122211121212222211112113.2.1 行已得到。的前列和的前假定故時(shí)，時(shí)，特別，所以，因?yàn)椋@然，令：11)213(, 21203, 2 , 11193, 2 , 1, 2 , 1,1,1111111111111,min1kukLnjlauulainilulajnjiulaLUAnjiuuUlLjjjjiiijirrjirijiiijij3.2.1233, 1223,193, 1111111nkjlulaunkiulalnkiullaukkkrrjkrkjkjkrrkirikikkrrkirikikk

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

17、R 分解。 定理：恣意矩陣 A，總是以分解成正交 矩陣 Q 與上三角矩陣 R 的乘積： 假設(shè) A 是非奇特的，那么在規(guī)定R的對角元 素的符號(hào)下，分解式是獨(dú)一的。 假設(shè) ， 那么 Q 是正交矩陣RQATQQ13.2.1 常見的有 Householder 正交三角分解 有了正交三角分解以后，解方程組 就變得非常簡單：bQRXbQRXbAXT 用 Householder 變換進(jìn)展分解。從而 求解線性方程組的過程是非常穩(wěn)定的。也 不用選主元。特別在方程性質(zhì)不太好時(shí)， 更顯其優(yōu)越性，但計(jì)算量大。 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í)行程序輸出結(jié)果編輯WS編譯F77連結(jié)LINK執(zhí)行程序名庫修正圖3.2 程序調(diào)試流程圖3.2.2 迭代改良 由前面討論，我們知道，由于各種緣由， 特別是方程組本身的病態(tài)，將會(huì)導(dǎo)致解與真 解之間的誤差不能到達(dá)令人稱心的程度。有 各種處置病態(tài)方程組的方法。這里引見一種 簡單適用的方法。它還可以用于普通方程組 的高精度求解。該方法的根本思想是利用迭 代逐漸改善解的精度關(guān)鍵在于在迭代過程 中有些運(yùn)算需用雙精度進(jìn)展 迭代改善過程的框圖如下：3.2.2LUAA的三角分解

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

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

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

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

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

25、任何解向量都可以的所有解向量中長度最小式還是事實(shí)上，的解。式是問題故則時(shí)，取當(dāng)令的解仍然是方程所以的解時(shí)，是當(dāng)是零空間中的向量。即設(shè)解上，仍是方程的解：解的線性組合加在某個(gè))243(24311010,10, 00, 10, 0jjjjww令對角陣0jwijubAb的域，是屬于因?yàn)?.2.3 的解。是所有解中，長度最小中的特解的長度最??；或者說，換言之，當(dāng)，故綜合以上兩點(diǎn)：時(shí)，自然當(dāng)上式長度更小，又才能使分量時(shí)，最好取這些下標(biāo)所以取分量時(shí)，由于當(dāng)因?yàn)閤xxxxVxvwxvjbuwwxvxvxvbuwbuwbuwxVbUWxVxVxxVxxxTTjjTjTjjjnTnTTTnnTTTTTTT000

26、00, 0, 0101112211221113.2.3 的大小控制。誤差值被“零化”；多少大小的奇異值可以較小。但應(yīng)注意掌握倒可能會(huì)使問題求最小長度解此時(shí)，把方程作為奇異可能很大差分解直接求解將會(huì)使誤分解或用時(shí)，件數(shù)對病態(tài)方程組，即使條最小的解。即使向量長度最小二乘意義下的解，式給出了無解，但的域時(shí)，當(dāng)說明：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，其中分解：進(jìn)行把最小長度解。現(xiàn)求最小二乘意義下的為矛盾方程組，無解所以因?yàn)?，是矛盾方程組。例：下列線性代數(shù)方程1u2u3.2.3 3219191361221031212012312342312102123162012221133213bUVxukukAxRxkvAuuvArankAT：原方程組的最小長度解即有，且域的一組基為：域的維數(shù)為，且零空間的一組基為零度為奇異，

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

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

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

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

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

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

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

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 法的收斂速度可提高一個(gè)數(shù)量級。 最后引見一類對于三種方法都收斂的 矩陣。先定義可約矩陣和

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

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

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

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

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

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

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

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

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

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

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

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