6矩陣的三角分解法6.4-6.6

1、16.4 矩 陣 的 三 角 分 解 法26.4 矩陣的三角分解法 杜里特爾(Dolittle)分解法 消去法實(shí)際上是對線性方程組的增廣矩陣A,b做第三種初等行變換。 由于對A,b 施行第三種初等行變換相當(dāng)于用對應(yīng)的第三種初等矩陣左乘于A,b 。0)(kkkaGauss消去法的矩陣解釋消去法的矩陣解釋設(shè)約化主元素 （k=1, 2, n1）。1111iikkmM36.4 矩陣的三角分解法（續(xù)）1111ikikMmk列k行i行Mik是特殊的初等矩陣，稱為倍加矩陣，某矩陣Z左乘Mik相當(dāng)于將矩陣Z的第k行mik倍加于第i行。 46.4 矩陣的三角分解法（續(xù)）111213142122232421313

2、23334414243441112131421 112121 122221 132321 142431323334414243441111aaaaaaaamaaaaaaaaaaaam aam aam aam aaaaaaaaaa56.4 矩陣的三角分解法（續(xù)）nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111)2()2(2) 1 (121)2()2(2)2(2)2(22) 1 (1) 1 (12) 1 (11nnnnnnnbbbxxxaaaaaaa高斯消去法第1步： A(1)x=b(1)A(2)x=b(2) 矩陣表示為(2)(2)11,121

3、( , )(,)nnM MMA bAb其中21211101mM313111101Mm 6111101iiMm (1)11(1)11,(2, )iiamina6.4 矩陣的三角分解法（續(xù)）11111nnMm記111,121,nnLM MM有(2)(2)11,L AALbb76.4 矩陣的三角分解法（續(xù)）21111.1121111111nniinmLM MMM Imm8高斯消去法第k步： A(k)x=b(k)A(k+1)x=b(k+1) )()()2(2)1(121)()()()()2(2)2(22)1(1)1(12)1(11knkknknnknkkknkkknnbbbbxxxaaaaaaaaa)

4、1()1(1)()2(2)1(121)1()1(1,)1(n ,1)1(1 1)()()2(2)2(22)1(1)1(12)1(11knkkkknknnkknkkkkkkknkkknnbbbbbxxxaaaaaaaaaaa6.4 矩陣的三角分解法（續(xù)）9則有 LkA(k)= A(k+1)，Lkb(k)=b(k+1) （k=1, 2, n1） 其中1,knkikkkLMMM1,1,1111kkkkMmK列K行6.4 矩陣的三角分解法（續(xù)）10( )( ),(1, )kikikkkkamikna,1111i ki kMmk列k行i行6.4 矩陣的三角分解法（續(xù)）111,1,11111knkikkk

5、kknkLMMMImmk列6.4 矩陣的三角分解法（續(xù)）LkA(k)= A(k+1)，Lkb(k)=b(k+1) （k=1, 2, n1） 12經(jīng)過n-1步消元后，可以得到()121()121,nnnnnnLLL AAULLL bby因此，不選主元的高斯消去法消去過程,實(shí)質(zhì)是增廣矩陣A,b被左乘一系列倍加矩陣,變成上三角形矩陣U,y記( )( ), , ,nnUUAyb A byR,1,1,23213121121n nn kkknnnkMMMMMMMMLLL L R高 斯 消 去法 的 矩 陣形式1,1,1,232131211112131,1() ()n nn kkknnn nMMMMMMMM

6、MMMI RRLR6.4 矩陣的三角分解法（續(xù)）13,1111i ki kMmk列k行i行1,1111i ki kMmk列k行i行Mik及其逆矩陣 都 是 單 位下 三 角 陣 ，即 對 角 線 上方 元 素 全 為零的矩陣。6.4 矩陣的三角分解法（續(xù)）14 是將單位矩陣I的第n-1行倍數(shù)加于第n行,將第一行的倍數(shù)加于第n行, ,第二行，可見L是單位下三角矩陣。1112131,1n nMMMIL, , , UUUA bLRLyLLyALLybUAxbLxb高斯消去法的消去過程，實(shí)質(zhì)上是將A分解為兩個三角矩陣的乘積A=LU，并求解Ly=b的過程?；卮^程就是求解上三角方程組Ux=y。 6.4

7、矩陣的三角分解法（續(xù)）15A=LU : L為單位下三角陣，為單位下三角陣，U為上三角陣。這種三角分為上三角陣。這種三角分解為杜利特爾分解。解為杜利特爾分解。213132121111nnmmmmmL(1)(1)(1)11121(2)(2)222( )nnnnnaaaaaUaL為由乘數(shù)構(gòu)成為由乘數(shù)構(gòu)成的單位下三角陣的單位下三角陣 Ly=bUx=y6.4 矩陣的三角分解法（續(xù)）16定理定理2 （矩陣的三角分解）（矩陣的三角分解）設(shè) 。如果A的順序主子式det(Ai)0（i=1,2,n-1）,則A可分解為一個單位下三角陣與一個上三角陣的乘積，即 A=LU且分解是唯一的。6.4 矩陣的三角分解法（續(xù)）n

8、 nAR克勞特(Crout)分解：分解為一個下三角陣和一個上三角陣。17矩陣L和U也可以直接算出，而不需要任何中間步驟，這就是所謂的三角分解法。設(shè)A為非奇異的矩陣，且有分解式 A=LUL為單位下三角陣，U為上三角陣。111212122212111nnnnnnuuuluuAllu根據(jù)矩陣乘法，由11(1,2, )jjaujn可得U的第一行元素；6.4 矩陣的三角分解法（續(xù)）186.4 矩陣的三角分解法（續(xù)）112121212212111nnnnnnluuAlluuuu再由11 11 (2, )iial uin可得L的第1列元素1111 (2, )iialinu19121,1,12,11(,1,0

9、,0) 00jjijii jijiii iikkjijkjjuuuuallll uuu6.4 矩陣的三角分解法（續(xù)）一般地，當(dāng)ij時(上三角陣）112222121211111nnnnnnuuAuluulul有206.4 矩陣的三角分解法（續(xù)）當(dāng)i j時，有1211,12,1,11( ,1,0,0)00jjjjjijiii ji ji iikkjijjjkjjuuuallllll ul uu112222121211111nnnnnnuuAuluulul216.4 矩陣的三角分解法（續(xù)）11iijikkjijkal uu一般地，當(dāng)ij時，有當(dāng)i j時，有11jijikkjijjjkal ul u由

10、這兩個式子可得計算公式1111 (,1, ;1,2, ) (6.6)()/ (1,2, ;1,2, )iijijikkjkjijijikkjjjkual uji in inlal uuijjn jn226.4 矩陣的三角分解法（續(xù)）1111 (,1, ;1,2, ) (6.6)()/ (1,2, ;1,2, )iijijikkjkjijijikkjjjkual uji in inlal uuijjn jn利用(6.6)，可以按照先U的第k行，后L的第k列（k=1,2,n)的順序完成對矩陣A的LU分解。得到矩陣A的三角分解式后，由Gauss消去法的矩陣解釋可知：, UALLyb求解方程組Ax=b

11、等價于解兩個三角形方程組：(1), ;( 2 ), L ybyU xyx求求23利用已算出的lij，從前往后反復(fù)代入可求出下三角形方程組Ly=b的解y*：11212212111nnnnyblybllyb1111 (6.7) (2,3, )iiiikkkybybl yin6.4 矩陣的三角分解法（續(xù)）246.4 矩陣的三角分解法（續(xù)）利用已算出的uij和y*，回代可求出上三角方程組Ux=y*的解。*11*22222*11121nnnnnnxyuuxyuxyuuu1/()/ (2,3, )nnnnniiikkiik ixyuxyu xuin 25 實(shí)際計算時L的對角元lii=1不必存放，L和U中肯

12、定為零的元素也不必存放，因此L和 =U,y 可共同存放在增廣矩陣 =A,b中的相應(yīng)位置：6.4 矩陣的三角分解法（續(xù)）1111 (,1, ;1,2, ) (6.6)()/ (1,2, ;1,2, )iijijikkjkjijijikkjjjkual uji in inlal uuijjn jn1111 (6.7) (2,3, )iiiikkkybybl yinUA26111112121313111121212222232322223333333131323233()()()()()()()()()()()()()()()nnnnnnuauauauayblauauauaybluaualayab

13、uij或lij都是原矩陣 對應(yīng)的元素，減去同行左邊L的元素與同列上邊 的元素的乘積；只是對L的元素，然后需要除以U的對角元。計算順序，通常先算 的第i行,再算L的第i列。hAUU6.4 矩陣的三角分解法（續(xù)）1111 (,1, ;1,2, ) (6.6)()/ (1,2, ;1,2, )iijijikkjkjijijikkjjjkual uji in inlal uuijjn jn27i12i=1,2,n計算順序6.4 矩陣的三角分解法（續(xù)）2811121,11111222,122221,11,1,1,211,11,2121,112,112,1kkkkkkkjnkkjnkkkiii knnkk

14、kjknkikijininknjkkkjknnnnkknaaabAauuuuuuyllllllllllluuuuuyuuuuyaabaabla對方程組的增廣矩陣 經(jīng)過k-1步分解后，可變成如下形式 , AA b第1步第1步第2步第2步 第k-1步第k-1步第k步第k步接下來的第k步，由公式(6.6)先算U的第k行，后算L的第k列。6.4 矩陣的三角分解法（續(xù)）2911121,11111222,122221,11,1,1,211,11,2121,112,112,1kkkkkkkjnkkjnkkkiii knnkkkjknkikijininknjkkkjknnnnkknaaabAauuuuuuyl

15、lllllllllluuuuuyuuuuyaabaabla1111 (,1, ;1,2, ) (3.6)()/ (1,2, ;1,2, )kkjkjkmmjmkikikimmkkkmual ujk kn knlal uuikkn kn3011121,11111222,122221,11,1,1,211,11,2121,112,112,1kkkkkkkjnkkjnkkkiii knnkkkjknkikijininknjkkkjknnnnkknaaabAauuuuuuyllllllllllluuuuuyuuuuyaabaabla手工計算時，可直接在矩陣上進(jìn)行，ukj(j=k, k+1,n+1)等于

16、akj減去已算出的L的第k行元素乘以已算出的U的第j列對應(yīng)的元素；11 (,1, ;1,2, )kkjkjkmmjmual ujk kn kn3111121,11111222,122221,11,1,1,211,11,2121,112,112,1kkkkkkkjnkkjnkkkiii knnkkkjknkikijininknjkkkjknnnnkknaaabAauuuuuuyllllllllllluuuuuyuuuuyaabaablalik(i=k+1, k+2,n)等于aik減去已算出的L的第i行元素乘以已算出的U的第k列對應(yīng)的元素，再除以ukk；11()/ (1,2, ;1,2, )kik

17、ikimmkkkmlal uuikkn kn326.4 矩陣的三角分解法（續(xù)）這樣，經(jīng)過n步，即可完成對矩陣的分解。11121,11111222,122221,11,1,1,211,11,2121,112,112,1kkkkkkkjnkkjnkkkkkiii kiknnn knknkjknkkkkjjknkininnnuuuuuuyuuuuuyuuuuyuuullllllllllllyullyuyAl最后一列，即為列向量y，這樣只需要解三角形方程組Ux=y，即可得原方程組的解。33分解A=LU，并解方程組Ax=b，其中71052-b ,139144301021312434321A解： 6.4

18、矩陣的三角分解法（續(xù)）1111 (,1, ;1,2, ) (6.6)()/ (1,2, ;1,2, )iijijikkjkjijijikkjjjkual uji in inlal uuijjn jn34 71391441030102513124324321A123-4-2u11=1u12=2u13=3u14=-411 52yu -324l21=-3/1=-3l31=2/1=2l41=4/1=411(1,2, )jjaujn1111 (2, )iialinu6.4 矩陣的三角分解法（續(xù)）35u22=-4-(-3)*2=2u23=-12-(-3)*3=-3u24=13-(-3)*(-4)=122

19、55(3 ) * (2 )1yu l32=(10-2*2)/2=3l42=(14-4*2)/2=3 71391441030102513124324321A123-4-2-32-31-124336.4 矩陣的三角分解法（續(xù)）36 71391441030102513124324321A123-4-2-32-31-12433u44=-13-4*(-4)-3*1-2*2=-43u34=-3-2*(-4)-3*1=22335102 * ( 2)3 * ( 1)17yu17l43=(9-4*3-3*(-3)/3=22u33=0-2*3-3*(-3)=3-444574 * ( 2)3 * ( 1)2 *17

20、16yu -166.4 矩陣的三角分解法（續(xù)）371234132131L1234232324U161712y回代（解方程組Ux=y），得Tx)4,3 ,2, 1(6.4 矩陣的三角分解法（續(xù)）386.4.1 列主元三角分解法與列主元Gauss消去法相對應(yīng)的是列主元三角分解法。11121,11111222,122221,11,1,1,211,11,2121,112,112,1kkkkkkkjnkkjnkkkiii knnkkkjknkikijininknjkkkjknnnnkknaaabAauuuuuuyllllllllllluuuuuyuuuuyaabaabla對方程組的增廣矩陣 經(jīng)過k-1步

21、分解后，可變成如下形式 , AA b396.4.1 列主元三角分解法（續(xù)）第k步分解，使用公式（6.6)，為了避免用絕對值很小的數(shù)ukk作除數(shù)，引進(jìn)量11(,1,)kiikimmkmsaluik kn1111 (,1, ;1,2, ) (6.6)()/ (1,2, ;1,2, )kkjkjkmmjmkikikimmkkkmual ujk kn knlal uuikkn kn406.4.1 列主元三角分解法（續(xù)）11121,11111222,122221,11,1,1,211,11,2121,112,112,1kkkkkkkjnkkjnkkkiii knnkkkjknkikijininknjkk

22、kjknnnnkknaaabAauuuuuuyllllllllllluuuuuyuuuuyaabaabla于是有kkkus11(,1,)kiikimmkmsaluik kn416.4.1 列主元三角分解法（續(xù)）若maxtik i nss 則將矩陣的第t行與第k行元素互換，將（i,j)位置的新元素仍記為lij或aij，然后在做第k步分解。這時 ()/ 1,2, )1 (1,2, ),kkkktikikikussslssikknlikkn即交換前的，（且11(,1,)kiikimmkmsaluik kn426.4.1 列主元三角分解法（續(xù)）例6.5 用列主元三角分解法解方程組12312312322

23、3347712457xxxxxxxxx 解 對增廣矩陣進(jìn)行變換，有123223324771424572sAss 21477122332457rr13122211212513222332745747 ()4771ss 第 步436.4.1 列主元三角分解法（續(xù)）13122211212513222332745747 ()4771ss 第 步32215171322211221112254771445727713333rr第 步15171322212116652554771第3步446.4.1 列主元三角分解法（續(xù)）等價的三角形方程組為12315171323222663554771xxxxxx 回代求

24、解，得3211,2,2xxx 6.5 解三對角線方程組的追趕法Gauss消去消去法法LU分解法分解法求解一般線性方程組的方法，求解一般線性方程組的方法，不考慮線性方程組本身的特點(diǎn)。不考慮線性方程組本身的特點(diǎn)。 但實(shí)用中會遇到一些特殊類型的線性方程組，如稀疏線性方程組，對稱線性方程組等。 對于這些方程組，若還用原有的一般方法來求解，勢必造成存儲和計算的浪費(fèi)。 有必要構(gòu)造適合解特殊方程組的解法：如追趕法和平方根法。6.5 追趕法追趕法適于求解三對角線方程組Ax=f，即 111122222111iiinnnnnnnbcxfabcxfabcabcabxf 其中A是三對角的對角占優(yōu)陣，即對給定的i,當(dāng)|

25、i-j|1時aij=0,且 0b (3) 120( )2( 0 ) 1 (n11niiiiianicacabcb；，；用追趕法求解,追趕法具有計算量少,方法簡單,算法穩(wěn)定等特點(diǎn)。A為非奇異陣6.5追趕法(續(xù)）可將A分解為： A=LU具體為可以利用矩陣的直接三角分解法來推導(dǎo)解三對角線性方程組的計算公式。 0b (3) 120( )2( 0 ) 1 (n11niiiiianicacabcb；，；A為非奇異陣定理定理4 A為非奇異矩陣為非奇異矩陣定理定理5 A的所有順序主子式都不為零的所有順序主子式都不為零1112222iiiinnnbcfabcfAabcfab f 6.5 追趕法(續(xù)）111222

26、233111111111111kikkkikknnnnnqrypqrypqrypqrypqrypqy 由矩陣乘法及矩陣相等的定義，有由矩陣乘法及矩陣相等的定義，有11111122 1,bq cr fy ap q解之得解之得111111221,/qb rcyfpaq6.5 追趕法(續(xù)）1112222kkkknnnbcfabcfAabcfab f 111222231111111111111kkkkkkkkknnnnnqrypqrypqrypqrypqrypqy 一般地，由一般地，由111, , kkkkk kkkkkkkkap qbp rqcrfp yy6.5 追趕法(續(xù)）111, ,kkkkk

27、kkkkkkkkap qbp rqcrfp yy可得可得111, (2,3, )kkkkkkkkkkkkkaprc qbp cqyfp ykn最后，分解完畢，只需求解Uxyx6.5 追趕法(續(xù)）解三對角線方程組的追趕法（1）計算pi, qi, yi的遞推公式1111,qb yf111,; (2,3, )kkkkkkkkkkkapqqbp cyfp ykn（2）U xyx1/,()/(1,2,1)nnnkkkkkxyqxyc xqknn追追趕趕6.6 解對稱正定矩陣方程組的平方根法平方根法適于求解系數(shù)矩陣A對稱正定的方程組Ax=b。若A為對稱正定矩陣，則 A滿足下述條件：（1） A對稱：即對稱：

28、即AT=A（2）對任意非零向量）對任意非零向量xRn，則有，則有xTAx0。且對稱正定矩陣且對稱正定矩陣A具有性質(zhì)：具有性質(zhì)：a.設(shè)設(shè)A為對稱正定陣，則為對稱正定陣，則A的各階順序主子式都大于零，的各階順序主子式都大于零，即即det(Ak)0，（，（k=1,2,n）。）。b. A的特征值的特征值i0（i=1,2,n）設(shè)A為對稱正定矩陣，則A有三角分解6.6 平方根法(續(xù)）1112121222012111nnnnnnuuuluuALULDUllu其中1122nnuuDu12111112022111nnuuuuuUuTAA6.6 平方根法(續(xù)）設(shè)0ALDU0()TTAUDL單位下三角陣上三角陣矩陣

29、三角分解的唯一性ALU0TLU對稱正定矩陣對稱正定矩陣A有唯一的分解式有唯一的分解式TALDL1112121222121122111det(). (1,2, )nnnnnnkkkuuuluuAlluAu uuknA是對稱正定矩陣，是對稱正定矩陣，各階順序主子式都大于零，各階順序主子式都大于零，即即det(Ak)0，（，（k =1,2, ,n），），112211221/21/2,*,nnnnDdiaguuudiaguuu DD12121212 ()()T/T/TTL LAL D LL DDLL DL D則有記12/LL DA可分解為下三角矩陣及其轉(zhuǎn)置矩陣的乘積6.6 平方根法(續(xù)）1122det

30、(). (1,2,., )kkkAu uukn于是，對角陣D還可分解故uii0，i=1,2, ,n）。計算計算A=LLTA=LLT的遞推公式，及求解公式的遞推公式，及求解公式 設(shè)有Ax=b，其中ARnn為對稱正定陣，于是有三角分解 TnnnnnnnnllllllllllllLLA2221211121222111其 中 l i i 0 ，（i=1,2,n）。), 2( ,/ ,11111111nilalaliiL第1列元素 同 理 ， 可 確 定 L 的 第 j 列 元 素 l i j（i=j,n）。1111()jnnTijikkjikjkikjkij jjkkkalLl ll ll l由矩陣乘

31、法，則有 （當(dāng)jk時，則ljk=0） 6.6 平方根法(續(xù)）這種分解是唯一的。由此求得解對稱正定矩陣方程組的平方根法計算公式（一）A=LLT分解計算11111111, /, (2, )iilalalin （2）對于j=2,3,n （1）121/2111()()/, (1, ) jjjjjjkkjijijik jkjjklallal llijn6.6 平方根法(續(xù)）1111()jnnTijikkjikjkikjkij jjkkkalLl ll ll l（二）求解計算 求解Ly=b 111111/()/ ,(2,3, )iiiikkiikyb lybl ylin求解LTx=y ) 1 , 2 ,

32、1( ,/ )(/1nilxlyxlyxiinikkkiiinnnn6.6 平方根法(續(xù)）例例 用平方根法解方程組用平方根法解方程組 81515316114012505213121815 531614 25 5213 243214314214321xxxxxxxxxxxxxx,111111al21 / 2/112121lal11 / 1/113131lal31 / 3/114141lal12*25)(2/ 121212222llal21 / ) 2*10 (/ )(2221313232lllal11 / ) 2*) 3(5(/ )(2221414242lllal6.6 平方根法(續(xù)）11111

33、111, / iilalal121 / 2111()() /jjjjjjkkjijijikjkjjklallalll81515316114012505213121A1321 121L3)2(*)2(1*114)(2/ 1323231313333llllal23/)2(*11*)3(1 (/)(33324231414343lllllal12*21*1)3(*)3(15)(2/14343424241414444llllllal3216.6 平方根法(續(xù)）121 / 2111()() /jjjjjjkkjijijikjkjjklallalll求解Ly=b 111111/()/ ,(2,3, )iiiikkiikyb lybl ylin1213321 121L81621b11/1/1111lby01/ ) 1*22(/ )(2212122lylby53/ ) 0*) 2(1*116(/ )(3323213133lylylby11/ ) 5*20*11*) 3(8 (/ )(4434324214144lylylylby6.6 平方根法(續(xù)）求解LTx=y ) 1 , 2 , 1( ,/ )