解線性方程組的直接方法

1、1第第5 5章章 解線性方程組的直接方法解線性方程組的直接方法25.1 5.1 引言與預(yù)備知識(shí)引言與預(yù)備知識(shí) 5.1.1 5.1.1 引言引言 線性方程組的數(shù)值解法一般有兩類： 1. 直接法 經(jīng)過有限步算術(shù)運(yùn)算，可求得方程組精確解的方法(若計(jì)算過程中沒有舍入誤差). 但實(shí)際計(jì)算中由于舍入誤差的存在和影響，這種方法也只能求得線性方程組的近似解.3 2. 迭代法 是用某種極限過程去逐步逼近線性方程組精確解的方法. 4 5.1.2 5.1.2 向量和矩陣向量和矩陣 用 表示全部 實(shí)矩陣的向量空間， 表示全部 復(fù)矩陣的向量空間. nmRnm nmCnm mnmmnnijnmaaaaaaaaaaAA21

2、2222111211)(R這種實(shí)數(shù)排成的矩形表，稱為 行 列矩陣. mnnnxxxxRx21稱為 維列向量. n5,21naaaA其中 為 的第 列. iaAi,21TmTTbbbA其中 為 的第 行. TibAi 也可寫成行向量的形式 寫成列向量的形式6 (5) 單位矩陣 矩陣的基本運(yùn)算： (1) 矩陣加法 ,BAC (2) 矩陣與標(biāo)量的乘法 .,ijijacAC (3) 矩陣與矩陣乘法 ).R,R,R(1pmpnnmnkkjikijCBAbac,ABC )R,(nmijijijCBAbac (4) 轉(zhuǎn)置矩陣.,RijijTnmacACA,R21nnneeeI7 (6) 非奇異矩陣 設(shè).R,

3、RnnnnBA則稱 是B 如果 存在，1A則稱 為非奇異矩陣. A 如果 均為非奇異矩陣，nnBA R,其中 .,2, 1,0 ,0 , 1 ,0 ,0nkeTk, IBAAB如果A的逆矩陣，,1A記為.)()(11TTAA且.)(111ABAB則 (7) 矩陣的行列式 設(shè),RnnA則 的行列式可按任一行(或列)展開，A8),2, 1()(det1niAaAnjijij其中 為 的代數(shù)余子式，ijAija,)1(ijjiijMA 行列式性質(zhì)：.R,),()det(det)(det a)(nnBABAAB即 ija 的余子式. .R),(det)(det (b)nnTAAA.RR,),(det)

4、(det (c)nnnAcAccA.0)(det (d)是非奇異矩陣AA為元素ijM9 5.1.3 5.1.3 特殊矩陣特殊矩陣 設(shè) .R)(nnijaA (1) 對(duì)角矩陣 (2) 三對(duì)角矩陣.01ijaji，如果當(dāng) (3) 上三角矩陣 .0ijaji，時(shí)如果當(dāng) (4) 上海森伯格（Hessenberg）陣 .01ijaji，時(shí)如果當(dāng) (5) 對(duì)稱矩陣 .AAT如果.0ijaji，時(shí)如果當(dāng)10 (6) 埃爾米特矩陣 .,CAAAHnn如果設(shè) (7) 對(duì)稱正定矩陣 , (a) AAT如果.0),(,R (b) AxxxAxxTn對(duì)任意非零向量 (8) 正交矩陣 .1TAA如果 (9) 酉矩陣 .

5、,CH1AAAnn如果設(shè) (10) 初等置換陣 由單位矩陣 交換第 行與第 行(或交換第 列與第 列)，得到的矩陣記為 ,且 IijijijI11 (11) 置換陣 定理定理1 1設(shè) ，nnA R(1) 對(duì)任何 方程組 有唯一解. ,Rnb bAx AAIij（為交換 第 行與第 行得到的矩陣）；Aij（為交換 第 列與第 列得到的矩陣）；iAjBAIij由初等置換陣的乘積得到的矩陣. 則下述命題等價(jià)： (2) 齊次方程組 只有唯一解 .0Ax0 x(4) 存在. 1A(5) 的秩A.)(nArank.0)det(A(3)12 定理定理2 2設(shè) 為對(duì)稱正定陣，則 nnA R (1) 為非奇異矩

6、陣，且 亦是對(duì)稱正定陣. A1A (2) 記 為 的順序主子陣，則 kAA).,2, 1(1111nkaaaaAkkkkk),2, 1(nkAk亦是對(duì)稱正定矩陣，其中 (3) 的特征值 A).,2,1(0nii (4) 的順序主子式都大于零，即 A)., 2 , 1(0)det(nkAk13 定理定理3 3設(shè) 為對(duì)稱矩陣. nnA R), 2 , 1(nk或 的特征值A(chǔ)),2, 1(0nii則 為A 定理定理4 4(Jordan標(biāo)準(zhǔn)型) 設(shè) 為 階矩陣，則存在一個(gè)An非奇異矩陣 使得 P,)()()(22111rrJJJAPP0)(detkA如果對(duì)稱正定陣.14其中 .),2,1(111)(1

7、nnrinJriiinniiiiiiii且為若當(dāng)（Jordan）塊. (1) 當(dāng) 的若當(dāng)標(biāo)準(zhǔn)型中所有若當(dāng)塊 均為一階時(shí)，AiJ此標(biāo)準(zhǔn)型變成對(duì)角矩陣. 15 (2) 如果 的特征值各不相同，則其若當(dāng)標(biāo)準(zhǔn)型必為A).,(21ndiag對(duì)角陣165.2 5.2 高斯消去法高斯消去法17 5.2.1 5.2.1 高斯消去法高斯消去法 設(shè)有線性方程組 .,22112222212111212111mnmnmmnnnnbxaxaxabxaxaxabxaxaxa（2.1）或?qū)憺榫仃囆问?,2121212222111211mnmnmmnnbbbxxxaaaaaaaaa18簡(jiǎn)記為 .bAx 例例1 1)4.2(.

8、122)3.2(,54)2.2(,632132321xxxxxxxx 解解消去(2.4)中的未知數(shù) 得到,1x將方程(2.2)乘上 加到方程(2.4)上去，2)5 .2(.11432xx 第2步. 用消去法解方程組 第1步. 將方程(2.3)加到方程(2.5)上去，消去方程19(2.5)中的未知數(shù),2x得到與原方程組等價(jià)的三角形方程組 .62)6.2(,54,6332321xxxxxx顯然，方程組(2.6)是容易求解的，解為 .)3,2, 1(Tx 上述過程相當(dāng)于 112251406111bA111405140611120620051401111331)2(rrr332rrr其中用 表示矩陣的

9、第 行. iri 由此看出，用消去法解方程組的基本思想是用逐次消去未知數(shù)的方法把原方程組 化為與其等價(jià)的三角形方程組，而求解三角形方程組可用回代的方法. bAx 上述過程就是用行的初等變換將原方程組系數(shù)矩陣化為簡(jiǎn)單形式(上三角矩陣)，從而將求解原方程組(2.1)的問題轉(zhuǎn)化為求解簡(jiǎn)單方程組的問題. 21 或者說，對(duì)系數(shù)矩陣 施行一些左變換(用一些簡(jiǎn)單矩陣)將其約化為上三角矩陣. A 下面討論求解一般線性方程組的高斯消去法. 將(2.1)記為 其中 ,)1()1(bxA.),()()1()1()1(bbaaAijij (1) 第1步 ).1(k 設(shè) 首先計(jì)算乘數(shù) ,0)1(11a.),3,2(/)

10、1(11)1(11miaamii用 乘(2.1)的第一個(gè)方程，加到第 個(gè)方程上，1imi),3,2(mi消去(2.1)的從第二個(gè)方程到第 個(gè)方程中m22).,2(mi的未知數(shù) 得到與(2.1)等價(jià)的方程組 ,ix（2.7）.00)2()2(2)1(121)2()2(2)2(2)2(22)1(1)1(12)1(11mnmnmnnbbbxxxaaaaaaa簡(jiǎn)記為 ,)2()2(bxA其中 的元素計(jì)算公式為 )2()2(, bA)1(11)1()2(jiijijamaa),2;,2(njmi)1(11)1()2(bmbbiii23 (2) 第 次消元 k).,1min(,2,1(nmsk 設(shè)上述第1

11、步，第 步消元過程計(jì)算已經(jīng)完成，1k（2.8）,)()()2(2)1(121)()()()()2(2)2(2)2(22)1(1)1(1)1(12)1(11nnkknkkmnkmkkknkkknknkbbbbxxxxaaaaaaaaaaa即已計(jì)算好與(2.1)等價(jià)的方程組簡(jiǎn)記為 .)()(kkbxA24)()()1(kkjikkijkijamaa),1;,1(nkjmki).,1(mki 設(shè) 計(jì)算乘數(shù) ,0)(kkka.),1(/)()(mkiaamkkkkikik加到第 個(gè)方程i),1(mki用 乘(2.8)的第 個(gè)方程，ikmk消去從第 個(gè)方程到第 個(gè)方程中的未知數(shù) 得到與m,kx1k 元素

12、的計(jì)算公式為 )1()1(,kkbA 顯然 中從第1行到第 行與 相同. )1(kAk)( kA.)1()1(kkbxA(2.1)等價(jià)的方程組 )()()1(kkikkikibmbb25 (3) 繼續(xù)上述過程，且設(shè)),2,1(0)(skakkk直到完成第 步消元計(jì)算.s 最后得到與原方程組等價(jià)的簡(jiǎn)單方程組 ,)1()1(ssbxA其中 為上梯形. )1(sA 特別當(dāng) 時(shí)，與原方程組等價(jià)的方程組為 nm ,)()(nnbxA即 （2.10）.)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11nnnnnnnnbbbxxxaaaaaa26 如果 是非奇異矩陣，且nnA R),

13、1,2, 1(0)(nkakkk由(2.1)約化為(2.10)的過程稱為消元過程. 求解三角形方程組(2.10)，得到求解公式 ,/)()(nnnnnabx).1 ,2,1(nnk（2.11）(2.10)的求解過程(2.11)稱為回代. )(1)()(/)(kkknkjjkkjkkkaxabx 如果 由于 為非奇異矩陣，所以 的第一列一定有元素不等于零. ,011aAA27 例如 于是交換兩行元素(即 ），將 調(diào)到(1,1)位置，然后進(jìn)行消元計(jì)算，這時(shí) 右下角矩陣為 階非奇異矩陣. ,011ia11irr 11ia)2(A1n 繼續(xù)這過程，高斯消去法照樣可進(jìn)行計(jì)算.28 定理定理5 5設(shè) 其中

14、 ,bAx .RnnA (1) 如果),2, 1(0)(nkakkk將 約化為等價(jià)的三角形方程組(2.10)，且計(jì)算公式為：bAx 則可通過高斯消去法 (a) 消元計(jì)算 )1,2, 1(nk),1(/)()(nkiaamkkkkikik),1,()()()1(nkjiamaakkjikkijkij).,1()()()1(nkibmbbkkikkiki29 (b) 回代計(jì)算 ,/)()(nnnnnabx).1 ,2,1(/)()(1)()(nniaxabxiiinijjiijiii (2) 如果 為非奇異矩陣，則可通過高斯消去法(及交換兩行的初等變換)將方程組 約化為(2.10).AbAx 30

15、 算法算法1 1(高斯算法),2, 1(0)(skakkk本算法用高斯方法將 約化為上梯形，A且 覆蓋 ，乘數(shù) 覆蓋 .A)(kAikmika 對(duì)于sk,2, 1 (1) 如果 則計(jì)算停止,0kka (2) 對(duì)于 mki, 1 (a)kkikikikaama/ (b) 對(duì)于 nkj, 1 .*kjikijijamaa),1min(),1(RnmsmAnm設(shè)如果31上三角陣， 算法1第 步需要作 次除法， 次乘法，kkm )(knkm因此，本算法(從第1步到第 步消元計(jì)算總的計(jì)算量)s 當(dāng) 時(shí)，總共大約需要 次乘法運(yùn)算. nm 3/3n 數(shù) 稱為約化的主元素主元素. )(kkka 算法算法2 2

16、(回代算法)設(shè) 其中 為非奇異,bUx nnU R本算法計(jì)算 的解. bUx 對(duì)于1 ,ni (1) iibx 大約需要 次乘法(對(duì)相當(dāng)大的 ). mnssnms2/)(3/23s32 (2) 對(duì)于 nij, 1 jijiixuxx* (3) iiiiuxx/ 這個(gè)算法需要 乘除法運(yùn)算. 2/)1(nn 高斯消去法對(duì)于某些簡(jiǎn)單的矩陣可能會(huì)失敗，.0110A由此，需要對(duì)算法1進(jìn)行修改，例如 ).,2, 1(0)(kakkk在什么條件下才能保證 A首先需要研究原來的矩陣33 定理定理6 6 約化的主元素 的充要條件),2, 1(0)(kiaiii是矩陣 的順序主子式A).,2, 1(0kiDi,0

17、111 aD即（2.12）).,2, 1(01111kiaaaaDiiiii 證明證明 顯然，當(dāng) 時(shí)，定理6成立.1k 現(xiàn)設(shè)定理6充分性對(duì) 是成立的，求證定理6充分性對(duì) 亦成立. 1kk首先利用歸納法證明定理6的充分性. 34 設(shè)),2, 1(0kiDi),1,2, 1(ki可用高斯消去法將 約化到 ，)1(A)( kA,)()()()()2(2)2(2)2(22)1(1)1(1)1(12)1(11)()1(knnknkkknkkknknkkaaaaaaaaaaaAA且有 0)(iiia于是由歸納法假設(shè)有即 ,0)2(22)1(11)2(22)1(12)1(112aaaaaD35.)()2(2

18、2)1(11)()1(1)1(11kkkkkkkkaaaaaaD（2.13） 由設(shè)),2, 1(0kiDi定理6充分性對(duì) 亦成立. k 顯然，由假設(shè)),2, 1(0)(kiaiii利用(2.13)式，,0)(kkka則有利用(2.13)式亦可).,2, 1(0kiDi推出 36 推論推論如果 的順序主子式A),1,2, 1(0nkDk,1)1(11Da則 ).,3 ,2(/1)(nkDDakkkkk37于是對(duì)(2.1)施行第一次消元后化為(2.7)， 5.2.2 5.2.2 矩陣的三角分解矩陣的三角分解 下面借助矩陣?yán)碚撨M(jìn)一步對(duì)消去法作些分析，從而建立高斯消去法與矩陣因式分解的關(guān)系. 設(shè)(2.

19、1)的系數(shù)矩陣 的各順序主子式均不為零. nnA R由于對(duì) 施行行的初等變換相當(dāng)于用初等矩陣左乘 ，AA這時(shí) 化為)1(A,)2(A化為 ，)1(b)2(b,)2()1(1)2()1(1bbLAAL即 38其中 .1111131211nmmmL 一般第 步消元，k化為 , )( kA)1(kA化為 ，)( kb)1(kb,)1()()1()(kkkkkkbbLAAL相當(dāng)于 其中 39.1111,1knkkkmmL重復(fù)這過程，最后得到 ;)()1(121nnAALLL（2.14）.)()1(121nnbbLLL 記上三角矩陣 為 ，由(2.14)得到 )( nAU40,111211LUULLLA

20、n其中 111211nLLLL為單位下三角矩陣. 這就是說，高斯消去法實(shí)質(zhì)上產(chǎn)生了一個(gè)將 分解為兩個(gè)三角形矩陣相乘的因式分解，于是得到如下重要定理，它在解方程組的直接法中起著重要作用. A1111321323121nnnmmmmmm41 定理定理7 7設(shè) 為 階矩陣，An如果 的A順序主子式),1,2, 1(0niDi則 可分解為一個(gè)單位A下三角矩陣 和一個(gè)上三角矩陣 的乘積，LU 證明證明現(xiàn)在在 為非奇異矩陣的假定下證明唯一性， A 設(shè) ,11ULLUA其中 為單位下三角矩陣， 為上三角矩陣. 1,LL1,UU(矩陣的LU分解)且這種分解是唯一的. 根據(jù)以上高斯消去法的矩陣分析，存在性已得證

21、， 42.1111UULL上式右邊為上三角矩陣，左邊為單位下三角矩陣， 例例2 2,122140111A 由高斯消去法，, 1,2,0323121mmm 由于 存在，故 11U從而上式兩邊都必須等于單位矩陣，唯一性得證. ,11UULL故對(duì)于例1，系數(shù)矩陣 故 43200140111112010001A.LU44 例例3 3 5.3 5.3 高斯主元素消去法高斯主元素消去法 由高斯消去法知道，在消元過程中可能出現(xiàn) 0)(kkka 即使主元素 但很小時(shí)，用其作除數(shù)，會(huì)導(dǎo)致其他元素?cái)?shù)量級(jí)的嚴(yán)重增長(zhǎng)和舍入誤差的擴(kuò)散，最后也使得計(jì)算解不可靠. ,0)(kkka.000.3000.2000.1643.5

22、072.1000.2623.4712.3000.1000.3000.2001.0321xxx這時(shí)消去法將無法進(jìn)行；求解方程組 45用4位浮點(diǎn)數(shù)進(jìn)行計(jì)算. 精確解舍入到4位有效數(shù)字為 ,)0.3675 0.05104, 0.4904,(*Tx 解法解法1 1000.3643.5072.1000.2000.2623.4712.3000.1000.1000.3000.2001.0bA用高斯消去法 2000001.0/000.21000001.0/000.13121mm20036006400101002300520040000.1000.3000.2001.0997.12004/400123m46計(jì)算

23、解為 .)0.4000 0.09980, 0.400,(Tx,000.2000.5001002300520040000.1000.3000.2001.0顯然計(jì)算解是一個(gè)很壞的結(jié)果，不能作為方程組的近似解. 其原因是我們?cè)谙?jì)算時(shí)用了小主元 0.001，使得約化后的方程組元素?cái)?shù)量級(jí)大大增長(zhǎng)，經(jīng)再舍入使得在計(jì)算(3,3)元素時(shí)發(fā)生了嚴(yán)重的相消情況，因此經(jīng)消元后得到的三角形方程組就不準(zhǔn)確了. 47 解法解法2 2000.1000.3000.2001.0000.2623.4712.3000.1000.3643.5072.1000.231rrbA 交換行，避免絕對(duì)值小的主元作除數(shù). 0005.0500

24、0.03121mm 002.1003.3001.205000.0801.1176.30000.3643.5072.1000.26300.032m,6870.0868.1005000.0801.1176.30000.3643.5072.1000.2 48得計(jì)算解為 .*)0.3678 0.05113, 0.4900,(xxT 這個(gè)例子告訴我們，在采用高斯消去法解方程組時(shí)，小主元可能產(chǎn)生麻煩，故應(yīng)避免采用絕對(duì)值小的主元素 .)(kkka 對(duì)一般矩陣來說，最好每一步選取系數(shù)矩陣(或消元后的低階矩陣)中絕對(duì)值最大的元素作為主元素，以使高斯消去法具有較好的數(shù)值穩(wěn)定性. 這就是全主元素消去法全主元素消去法. 在選主元時(shí)要花費(fèi)較多機(jī)器時(shí)間，目前主要使用的是列主元消去法列主元消去法. .49 本節(jié)主要介紹列主元消去法，并假定(2.1)的 為非奇異的. nnA R50 5.3.1 5.3.1 列主元素消去法列主元素消去法 設(shè)方程組(2.1)的增廣矩陣為 .21212221111211nnnnnnnbaaabaaabaaaB 首先在 的第一列中選取絕對(duì)值最大的元素作為主元素，A,0max1 ,11 ,1iniiaa例如 51重復(fù)上述過程，設(shè)已完成第 步的選主元素，交換兩行1k,)(222211111211)()(nnnnkkknkknknkkkbaabaabaaabaaaa