直接三角分解法课件.pptx

1、矩阵的三角分解n一、LU分解(Doolittle分解)1. LU分解分解用用n=3来举例说明。三元方程组来举例说明。三元方程组Ax=b的增广矩阵为的增广矩阵为 A b 111213121222323132333aaabaaabaaab ,用初等行变换变换为用初等行变换变换为 1112131111222321113233300aaabaabaab 11Ab 这相当于将这相当于将A矩阵左乘初等行变换矩阵矩阵左乘初等行变换矩阵 12110010001Ml 和和23110001001Ml 使使M2M1A b=A(1) b(1),其中其中l21=a21/a11, l31=a31/a11再将再将 11Ab

2、 进行初等行变换进行初等行变换,得到得到 11121311112223222333000aaabaabab 22Ab 11121311112223222333000aaabaabab 22Ab 这相当于左乘初等行变换矩阵这相当于左乘初等行变换矩阵 33210001001Ml ,其中其中 11323222laa ,则则 2321M M M AA 。记。记 2UA ,则则U是一个上三角矩阵是一个上三角矩阵,有有 321M M M AU 。则。则111123AMMM U 。其中。其中112110010001Ml ,122110010001Ml ,132110010001Ml 。 记记11112321

3、3132100101LMMMlllL是下三角矩阵。这就是矩阵是下三角矩阵。这就是矩阵A的的LU分解分解:A=LU。 3.LU分解的充要条件分解的充要条件定理定理1:A能分解为能分解为的充分必要条件是的充分必要条件是A的各的各阶顺序主子式均不为零。即阶顺序主子式均不为零。即LU 111det0Aa , 111222122det0,aaAaa , det0A 。 4、LU分解的紧凑格式分解的紧凑格式我们不必在高斯消去法过程中产生我们不必在高斯消去法过程中产生L和和U,而而是直接用矩阵是直接用矩阵A来进行来进行LU分解。分解。下面导出计算公式下面导出计算公式因因A=LU则则 4、LU分解的紧凑格式分

4、解的紧凑格式我们不必在高斯消去法过程中产生我们不必在高斯消去法过程中产生L和和U,而而是直接用矩阵是直接用矩阵A来进行来进行LU分解。分解。下面导出计算公式下面导出计算公式因因A=LU则则 111213121222323132333123nnnnnnnnaaaaaaaaaaaaaaaa 2131321231000100101nnnllllll 111213122232333000000nnnnnuuuuuuuuuu 利用矩阵乘法利用矩阵乘法,得得111111,2,.,2,3,., .2,3,., .jjiijikkjijkjijikkjkaujnal uuinijal uinij综合以上分析,

5、有njuajj,2 , 111rkkjrkrjula1n2r,nrj,rkkrikirula11n2r,nri, 1 1111ulaiini,3 ,2因此可以推导出ju1ja1nj,2 , 1U的第一行1111ualiini,3 ,2L的第一列rjrkkjrkrjuula111rrirrkkrikirulula11-(1)-(2)11rkkjrkrjrjulaun2r,nrj,U的第r行rrrkkrikiriruulal111n2r,nri, 1 L的第r列-(3)-(4)称上述(1) (4)式所表示的分解过程为Doolittle分解分解由此可以得到由此可以得到 ijlij 和和 ijuij

6、的计算公式的计算公式: 111,2,jjuajn 。在。在U的第的第1,2, j行和行和L的第的第1,2,1j 列计算出来后再列计算出来后再先计算先计算U的第一行的第一行计算计算L的第的第j列列:11jijijikkjjjklal uu 在在U的第的第1, 2,1i 行和行和L的的1, 2,1i 再计算再计算U的第的第i行行: 11,iijijikkjkualujin 计算的过程是计算的过程是:U第第1行行,L第第1列列,U第第2行行,L第第2列列,顺序计算。顺序计算。 第第列均计算出来后列均计算出来后 11112,3,1,1,对于做对于做对于做rrjrjrkkjkriririkkrrrkrn

7、jr rnual uirnlal uu 1.计算流程计算流程 1111111,2,jjjjjnualau 对于做2.存储问题和全部流程U可以存储在可以存储在A的上三角部分的上三角部分,L可以存储在可以存储在A的的下三角部分下三角部分,对角元存对角元存U的对角元的对角元,A的对角元为的对角元为1而不必存储而不必存储,如下图如下图: 1111121213131121 21222223232231 313232333333112233nnnnnnnnnnnnn nn na ua ua ua ua la ua ua ua la la ua ua la la la u用LU分解来解线性方程组的全部流程如

8、下:11112,:iiinaaa 对于做2,3,rn 对于做11,:rrjrjrkkjkjrnaaa a 对于做111,:riririkkrrrkirnaaa aa 对于做11yb 112,3,iiiijjjinyba y 对于做nnnnxya 11, 2,1niiijjiijiinxya xa 对于做例1:利用LU分解求解线性方程组123412341234123423475873214511216255318xxxxxxxxxxxxxxxx 解解:第一步第一步,A的的LU分解分解23415873451122553 10 0 02.5 1 0 02 2 1 024 1 1 2 34 10 0.

9、5 3 0.50 03 30 003 第二步第二步,求解求解Lyb 10 0 02.5 1 0 02 2 1 024 1 1 1234yyyy 7211618 解得解得: 17y ,23.5y , 39y ,46y 。第二步第二步,求解求解Uxy 2 34 10 0.5 3 0.50 03 30 003 1234xxxx 73.596 解得解得:12x , 23x ,31x , 42x 。矩阵的三种形式的分解:Doolittle分解: A = LU (单位下三角与上三角) Crout分解: (下三角与单位上三角)LDU分解: A = LDU (单位下三角, 对角及单位上三角)ULA.)4()

10、1 (,式的表达式请找出类似于解分则称之为表示为单位上三角阵角阵表示为下三中的为上三角阵，如果将为单位下三角阵中分解的CroutULLUAULLUADoolittleA二、追赶法1. 三对角矩阵三对角矩阵:在实际问题中在实际问题中,经常会遇到如下经常会遇到如下形式的方程组形式的方程组, 1112121222321211111nnnnnnnnnnnnb xc xda xb xc xdaxbxcxda xb xd 其系数矩阵为其系数矩阵为A 11222333111nnnnnbcabcabcabcab 没有写的部分均为零没有写的部分均为零(下同下同),对角元为对角元为 后次后次12,nb bb对角线

11、上的元素为对角线上的元素为121,nc cc ,前次对角线上的元素为前次对角线上的元素为23,naaa。 我们称矩阵我们称矩阵A为三对角矩阵为三对角矩阵,相应的方程组称三相应的方程组称三对角方程组。如果对对角方程组。如果对A进行进行LU分解分解,则将有如下形式则将有如下形式:23111111nnllLll 11223311nnnu cucu cUucu 并称它们为二对角矩阵。并称它们为二对角矩阵。定理3:设上述三对角矩阵A满足iiibac 且且 0iia c ,11,2,0,0ninac设则对矩阵则对矩阵A的的LU分解能进行分解能进行,且分解是唯一的。且分解是唯一的。3.追赶法的计算公式追赶法

12、的计算公式利用矩阵乘法可得利用矩阵乘法可得: 11bu ,12,3,iiial uin ,12,3,iiiibl cuin 从而可以得到从而可以得到:11ub ,12,3,iiilauin ,12,3,iiiiubl cin 解解Lyd 得得: 11yd ,12,3,kkkkydl ykn 解解Uxy 得得: nnnxyu , ,11,2,1kkkkkxyc xukn 4.追赶法的计算流程11ub ,11yd 1112,3,iiiiiiiiiiiinlauubclydl y 对于做nnnxyu 11,2,1iiiiiinxyc xu 对于做第一个循环称之为追的过程第一个循环称之为追的过程,相当

13、于消元过程相当于消元过程; 第二个循环称之为赶的过程第二个循环称之为赶的过程,相当于回代过程。相当于回代过程。20总结u 事实上，追赶法的求解过程就是将系数矩阵分解两个简单的二对角线矩阵，从而归结为求解两个简单三角形方程组的过程。u 追赶法的原理和高斯消去法相同，但考虑到方程组的特点，计算时会把大量零元素撇开，从而大大节省计算量。也称Thomas法法例2:用追赶法求解方程组4 2 0 01 4 1 00 1 4 10 0 2 4 1234xxxx 1000 解解:追的过程追的过程:114ub ,111yd ;2211 4lau ,221 27 2ubc l ,22211 4ydl y ;332

14、2 7lau ,332 326 7ubc l ,33321 14ydl y ;4437 13lau ,443 445 13ubc l ,44431 26ydl y 。赶的过程赶的过程: , 333431 45xyc xu 4441 90 xyu 222327 90 xyc xu , 1112113 45xyc xu 。22定理定理1. (Cholesky分解分解),AL设设 为为对对称称正正定定矩矩阵阵 则则一一定定存存在在一一个个主主对对角角元元全全是是正正数数的的下下三三角角阵阵使使得得TLLA 且该分解式唯一且该分解式唯一。这种关于对称正定矩阵的分解称为Cholesky分解分解nnnrn

15、rrrllllllL1111nnnrnrnrrrnraaaaaaaaaA111111设jiijaa 三、解正定矩阵方程组的平方根法 如果方程组的系数矩阵如果方程组的系数矩阵A的对称正定矩的对称正定矩阵阵,可以证明可以证明: A可以唯一分解为可以唯一分解为TALL ,其中其中L是下三角矩阵是下三角矩阵,TL是是L的转置的转置, 即即 A= 11212212nnnnllllll11211222nnnnllllll =LTL。由矩阵乘法可知由矩阵乘法可知,在对角元上在对角元上22212jjjjjjalll ; 在第在第1,2,1j 列均计算完后得列均计算完后得22212,1jjjjjjj jlall

16、l 121jjjjkkal ;在在ij 时时,iji1 j1i2 j2ijjjal ll ll l;在在1,2,j-1列均计算完后列均计算完后 ,j1ijiji1j1i 2j 2ij1j j1jjijikjkjjk1lal llllllal ll 计算是按计算是按L的第的第1列列, 第第2列列,.,第第n列的次序进行的。列的次序进行的。 计算流程如下计算流程如下:1111la ,i1i111lal , ,:j 2 3nj 12laljjjjjkk 1 对对于于做做, :ij 1nj 1lal llijijik jkjjk 1 对于做对于做:1111ybl (解解Lyb ), , :i 1iii

17、kkiik 1i2 3nybl yl 对对于于做做 :nnnnxyl , , :niikikiik i 1in12 1xyl xl 对对于于做做例例3.用平方根法求解方程组用平方根法求解方程组541464146 123x2x11x 解解: 11l5 ,21l45 ,31l1 5 2222221lal14 5 , 323231 2122lal ll1670 2233333132lall15 7 则则 500L4514 5015167015 7 解解Ly b 得得: 1y25 , 2221122ybl yl370 , 3331 132233ybl yl yl5 21 解解TLxy 得得: 3333xyl1 3 , 2232322xylxl1 6 , 1121231311xyl xl xl1 3 平方根法不需要选主元平方根法不需要选主元(矩阵正定矩阵正定)约需约需3n6次乘法的工作量次乘法的工作量,是高斯消去法的一半是高斯消去法的一半(由对称性引由对称性引起起),且具有算法稳定性且具有算法稳定性,但其要进行但其要进行n次开方运算。次开方运算。