矩阵的三角分解法ppt课件.ppt

回顾：回顾：定义定义 由单位矩阵由单位矩阵 经过一次初等变换得到的方经过一次初等变换得到的方阵称为初等矩阵阵称为初等矩阵. .E性质性质 设设 是一个是一个 矩阵，对矩阵，对 施行一施行一次初等行变换，相当于在次初等行变换，相当于在 的左边乘以相应的的左边乘以相应的 阶初等矩阵；对阶初等矩阵；对 施行一次初等列变换，相当于施行一次初等列变换，相当于在在 的右边乘以相应的的右边乘以相应的 阶初等矩阵阶初等矩阵. .AAAAmn mnAijrkrAB 若若则则( ( )E ij kAB jickcAB 则则( ( )AE ij kB ijrrAB 若若则则( , )E i j AB jiccAB 则则( , )AE i jB ik rAB 若若则则( ( )E i kAB ik cAB 则则( ( )AE i kB 3.2 矩阵的三角分解法矩阵的三角分解法3.2.1 高斯消去法的矩阵描述高斯消去法的矩阵描述则有则有(1)(2)1(1)(2)1M AAM bb 记记 为为 ，Axb (1)(1)Axb 2111111mM 311111m 11111nm (1)A(1)b(2)b(2)A1133112211()()()nnrmrrmrrmr 2131111111nmmMm 则有则有( )(1)( )(1)kkkkkkM AAM bb 第第 次消元：次消元：k( )( ),kkAb化为化为(1)(1),kkAb1,111kkknkMmm 1,2,1kn (1)( )121(1)( )121nnnnMM M AAMM M bb 故故又又(1)( )121nnMM M AA 111(1)111( )121121121nnnnMMMMM M AMMMA (1)111( )121nnAMMMA 由于由于10kM 1,2,1kn 故故 均可逆。均可逆。kM121131111111nmmMm 213111111nmmm 111,111kkknkMmm 1,111kknkmm 111121nMMM 213111111nmmm3221111nmm,11111n nm 213132431231111nnnmmmmmmm L下三角矩阵下三角矩阵(1)111( )121nnAMMMA ( )nLA 记记 为为 ，( )nAU则则ALU 上三角矩阵上三角矩阵三角形矩阵三角形矩阵 和和 相乘，即相乘，即 ALU UL因此高斯消去法的实质是将系数矩阵因此高斯消去法的实质是将系数矩阵 分解为两个分解为两个A3.2.2 矩阵的直接三角分解矩阵的直接三角分解分解。分解。LU将矩阵将矩阵 分解成一个下三角矩阵分解成一个下三角矩阵 和一个上和一个上AL三角矩阵三角矩阵 的乘积，称为对矩阵的乘积，称为对矩阵 的三角分解，又称的三角分解，又称AU注：注：依赖于消元过程。依赖于消元过程。（1）矩阵矩阵 的元素可以从的元素可以从 的元素直接得到，不的元素直接得到，不,L UA（2）分解不唯一。分解不唯一。,L U杜里特尔分解杜里特尔分解或或 为为单位单位上三角矩阵时，分解是唯一的。上三角矩阵时，分解是唯一的。U当要求当要求 为为单位单位下三角矩阵下三角矩阵L（3）ALU 的乘积，称为杜里特尔分解；的乘积，称为杜里特尔分解；将将 分解为一个单位下三角阵和一个上三角阵分解为一个单位下三角阵和一个上三角阵A的乘积，称为克洛特分解；的乘积，称为克洛特分解；将将 分解为一个下三角阵和一个单位上三角阵分解为一个下三角阵和一个单位上三角阵A单位上三角矩阵单位上三角矩阵单位下三角矩阵单位下三角矩阵克洛特分解克洛特分解杜里特尔分解的唯一性（充分条件）：杜里特尔分解的唯一性（充分条件）：ALU 设设 有两种有两种 分解，分解，LUA成一个单位下三角阵成一个单位下三角阵 和一个非奇异的上三角阵和一个非奇异的上三角阵 的的矩阵矩阵 各阶主子式不为零，则可惟一地分解各阶主子式不为零，则可惟一地分解AL乘积。乘积。U因为因为欲证欲证证明证明：（反证法）：（反证法）,LL UU 其中其中 为单位下三角阵，为单位下三角阵，,L L为上三角阵。为上三角阵。,U U0A AL U 0 L U 故故 均可逆。均可逆。 , ,L L U U0,0,0,0,LULU L U LUL U 1L 1L 1U 1U 证。证。即即1L L 1UU 分析知分析知 ,LL UU 均为单位下三角阵，均为单位下三角阵，,L L故故 也为单位下三角阵，也为单位下三角阵，11,LL 故惟一性得故惟一性得因此因此则则 仍为单位下三角阵。仍为单位下三角阵。1L L 同理同理 为上三角阵。为上三角阵。1UU 1L L 1,UUI 注：注：例例定理中所述条件对克洛特分解也同样适用。定理中所述条件对克洛特分解也同样适用。（1）0110A （2）0,1,bab则应存在则应存在 使使, , ,a b c d0A 定理中的条件是矩阵定理中的条件是矩阵 的各阶主子式不为零，的各阶主子式不为零，A而不能改为而不能改为 的行列式不为零。的行列式不为零。A设设 存在杜里特尔分解，存在杜里特尔分解，A01101010bdAac故应有故应有因此因此 不存在杜里特尔分解。不存在杜里特尔分解。A即矩阵非奇异不能保证其存在杜利特尔分解即矩阵非奇异不能保证其存在杜利特尔分解。杜里特尔分解的步骤：杜里特尔分解的步骤：设设 为，为，ALU 111211112121222212221212111nnnnnnnnnnnnaaauuuaaaluuaaallu 利用矩阵乘法分析利用矩阵乘法分析 第一行和第一列的元素可知第一行和第一列的元素可知A11,iiau 1111,iial u 1,2,in 2,3,in 故可得到故可得到 的第一行元素和的第一行元素和 的第一列元素：的第一列元素：UL11,iiua 1111,iialu 1,2,in 2,3,in 111211112121222212221212111nnnnnnnnnnnnaaauuuaaaluuaaallu 利用矩阵乘法分析利用矩阵乘法分析 第二行和第二列的其余元素，第二行和第二列的其余元素，A22112,iiial uu2112222,iiial ul u2,3,in 3,4,in 22211,iiiual u2211222(),iiilal uu假设已经得到假设已经得到 的前的前 行元素和行元素和 的前的前 列元素，列元素，UL1r 1r 22211,iiiual u2211222(),iiilal uu2,3,in 3,4,in 利用矩阵乘法分析利用矩阵乘法分析 第第 行和第行和第 列的其余元素，列的其余元素，Arr1111,111,1,1,11,1,11,1,1rrnrrrr rr nrrrrrrnnnrn rnnaaaaaaaaaaaaaaaa 1,1,1,11,1,1111rrr rnn rn rllllll 111,1111,11,1,rrnrrrrrnrrr nnnuuuuuuuuuu 分析分析 rii ra 12,1(,1,0,0)rrr rlll ,1,ir rn 11rrkkirikl uu 的的 列列Ui 的的 行行Lr 1200iiriiiuuuu 1122,11,ririr rriril ul uluu 分析分析 iri ra 12,1(,1,0,0)iii rirllll 1,2,irrn 11rikkrirrrkl ul u 的的 列列Ur 的的 行行Li 121,00rrrrrruuuu 1122,11,iriri rrrirrrl ul ulul u 综上可得：综上可得： ,1,ir rn 11rrkkirikl uu 1,2,irrn 11rikkrirrrkl ul u iri ra rii ra 11rririrkkikual u ,1,ir rn 11()riririkkrrrklal uu 1,2,irrn 依据上式可得到依据上式可得到 第第 行元素和行元素和 的第的第 列元素，列元素，ULrr杜里特尔分解的手算步骤：杜里特尔分解的手算步骤：12()a31()a21()a11()a 1()na()nna3()na2()na32()a22()a 1nu12u11u21l32l31lnnu3nu2nu22u(2)( 2) (4)(2)(3)(5)(7)(4)(7)322221 613223477245A 先行后列，先先行后列，先 后后 。LU(2)( 2) (4)(2)(3)(5)(7)(4)(7)322221 613121121L 223316U 2 3 636 UA 3.2.3 用矩阵三角分解法解线性方程组用矩阵三角分解法解线性方程组Uxy LUxb ALU Axb 即先求解即先求解令令则方程组则方程组 的求解可归的求解可归Axb Uxy Lyb LybUxy 1111iiiikkkybybl y 再求解再求解11()nnnniiiikkiikxyuxyu xu 11212212111nnnnyblybllyb 111211122222nnnnnnuuuxyuuxyuxy 结为求解两个三角形方程组结为求解两个三角形方程组例例3-8： 用杜里特尔分解法求解方程组。用杜里特尔分解法求解方程组。112233223477245xbxbxb 由方程组由方程组对系数矩阵进行杜里特尔分解，对系数矩阵进行杜里特尔分解，解：解：121121L 223316U LybUxy 123132111217yyy 13y 212 35y 37( 1) 32 ( 5)6y 再由方程组再由方程组123223331566xxx 31x 2( 51 1) 32x 131 32 ( 2)22x 注：注：（1）方程组方程组 与方程组与方程组 为同解的方程组。为同解的方程组。Axb Uxy （2）方法可将方法可将 化为化为 。yb对系数矩阵进行对系数矩阵进行 分解的同时，利用相同的分解的同时，利用相同的LU(2)( 2) (4)(2)(3)(5)(7)(4)(7)322221 613(3)( 7) (1)35 6（3）利用杜里特尔分解可解利用杜里特尔分解可解线性方程组系线性方程组系。123AxbAxbAxb 系数矩阵相同，系数矩阵相同，常数项不同常数项不同（4）杜里特尔分解可用来求解矩阵的逆矩阵。杜里特尔分解可用来求解矩阵的逆矩阵。1nnnA AE 则则令令求解该方程组系即可求得求解该方程组系即可求得 的逆矩阵。的逆矩阵。AnjjA ae 112(,)nnAa aa 12(,)nnEe ee 1,2,jn 克洛特分解克洛特分解111211112121222212221212111nnnnnnnnnnnnaaaluuaaalluaaalll 为为单位单位上三角矩阵上三角矩阵U类似杜里特尔分解的分析过程有类似杜里特尔分解的分析过程有11,iila 1111,iiaul 1,2,in 2,3,in 先列后行先列后行，先先 后后 。LU分析知其运算规则为：分析知其运算规则为： 2221122(),iiiual ul22112,iiilal u2,3,in 3,4,in (2)( 2) (4)(2)(3)(5)(7)(4)(7)3 212462 41 33243264L 113 211 31U 223477245A 3.2.4 追赶法追赶法用于求解三对角方程组用于求解三对角方程组的方程组，称为的方程组，称为三对角方程组三对角方程组；形如形如11112222233311111nnnnnnnnnxfbcxfabcabcabcxfabxf 其系数矩阵称为其系数矩阵称为三对角矩阵三对角矩阵。1()c4()b2()a1()b2()c3()c4()a3()b3()a2()b 2a222ucl 11lb 111ucb 2221lba u3a4()c3332lba u4a333ucl 对其进行克洛特分解：对其进行克洛特分解：122nnlalal11111nuu 1()c4()b2()a1()b2()c3()c4()a3()b3()a2()b 2a222ucl 11lb 111ucl 2221lba u3a4()c3332lba u4a333ucl 对其进行克洛特分解：对其进行克洛特分解：分析上式可知计算顺序为：分析上式可知计算顺序为：1,2,1in iiiucl 111iiiilbau 11lb 11lu2l2u3l3unl即即( 1) ( 2) ( 1) (2)( 3) ( 2) ( 2) (4)(3) 5 21 2 1 2 3 (5)4 5 212 55 6 5 2215 2212 535 2 11 214 515 61 即先解即先解对三对角方程组对三对角方程组Axf 的求解仍可转化为的求解仍可转化为Uxy LUxf ALU Axf 令令LyfUxy Lyf 1112222nnnnlyfalyfalyf 21222a yl yf111l yf 32333a yl yf1nnnnna yl yf 111yfl 即即111l yf 1iiiiia yl yf 2,3,in 1iiiiiyfa yl 2,3,in “追追”再解再解111221111nnnxyuxyuxy Uxy 1121xu xynnxy 即即 1,2,2,1inn 2232xu xy111nnnnxuxynnxy 1iiiixu xy nnxy 1iiiixyu x 1,2,2,1inn “赶赶”上述求解方程组的方法称为追赶法，也称托马斯法。上述求解方程组的方法称为追赶法，也称托马斯法。例例3-12： 用追赶法解下列三对角方程组。用追赶法解下列三对角方程组。123421313212420355xxxx 215 2212 535 2L 11 214 515 61U 解：解：12342315 21212 5035 25yyyy 13 2y 21(3 2)( 1)(5 2)y 1 301 ( 2)(12 5)y 5 6 45(5 6) ( 3)(5 2)y 1 1234311 22114 5515 6611xxxx 41x 355() ( 1)66x 0 241() 05x 1 131() 122x 2 11212212111nnnnyblybllyb 111211122222nnnnnnuuuxyuuxyuxy 21l3nu2nu 12u11u2a有有2,3,in 方法方法计算过程：计算过程：(1)110a (1)11(1)11iiama (1)(1)Axb (1)(1)ijbb (1)(1),ijAa ( )0,kkka ( )kkka( )0,kkka 1,2,in UL由于由于由于由于由于由于由于由于由于由于