直接三角分解法.ppt課件

1、第四章方程組的直接解法4.2 直接三角分解法直接三角分解法 4.2.3 平方根法平方根法4.2.1 一般矩陣的直接三角分解法一般矩陣的直接三角分解法4.2.2 三對角方程組的追趕法三對角方程組的追趕法第四章方程組的直接解法4.2 直接三角分解法直接三角分解法4.2.1 一般矩陣的直接三角分解法一般矩陣的直接三角分解法本節(jié)討論矩陣本節(jié)討論矩陣A的三角分解法的直接計算以及直接利用的三角分解法的直接計算以及直接利用A的三角分的三角分解式來求解方程組。解式來求解方程組。1.不選主元的三角分解法不選主元的三角分解法),(),(),(ijijijuUlLaA 設(shè)設(shè)A=LU，記，記 其中其中L為單位下三角陣

2、，為單位下三角陣，U為上三角陣。我們可直接給出為上三角陣。我們可直接給出L和和U的元素的計算公式。的元素的計算公式。由由A的第的第1行和第行和第1列可計算出列可計算出U的第的第1行和行和L的第的第1列，即列，即（4.2.1）（4.2.2）如果如果U的第的第1至至k-1列和列和L的第的第1至至k-1列已經(jīng)算出，則由列已經(jīng)算出，則由, 1,1nkkjulakrrjkrkj 111111,1,2, ,2,3, .jjkkuajnalknu第四章方程組的直接解法可得可得U的第的第k行元素行元素同理，由同理，由 ukj =akj - ,j =k,k+1, ,n。 （4.2.3） 11krrjkrul a

3、kj = ,i=k+1,k+2,n, krrkirul1可得可得L的第的第k列元素列元素交替使用交替使用4.2.3和和 （4.2.4），就能逐次計算出），就能逐次計算出U按行和按行和L按列的全部元素，而且可以把它們存放在矩陣按列的全部元素，而且可以把它們存放在矩陣A對應(yīng)的位置上對應(yīng)的位置上L的對角線元素不必存放）。這就完成了的對角線元素不必存放）。這就完成了A的的LU分解。分解。krrkirul1 lik=(aik - )/ ukk ,i =k+1,k+2, ,n。 由由4.2.1）- （4.2.4求得求得L和和U后，解方程組后，解方程組Ax=b接化接為求接化接為求解解LUx=b，若記，若記U

4、x=y，則有，則有Ly=b。于是可分兩部解方程組。于是可分兩部解方程組LUx=b，只要琢次向前代入的方法即可求得只要琢次向前代入的方法即可求得y。第二步求解。第二步求解Ux=y，只要琢次，只要琢次第四章方程組的直接解法用向后回代的方法即可求得用向后回代的方法即可求得x。設(shè)。設(shè)x=（x1 ，x2， xn) T, y=（y1, y2, yn) T,b= （b1 ，b2， bn) T, 則有計算公式則有計算公式 1111,.,2,1,yirririiniylbyb niriiririinnnnniuxuyxuy1n1,.,2, 1,/x（4.2.5）（4.2.6） 以上解方程組的計算與順序以上解方程

5、組的計算與順序Gauss消去法相當(dāng)。如果有一系列方消去法相當(dāng)。如果有一系列方程組，其系數(shù)距陣都是相同的，右端向量程組，其系數(shù)距陣都是相同的，右端向量b不同，則只須進行一次不同，則只須進行一次LU分解計算。上述解方程的方法稱為分解計算。上述解方程的方法稱為LU分解法，也稱分解法，也稱Doolittle方法。方法。 例例4.5 用用LU分解法求解分解法求解第四章方程組的直接解法 551631011411014211264321xxxx 解解 由由4.2.1）-（ 4.2.4 ）計算可得）計算可得 741911091037313231039101615161314126,1111u由由4.2.5計算

6、得計算得由由4.2.6計算得計算得 T y=(6,3,23/5,-191/74)Tx=(1,-1,1,-1) 第四章方程組的直接解法2.列選主元的三角分解法列選主元的三角分解法 設(shè)從設(shè)從A=A （1開始已完成開始已完成k-1步分解計算，步分解計算，U的元素按行的元素按行和和L的元素按列存放在的元素按列存放在A的位置，得到的位置，得到 )()(1,21)()(1,11,1322222111211knnknkknnnkknkkkkknkkknnaalllaaluuluuluuuA該矩陣與順序該矩陣與順序Gauss消去法中得到的消去法中得到的Ak是不同的，這種存儲是不同的，這種存儲方式的形式稱為緊湊

7、形式。方式的形式稱為緊湊形式。第四章方程組的直接解法當(dāng)當(dāng)i=k時，時， si對應(yīng)于對應(yīng)于4.2.3中的中的ukk，它可能不宜在，它可能不宜在4.2.4作除作除法。當(dāng)法。當(dāng)i=k+1,k=2,.n， si對應(yīng)于對應(yīng)于4.2.4中的分子。記中的分子。記 ,maxinikikss nkkiulasrkkrirkiki, 1,11)( 現(xiàn)做第現(xiàn)做第k行計算，令行計算，令),()()(kkbA交換的第交換的第i行與第行的位置，但每個位置上仍用原記號。行與第行的位置，但每個位置上仍用原記號。然后仍按然后仍按4.2.3計算，算出計算，算出U的第的第k行。行。的計算可用的計算可用 這就算出了這就算出了L的第的

8、第k行。行。nkkjukj,2,1, iklkinkkissiki,.,2, 1, 以上分解過程經(jīng)過以上分解過程經(jīng)過n-1步，可得步，可得PA=LU，因為，因為b也參加換行計算，也參加換行計算，所以在其位置上得到所以在其位置上得到Pb。最后再分兩步求解方程組。最后再分兩步求解方程組LUx=Pb，即求解，即求解Ly=Pb和和Ux=y。第四章方程組的直接解法例例4.6 用列選主元的三角分解法解用列選主元的三角分解法解 182014252513321321xxx 39/21639/7213/53/13/143/43/133/220513),()3()3(bA由此知由此知,18253/214323/1

9、20513),()2()2( bA由于由于s2=5/30 ,i=1，2，n 。 由此推出由此推出dvi 0， i=1，2，n 。記。記第四章方程組的直接解法 令令 ，則有，則有由分解式由分解式 的唯一性可得的唯一性可得4.2.3分解式的唯一性。定理分解式的唯一性。定理得證。得證。 稱稱4.2.13式為矩陣式為矩陣A的的Cholesky分解。利用分解。利用A的的Cholesky分解式來求解方程組分解式來求解方程組Ax=b的方法稱為的方法稱為Cholesky方法或方法或平方根法，這是因為計算過程含開方運算。平方根法，這是因為計算過程含開方運算。 211LLL TTTLLDLDLLDDLA )(21

10、1211121211TDLL11 nnnnllllllL21222111 設(shè)設(shè)A=（aij），），由式由式4.2.13可得可得njjillllajjijjkjkikij,2,1,11 第四章方程組的直接解法 這樣，可以從這樣，可以從j=1直到直到j(luò)=n逐列算出逐列算出L的元素的元素,再求解下三角方程組再求解下三角方程組Ly=b和和上三角方程組上三角方程組 L T x=y 。計算公式為。計算公式為1 , 2, 1,/ )(,/, 3 , 2,/ )(,/1111111 nnilllyxlyxnilllbylbyiinkkkiiinnnniijkkikii按逐列計算按逐列計算L的元素的計算步驟的元

11、素的計算步驟,設(shè)第設(shè)第1列至第列至第j-1列已經(jīng)計算得到列已經(jīng)計算得到,則有則有njjilllallaljjjkjkikijijjkjkjjjj,2,1,/,1121112 （4.2.15）（4.2.14）第四章方程組的直接解法 解解 不難驗證系數(shù)矩陣是對稱正定的，按不難驗證系數(shù)矩陣是對稱正定的，按4.2.14和和4.2.15依次計算得依次計算得 .25.15 .375.2,5 .075.225.4,64221321321xxxxxxxxx 例例4.8 用平方根法求解用平方根法求解 15.15.025.02L 由由4.2.14可得可得 由此推出由此推出 ，所以平方根法的中間量所以平方根法的中間

12、量 得以控制。不必選主元。得以控制。不必選主元。,12 jkjkjjlajkljkaljjjk,2,1, 平方根法的原理基于矩陣的平方根法的原理基于矩陣的LU分解分解,所以它也是所以它也是Gauss消消去法的變形去法的變形.但由于利用了矩陣正定的性質(zhì)但由于利用了矩陣正定的性質(zhì),減少了計算量。平減少了計算量。平方根法的乘除法運算次數(shù)為方根法的乘除法運算次數(shù)為(n3+9n2+2)/6,加減法次數(shù)為加減法次數(shù)為(n3+6n2-7n)/6 。另外還有。另外還有n次開方運算，其所含乘除法和加次開方運算，其所含乘除法和加減法次數(shù)可分別看成減法次數(shù)可分別看成n的常數(shù)倍。平方根需的常數(shù)倍。平方根需n3 /6次

13、乘除法，與次乘除法，與Gauss消去法相比減少了一半。消去法相比減少了一半。第四章方程組的直接解法 njjidlldaldladjjkjkikkijijjkkjkjjj, 2, 1,/ )(11112則可避免開方根運算，稱為改進的平方根法。則可避免開方根運算，稱為改進的平方根法。 它即適合于求接對稱正定方程它即適合于求接對稱正定方程組，也適合于組，也適合于A求解對稱且其順序主子式全不為零的方程組。分解式的計算求解對稱且其順序主子式全不為零的方程組。分解式的計算公式為公式為(j=1,2,n)解解Ly=（6，-0.5，1.25T ，得，得y=（3，0.5，-1） T ，再解，再解L T x=y可以得到可以得到x=（2，1，-1） T 。 ,1111112121222121 nnnnnllldddlllA 如果對矩陣采如果對矩陣采4