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

1、16.4 矩 陣 的 三 角 分 解 法26.4 矩陣的三角分解法 杜里特爾(Dolittle)分解法 消去法實際上是對線性方程組的增廣矩陣A,b做第三種初等行變換。 由于對A,b 施行第三種初等行變換相當于用對應的第三種初等矩陣左乘于A,b 。0)(kkkaGauss消去法的矩陣解釋消去法的矩陣解釋設約化主元素 （k=1, 2, n1）。1111iikkmM36.4 矩陣的三角分解法（續(xù)）1111ikikMmk列k行i行Mik是特殊的初等矩陣，稱為倍加矩陣，某矩陣Z左乘Mik相當于將矩陣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經過n-1步消元后，可以得到()121()121,nnnnnnLLL AAULLL bby因此，不選主元的高斯消去法消去過程,實質是增廣矩陣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行倍數加于第n行,將第一行的倍數加于第n行, ,第二行，可見L是單位下三角矩陣。1112131,1n nMMMIL, , , UUUA bLRLyLLyALLybUAxbLxb高斯消去法的消去過程，實質上是將A分解為兩個三角矩陣的乘積A=LU，并求解Ly=b的過程。回代過程就是求解上三角方程組Ux=y。 6.4

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

8、 nAR克勞特(Crout)分解：分解為一個下三角陣和一個上三角陣。17矩陣L和U也可以直接算出，而不需要任何中間步驟，這就是所謂的三角分解法。設A為非奇異的矩陣，且有分解式 A=LUL為單位下三角陣，U為上三角陣。111212122212111nnnnnnuuuluuAllu根據矩陣乘法，由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ù)）一般地，當ij時(上三角陣）112222121211111nnnnnnuuAuluulul有206.4 矩陣的三角分解法（續(xù)）當i j時，有1211,12,1,11( ,1,0,0)00jjjjjijiii ji ji iikkjijjjkjjuuuallllll ul uu112222121211111nnnnnnuuAuluulul216.4 矩陣的三角分解法（續(xù)）11iijikkjijkal uu一般地，當ij時，有當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，從前往后反復代入可求出下三角形方程組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 實際計算時L的對角元lii=1不必存放，L和U中肯

12、定為零的元素也不必存放，因此L和 =U,y 可共同存放在增廣矩陣 =A,b中的相應位置：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都是原矩陣 對應的元素，減去同行左邊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對方程組的增廣矩陣 經過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手工計算時，可直接在矩陣上進行，ukj(j=k, k+1,n+1)等于

16、akj減去已算出的L的第k行元素乘以已算出的U的第j列對應的元素；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列對應的元素，再除以ukk；11()/ (1,2, ;1,2, )kik

17、ikimmkkkmlal uuikkn kn326.4 矩陣的三角分解法（續(xù)）這樣，經過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消去法相對應的是列主元三角分解法。11121,11111222,122221,11,1,1,211,11,2121,112,112,1kkkkkkkjnkkjnkkkiii knnkkkjknkikijininknjkkkjknnnnkknaaabAauuuuuuyllllllllllluuuuuyuuuuyaabaabla對方程組的增廣矩陣 經過k-1步

21、分解后，可變成如下形式 , AA b396.4.1 列主元三角分解法（續(xù)）第k步分解，使用公式（6.6)，為了避免用絕對值很小的數ukk作除數，引進量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 解 對增廣矩陣進行變換，有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分解法分解法求解一般線性方程組的方法，求解一般線性方程組的方法，不考慮線性方程組本身的特點。不考慮線性方程組本身的特點。 但實用中會遇到一些特殊類型的線性方程組，如稀疏線性方程組，對稱線性方程組等。 對于這些方程組，若還用原有的一般方法來求解，勢必造成存儲和計算的浪費。 有必要構造適合解特殊方程組的解法：如追趕法和平方根法。6.5 追趕法追趕法適于求解三對角線方程組Ax=f，即 111122222111iiinnnnnnnbcxfabcxfabcabcabxf 其中A是三對角的對角占優(yōu)陣，即對給定的i,當|

25、i-j|1時aij=0,且 0b (3) 120( )2( 0 ) 1 (n11niiiiianicacabcb；，；用追趕法求解,追趕法具有計算量少,方法簡單,算法穩(wěn)定等特點。A為非奇異陣6.5追趕法(續(xù)）可將A分解為： A=LU具體為可以利用矩陣的直接三角分解法來推導解三對角線性方程組的計算公式。 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 解對稱正定矩陣方程組的平方根法平方根法適于求解系數矩陣A對稱正定的方程組Ax=b。若A為對稱正定矩陣，則 A滿足下述條件：（1） A對稱：即對稱：

28、即AT=A（2）對任意非零向量）對任意非零向量xRn，則有，則有xTAx0。且對稱正定矩陣且對稱正定矩陣A具有性質：具有性質：a.設設A為對稱正定陣，則為對稱正定陣，則A的各階順序主子式都大于零，的各階順序主子式都大于零，即即det(Ak)0，（，（k=1,2,n）。）。b. A的特征值的特征值i0（i=1,2,n）設A為對稱正定矩陣，則A有三角分解6.6 平方根法(續(xù)）1112121222012111nnnnnnuuuluuALULDUllu其中1122nnuuDu12111112022111nnuuuuuUuTAA6.6 平方根法(續(xù)）設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可分解為下三角矩陣及其轉置矩陣的乘積6.6 平方根法(續(xù)）1122det

30、(). (1,2,., )kkkAu uukn于是，對角陣D還可分解故uii0，i=1,2, ,n）。計算計算A=LLTA=LLT的遞推公式，及求解公式的遞推公式，及求解公式 設有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、法，則有 （當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( ,/ )