数值分析课件：5.3 直接三角分解方法.ppt

1、第四章方程组的直接解法5.3 直接三角分解法直接三角分解法5.3.3 平方根法平方根法5.3.1 一般矩阵的直接三角分解法一般矩阵的直接三角分解法5.3.2 三对角方程组的追赶法三对角方程组的追赶法第四章方程组的直接解法5.3 直接三角分解法直接三角分解法5.3.1 一般矩阵的直接三角分解法三角分解的紧凑形式一般矩阵的直接三角分解法三角分解的紧凑形式 将高斯消去法改写为将高斯消去法改写为紧凑形式紧凑形式，可以直接从矩阵，可以直接从矩阵A的的元素得到计算元素得到计算L、U元素的递推公式，而不需任何中间步元素的递推公式，而不需任何中间步骤，这就是所谓直接三角分解法骤，这就是所谓直接三角分解法. 一

2、旦实现了矩阵一旦实现了矩阵A的的LU分解，那么求解分解，那么求解Ax=b的问题的问题就等价于求解两个三角形方程组就等价于求解两个三角形方程组 (1)Ly=b，求，求y； (2)Ux=y，求，求x 第四章方程组的直接解法1.不选主元的三角分解法不选主元的三角分解法 设设A为非奇异矩阵，且有分解式为非奇异矩阵，且有分解式A= =LU，其中，其中L为单位为单位下三角阵，下三角阵，U为上三角阵，即为上三角阵，即1112112122212111nnnnnuuuluuAllu 111211112121 1121 122221 1221222121111 nnnnnnnnnnniinnniuuuaaal u

3、l uul uuaaaaaa nl ul uu 即第四章方程组的直接解法如果如果U的第的第1至至k-1列和列和L的第的第1至至k-1列已经算出，则由列已经算出，则由, 1,1nkkjulakrrjkrkj 可得可得U的第的第k行元素行元素同理，由同理，由ukj =akj ,j =k,k+1, ,n。 （5.3.3） 11krrjkrulakj = ,i=k+1,k+2,n, krrkirul1（5.3.1）（5.3.2）111111,1,2, ,2,3, .jjkkuajnalknu由由A的的第第1行行和和第第1列列可计算出可计算出U的第的第1行行和和L的第的第1列列，即，即第四章方程组的直接

4、解法可得可得L的第的第k列元素列元素交替使用（交替使用（5.3.3）和）和 （5.3.4），就能逐次计算出），就能逐次计算出U（按（按行）和行）和L（按列）的全部元素，而且可以把它们存放在矩阵（按列）的全部元素，而且可以把它们存放在矩阵A对应的位置上（对应的位置上（L的对角线元素不必存放）。这就完成了的对角线元素不必存放）。这就完成了A的的LU分解。分解。krrkirul1 lik=(aik )/ ukk ,i =k+1,k+2, ,n。 由（由（5.3.1）- （5.3.4）求得）求得L和和U后，解方程组后，解方程组Ax=b 化为求解化为求解LUx=b，若记，若记Ux=y，则有，则有Ly=b

5、。于是可分两部解。于是可分两部解方程组方程组LUx=b，只要逐次向前代入的方法即可求得，只要逐次向前代入的方法即可求得y。第。第二步求解二步求解Ux=y，只要逐次用向后回代的方法即可求得，只要逐次用向后回代的方法即可求得x。设设 x=（x1 ，x2， xn) T, y=（y1, y2, yn) T, b= (b1 ，b2， bn) T, 则有计算公式则有计算公式（5.3.4）第四章方程组的直接解法1111,1 , 2 , .,iiii rrrybyblyin1/,1,2,.,1nnnnniiiriirrixyuxyu xuinn （5.3.5）（5.3.6） 以上解方程组的计算与顺序以上解方程

6、组的计算与顺序Gauss消去法相当。如果消去法相当。如果有一系列方程组，其系数矩阵都是相同的，右端向量有一系列方程组，其系数矩阵都是相同的，右端向量b不不同，则只须进行一次同，则只须进行一次LU分解计算。上述解方程的方法称分解计算。上述解方程的方法称为为LU分解法分解法，也称，也称杜利特尔杜利特尔(Doolittle)方法。方法。 第四章方程组的直接解法 123121242156301650 xxx 解解 由由LU分解的紧凑格式（分解的紧凑格式（5.3.1）-（ 5.3.4 ）计算可得）计算可得13121,01121335LU例例5.5 用用LU分解法求解分解法求解第四章方程组的直接解法解下三

7、角方程组 Ly = b，即解(单位)上三角方程组 Ux= y，即Thus . Let , then .AxbLUxbUxyLyb1122133312424 2163 15 015045 yyyyyy 1322311 2 12493315 45457xxxxxx 第四章方程组的直接解法二二 CroutCrout分解（）分解（）111211112121222212221212001001 001nnnnnnnnnnnnaaaluaaaalluaaalll 设设A为非奇异矩阵，为非奇异矩阵，A A还有一种分解式还有一种分解式A= =LU，其中，其中L为下三角阵，为下三角阵，U为单位上三角阵，即为单位

8、上三角阵，即 先计算先计算L L的第一列，再计算的第一列，再计算U U的第一行的第一行，其余类此。，其余类此。得到以下公式，得到以下公式，1111111111, ,1,2,.,/ ,2,3,., , 2,3,., ,1,2,., /,2,3,.,1, ,1,., jijjjijijirrjriijijirrjiirlai jnualjnlal uin jnual ulinji in第四章方程组的直接解法 实现实现 A= =LU，则，则 Ax= =b 可以化为可以化为 LUx= =b。令令 Ux= =y，则，则 Ly=b。 由由 Ly=b解出解出 yi: : 再由再由 Ux= =y 解出解出 x

9、i: : 11 /, 1,2, iiiijjiijybl ylin1 , , 1,2,1nnniiijjj ixyxyu xin 第四章方程组的直接解法例例5.55.5用用CroutCrout分解求解方程组：分解求解方程组：解解 设设 A=LU，即，即1231212421563 .01 650 xxx 111121213131131212131111222221123232311223232113223333311332231,2,02,1,3,1()/1,5lalalaaauulllal ulal uual ullal ul u 10 0 2 3 0 ,01 51 2 1 0 11 .0 0

10、 1LU 第四章方程组的直接解法解下三角方程组 Ly = b，即解(单位)上三角方程组 Ux= y，即Thus . Let , then .AxbLUxbUxyLyb11223310 02424 2 3 063 5 01 5509 yyyyyy 1322311 2 12490 115 40 0 197xxxxxx 第四章方程组的直接解法在数值求解常微分方程边值问题、热传导方程和建立三次样条函数时，在数值求解常微分方程边值问题、热传导方程和建立三次样条函数时，都会要解三对角方程组：都会要解三对角方程组：AX=b5.3.2 三对角方程组的追赶法三对角方程组的追赶法并且满足并且满足111122222

11、111, , .nnnnnnnbcxdabcxdAXbabcxdab);1, 2 , 1( 0, ), 3 , 2( 0 (i)nicniaii. | , ) 1, 3 , 2( | |,| (ii)11nniiiabnicabcb条件条件(i)保证方程组不能降阶，条件保证方程组不能降阶，条件(ii)保证三角分解可做到底。保证三角分解可做到底。第四章方程组的直接解法(5.3.7)11222111nnnnnbcabcAabcab下面讨论三角分解下面讨论三角分解(1)如果如果A满足满足Gauss消去法的条件消去法的条件,可用可用LU (Doolittle)分分解法求解解法求解. 并且并且, L和和

12、U有如下形式有如下形式(5.3.8)111122222211111111nnnnnnnnbcucabcluccabcluab 按乘法展开按乘法展开 112212212221211,/,./,2,1,1, 2,1iiiiiiiublaulauubl clauinubl cin(5.3.9)第四章方程组的直接解法1223nnulullu计算次序为计算次序为 111 , ,2,3,.iiiiydydl yin而解原方程组而解原方程组Ax=bAx=b可分为两步可分为两步Ly=dLy=d和和UxUx=y=y, ,计算公式为计算公式为123nyyyy即依次求出也称为追的过程称这一过程为称这一过程为“追追”

13、的过程的过程. . (5.3.10)(5.3.11)1/()/,1,2,.1nnniiiiixyuxyc xu inn11nnxxx即依次求出称为赶的过程.第四章方程组的直接解法称为称为(5.3.9)、(5.3.10)和和(5.3.11)为求解三对角形方程组的追赶为求解三对角形方程组的追赶法法,又称为又称为Thomas算法算法。追赶法求解。追赶法求解 Ax=f 仅需仅需5n-4次乘除运次乘除运算。工作量较小。算。工作量较小。追赶法能实现的条件是追赶法能实现的条件是ui0，i=1,2,n.下面给出追赶法下面给出追赶法的一个充分条件。的一个充分条件。niucii,2,1,10 niabuabiii

14、ii,.2 , 1, 定理定理5.6 设三对角矩阵设三对角矩阵A有有(5.3.7)的表达式的表达式,且满足且满足则则A非奇异非奇异,且有且有110,0,0,2,3,.1nniiiiibcbabaca cin第四章方程组的直接解法(2)*如果如果A满足满足Gauss消去法的条件消去法的条件,也可用也可用LU (Crout)分解法求解分解法求解. 并且并且, L和和U有如下形式有如下形式(5.3.8*)11112122111122211nnnnnnnnuuulalalbacbacbacb按乘法展开按乘法展开 1,2, 111111niluabulclbiiiiiii1, 2 , 1/11111ni

15、uabllcubliiiiiii则可计算则可计算 11221nnluluul计算次序为计算次序为 第四章方程组的直接解法 (5.3.9*)111(),2,3,.iiiiiydyda ylin(5.3.10*)而解原方程组而解原方程组Ax=b可分为两步可分为两步Ly=d和和Ux=y,计算公式为计算公式为123nyyyy即依次求出也称为追的过程称这一过程为称这一过程为“追追”的过程的过程. 1, 2 , 1/11111niuabllcubliiiiiiinnluulul12211由此可依次求得由此可依次求得L和和U的所有元素的所有元素.第四章方程组的直接解法(5.3.11*)1,1,2,.1nni

16、iiixyxyu xinn11nnxxx即依次求出称为赶的过程.第四章方程组的直接解法220006112007, .011209001121100011 1Ab b例例 用追赶法求解三对角线性方程组用追赶法求解三对角线性方程组AX=b，其中，其中1223122312120120012000112,2111()22,.,22nnuluAlluulul 作作Doolitle分解分解解解第四章方程组的直接解法61102, .143184105yx 1122122212201220012100012A 第四章方程组的直接解法2111211,01211001211000121A .54321 ,5975

17、3xy作作Crout分解分解解解第四章方程组的直接解法练习练习 用追赶法求解三对角方程组用追赶法求解三对角方程组- Crout- Crout 分解分解 501352242231124321xxxx解解 21211111lcubl54252221222lcuuabl333323312556clba uul 4443103lba u第四章方程组的直接解法211252114213215122422551256102131221121231.5,12dda yyyll33244334345,16da yda yyyll 0, 1433344xuyxyx2, 121113222xuyxxuyx由由Ly=

18、f 解出解出y又由又由Ux=y解出解出x 第四章方程组的直接解法5.3.3 平方根法平方根法 工程实际计算中工程实际计算中,线性方程组的系数矩阵常常线性方程组的系数矩阵常常具有对称正定性具有对称正定性.TAAAAAALUUU利用对称正定距阵的三角分解而得到的求解对称正定方程组的一种有效方法根。设 为对称阵，即，且 的所有顺序主子式均非零，则知 可以唯一分解为：为利用 的非奇异性，将 再分解为：平方法第四章方程组的直接解法11211111,1,111220111nnnnnuuuuuunnuuUDUu00005.3.125.3.12为对角阵，为单位上三角阵，则:（）又（），由分解的唯一性即得：代入

19、上面（）中得：TTTTTDUALULDUAAUDLULALDL第四章方程组的直接解法 , ,.对称矩阵的三角分解设 为 阶对称矩阵 且的顺序主子式均不为零，则 可以唯一分解为其中 为单位下三角阵， 为对角阵TAnAAALDLLD定定理理5.7()5.7()(5.3.12)(5.3.12)总结上述讨论有总结上述讨论有112110(,),0,0 (2,3, ),iiTinDDiAADALDLDdiag d dddDdin当 为对称正定矩阵时，则 的所有顺序主子式，而。设则：于是:2.若若A为对称正定矩阵为对称正定矩阵, det(Ak)0,(k=1,2,n), 第四章方程组的直接解法2121111D

20、DddddddDnnnTTTTLLLDLDLDLDLDLA11)(21212121 ,.对称正定矩阵的三角分解或分解设 为阶对称正定矩阵 则存在实的非奇异下三角矩阵 使得当限定 对角元素为正时，这种分解是唯一的TCholeskyAnLALLL定定理理5.8()5.8()（5.3.13）12nddDd记记 于是对角阵于是对角阵D还可分解还可分解第四章方程组的直接解法称（称（5.3.135.3.13）式为矩阵）式为矩阵A A的的乔累斯基乔累斯基(Cholesky(Cholesky) )分解分解。利用利用A A的的CholeskyCholesky分解式来求解方程组分解式来求解方程组Ax=bAx=b的

21、方法称的方法称为为CholeskyCholesky方法或平方根法，这是因为计算过程含开方法或平方根法，这是因为计算过程含开方运算。方运算。 下面我们用直接分解方法来确定计算下面我们用直接分解方法来确定计算L L元素的递推公元素的递推公式。因为式。因为 1111211212222212nnnnnnnnllllllllAllll 其中其中lii00(i=1,2,n)由矩阵乘法及由矩阵乘法及ljk=0(=0(当当jk),),得得第四章方程组的直接解法1111221211122222122313111323231 212233333132 () lalallallallal lllall1111211

22、21222221221111 211112221 11212221122221 111 212 221()nnnnnnnnnnnijn nnnnnniillllllllAllllll ll ll llll ll lal ll ll ll 第四章方程组的直接解法于是得到解对称正定方程组于是得到解对称正定方程组Ax=bAx=b的平方根法计算公式：的平方根法计算公式：njjilllallaljjjkjkikijijjkjkjjjj,2,1,/,1121112 （5.3.15）（5.3.14）对于对于 j=1,2,n, 按逐列计算按逐列计算L的元素的计算步骤的元素的计算步骤,设设第第1列至第列至第j-

23、1列已经计算得到列已经计算得到,则有则有njjillllajjijjkjkikij,2, 1,11 第四章方程组的直接解法 221.1max,maxmax.jkjjjjjkjjj nj kj njkjjlaalaMll 则从而这表明分解过程中元素的数量级不会增长太快且对角元素 恒为正数。于是不选主元素的平方根法是一个数值稳定的方法。21(5.3.14)(1,2, )由知jjjjkkaljn第四章方程组的直接解法 平方根法的原理基于矩阵的平方根法的原理基于矩阵的LU分解分解,所以它也所以它也是是Gauss消去法的消去法的变形变形.但由于利用了矩阵正定的性质但由于利用了矩阵正定的性质,减少了计算量

24、。平方根法的乘除减少了计算量。平方根法的乘除法运算次数为法运算次数为(n3+9n2+2)/6,加减法次数为加减法次数为(n3+6n2-7n)/6 。另外还有。另外还有n次次开方运算，其所含乘除法和加减法次数可分别看成开方运算，其所含乘除法和加减法次数可分别看成n的常数倍。平方的常数倍。平方根需根需n3 /6次乘除法，与次乘除法，与Gauss消去法相比减少了一半消去法相比减少了一半。3. 求解求解Ax=b，即求解两个三角形方程组，即求解两个三角形方程组 (1)Ly=b，求，求y； （2）LTx=y，求，求x111111 / () (2,3,., )iiiikkiikyblybl ylin1/ (

25、) (1,.,1) nnnnniikikiik ixylxbl xlin 第四章方程组的直接解法 解解 不难验证系数矩阵是对称正定的，按（不难验证系数矩阵是对称正定的，按（5.3.14）和）和（5.3.15）依次计算得）依次计算得 .25.15 .375.2,5 .075.225.4,64221321321xxxxxxxxx 例例5.6 用平方根法求解用平方根法求解11112121112222221313111323231 212222223333313242,1 20.54.250.2521 20.5,()2.75( 0.5)0.5/21.53.50.51.51lalallallallal

26、lllall 15.15.025.02L解解Ly=(6, -0.5, 1.25)T ,得得y=(3, 0.5, -1) T ，再解，再解LTx=y可以得到可以得到x=(2,1,-1)T 。 第四章方程组的直接解法(5.3.14)由公式可见，用平方根法解对称正定方程组时，计算 的元素 需要进行开方计算，为避免开方计算，可对平方根法进行改进。iiLl11221,(1)jjjjjjkklalj（5.3.14）第四章方程组的直接解法 njjidlldaldladjjkjkikkijijjkkjkjjj, 2, 1,/ )(11112则可避免开方根运算，称为则可避免开方根运算，称为改进的平方根法改进的平

27、方根法。 它既适合于求接对称正定方程它既适合于求接对称正定方程组，也适合于求解组，也适合于求解A对称且其顺序主子式全不为零对称且其顺序主子式全不为零的方程组。分解式的计算的方程组。分解式的计算公式为公式为(j=1,2,n)22112122121111,11nnnnndllldlAlld 如果对矩阵采用定理如果对矩阵采用定理4.7的（的（5.3.12）分解式，）分解式， 即即其中其中j=1时，求和部分为零。这样求解方程组时，求和部分为零。这样求解方程组Ax=b化为求解化为求解Ly=b和和LTx=D-1y.4.改进的平方根法改进的平方根法第四章方程组的直接解法解解Ly=b得得y=(6,1,-1)T

28、。解。解LTx=D-1y得得x=(2,1,-1)T。140.251,4,0.250.7511LD 对于例对于例5.6给定的方程组，用改进的平方根法有给定的方程组，用改进的平方根法有 .25.15 .375.2,5 .075.225.4,64221321321xxxxxxxxx 例例5.6 用改进的平方根法求解用改进的平方根法求解解解11121211313112222221132321 31 21222223333113224,1 40.25,1 40.25,4.25( 0.25)44()2.754 0.25 ( 0.25)/40.753.50.2540.7541daladladdal dlad

29、 l lddal dl d 不难验证系数矩阵是对称正定的不难验证系数矩阵是对称正定的第四章方程组的直接解法 练习练习 用改进的平方根法求解方程组用改进的平方根法求解方程组 131101110400141030003520002321002254321xxxxx 分析：分析：对称很显然，需验证正定，可通过验证各顺序主子式大对称很显然，需验证正定，可通过验证各顺序主子式大于零。于零。解解 分解分解TLA 2/1111212212/11300120111即即,TLDLA ，得得求求解解byL ，Ty)2/1 , 1, 4, 2, 1( 到方程组的解：到方程组的解：。Tx)1 ,1 ,1 ,1 ,1( 得得，求求解解yDxLT1 1311011122121130012011154321yyyyy 114221121231102121001154321xxxxx