直接三角分解法ppt课件

1、第四章方程组的直接解法4.2 直接三角分解法直接三角分解法 4.2.3 平方根法平方根法4.2.1 一般矩阵的直接三角分解法一般矩阵的直接三角分解法4.2.2 三对角方程组的追赶法三对角方程组的追赶法第四章方程组的直接解法4.2 直接三角分解法直接三角分解法4.2.1 一般矩阵的直接三角分解法一般矩阵的直接三角分解法本节讨论矩阵本节讨论矩阵A的三角分解法的直接计算以及直接利用的三角分解法的直接计算以及直接利用A的三角分的三角分解式来求解方程组。解式来求解方程组。1.不选主元的三角分解法不选主元的三角分解法),(),(),(ijijijuUlLaA 设设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列已经算出，则由列已经算出，则由, 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对应的位置上对应的位置上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。设。设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消去法相当。如果有一系列方消去法相当。如果有一系列方程组，其系数距阵都是相同的，右端向量程组，其系数距阵都是相同的，右端向量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.列选主元的三角分解法列选主元的三角分解法 设从设从A=A （1开始已完成开始已完成k-1步分解计算，步分解计算，U的元素按行的元素按行和和L的元素按列存放在的元素按列存放在A的位置，得到的位置，得到 )()(1,21)()(1,11,1322222111211knnknkknnnkknkkkkknkkknnaalllaaluuluuluuuA该矩阵与顺序该矩阵与顺序Gauss消去法中得到的消去法中得到的Ak是不同的，这种存储是不同的，这种存储方式的形式称为紧凑

7、形式。方式的形式称为紧凑形式。第四章方程组的直接解法当当i=k时，时， si对应于对应于4.2.3中的中的ukk，它可能不宜在，它可能不宜在4.2.4作除作除法。当法。当i=k+1,k=2,.n， si对应于对应于4.2.4中的分子。记中的分子。记 ,maxinikikss nkkiulasrkkrirkiki, 1,11)( 现做第现做第k行计算，令行计算，令),()()(kkbA交换的第交换的第i行与第行的位置，但每个位置上仍用原记号。行与第行的位置，但每个位置上仍用原记号。然后仍按然后仍按4.2.3计算，算出计算，算出U的第的第k行。行。的计算可用的计算可用 这就算出了这就算出了L的第的

8、第k行。行。nkkjukj,2,1, iklkinkkissiki,.,2, 1, 以上分解过程经过以上分解过程经过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 设设A=（aij），），由式由式4.2.13可得可得njjillllajjijjkjkikij,2,1,11 第四章方程组的直接解法 这样，可以从这样，可以从j=1直到直到j=n逐列算出逐列算出L的元素的元素,再求解下三角方程组再求解下三角方程组Ly=b和和上三角方程组上三角方程组 L T x=y 。计算公式为。计算公式为1 , 2, 1,/ )(,/, 3 , 2,/ )(,/1111111 nnilllyxlyxnilllbylbyiinkkkiiinnnniijkkikii按逐列计算按逐列计算L的元素的计算步骤的元

11、素的计算步骤,设第设第1列至第列至第j-1列已经计算得到列已经计算得到,则有则有njjilllallaljjjkjkikijijjkjkjjjj,2,1,/,1121112 （4.2.15）（4.2.14）第四章方程组的直接解法 解解 不难验证系数矩阵是对称正定的，按不难验证系数矩阵是对称正定的，按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消消去法的变形去法的变形.但由于利用了矩阵正定的性质但由于利用了矩阵正定的性质,减少了计算量。平减少了计算量。平方根法的乘除法运算次数为方根法的乘除法运算次数为(n3+9n2+2)/6,加减法次数为加减法次数为(n3+6n2-7n)/6 。另外还有。另外还有n次开方运算，其所含乘除法和加次开方运算，其所含乘除法和加减法次数可分别看成减法次数可分别看成n的常数倍。平方根需的常数倍。平方根需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