数值分析-lec4-解线性方程组-LU分解法-1013

第二章(二)：LU分解法第二章：（1）Gauss消去法（2）LU分解法（3）带状方程组、矩阵条件数与病态方程组（4）迭代法2.2.1LU分解法矩阵A的LU分解：ALU若L为单位下三角矩阵：2111111nnnlLllDoolittle分解若U为单位上三角矩阵：1211111nnnuuUuCourt分解对矩阵A的Doolittle分解是否存在？是否唯一？2.2.1LU分解法AxbALULUxbUxyLybUxy矩阵的三角分解(LU分解)对解线性方程组有什么帮助？1111(2,3,,)iiiitttybyblyin1(-1,-2,,1)nnnnniiittiitixyuxyuxuinn1.向前迭代求解下三角系统：2.向后迭代求解上三角系统：思考:A=LU分解是否存在？2.2.1LU分解法回顾Gauss消元法的第k次消元过程：()(),(1,,)kikkkkaikikna第行第行从矩阵运算形式来看，相当于系数矩阵A左乘一个变换矩阵：()()()()1()11,,(1,,)11kkikkikkkkkkkknkaPpiknpap指标为k的初等下三角矩阵乘数1,2,,1kn（）2.2.1LU分解法因此，整个顺序Gauss消元法的过程，相当于系数矩阵A依次左乘了一系列初等下三角矩阵：121nPPPAU于是有：111121()nnAPPPU111121nnPPP是否为单位上三角阵？问题：()1()1111kkkkknkPpp-1()1()11-1-1kkkkknkPppU为上三角矩阵2.2.1LU分解法111121111:nnkkLPPPPP是否为单位下三角虑矩阵？考111()1()(1)1(k1)111111kkkkkknkkkknkPPpppp第k列第k-1列111121nnLPPP以此类推，为单位下三角矩阵！2.2.1LU分解法因此，整个顺序Gauss消元法的过程，相当于系数矩阵A依次左乘了一系列初等下三角矩阵：211111111kknnknnlLllll121nPPPAU于是有：111121()nnAPPPU..LLstALUU为单位下三角阵，为上三角阵矩阵A的Doolittle分解的存在性！2.2.1LU分解法(1)前n-1顺序主子式非0，保证可以进行n-1次消元（前n-1个主元非0）(2)唯一性证明（略）(3)必要性证明（略）矩阵A的Doolittle分解的存在唯一性：[](2)Doolittle10(1,2,,-1)ijnnkAanAnDkn矩阵有唯一的分解的充要条件是矩阵的前个顺序主子式定理2.3：（同顺序Gauss消去法）111211112121222212211211111nnnnnnnnnnnnnnaaauuuaaaluuaaallu2.2.1LU分解法矩阵A的Crout分解的存在唯一性：[](2)Crout10(1,2,,-1)ijnnkAanAnDkn矩阵有唯一的分解的充要条件是矩阵的前个顺序主子式推论：111211112121222212211211111nnnnnnnnnnnnnnaaaluuaaalluaaalll（同顺序Gauss消去法）2.2.1LU分解法（L为单位下三角矩阵，U为上三角矩阵）111211112121222212221212111nnnnnnnnnnnnaaauuuaaaluuaaallu比较第1行：1111(1,2,)jjjjaujnua，比较第1列：11111111(2,3,,)/iiiialuinlauDoolittle分解算法：2.2.1LU分解法Doolittle分解算法：（把已计算的第一行第一列放入原矩阵相应位置）111211112121222212221212111nnnnnnnnnnnnuuuuuulaaluulaallu比较第2行：2211222211(2,3,,)jjjjjjaluujnualu比较第2列：21122222211222(3,4,,)()/iiiiiialuluinlaluu2.2.1LU分解法（把已计算的第二行第二列放入原矩阵相应位置）1112111121212222122233312123111nnnnnnnnnnnnnnuuuuuuluuluuaallullaa比较第k行：比较第k列：1111,,kkkjkrrjkjkjkjkrrjrraluujknualu11111,,()/kkikirrkikkkikikirrkkkrraluluiknlaluuDoolittle分解算法：2.2.1LU分解法使用Doolittle分解法求解线性方程组的条件:(1)前n-1顺序主子式非0；（可进行Doolittle分解）(2)系数矩阵A行列式非0；（U非奇异，能够进行回带运算）LU分解求线性方程组(使用Doolittle分解)1112121222333123nnnnnnnnuuuluuALUuullluLybUxyAxb注：Crout分解可以类似的推导出来其中L为单位下三角矩阵，U为上三角矩阵！[课本P21,(2.13)]Doolittle分解2.2.1LU分解法例：计算矩阵A的Doolittle分解21104331A879567982.2.2*选主元的LU分解法11121111212221221,11,2111,1,12,112,1kknkknkkkkkkknkkkknnnkkknknknnuuuuuluuuulluuuaaaAllallllkku希望为较大的数！设矩阵A的Doolittle分解第k-1步已完成,于是有11,(,1,,)kkjkjkrrjrualujkkn11()/,(1,,)kikikirrkkkrlaluuikn(1)0(2)||0kkkkuu考虑两种情况：2.2.2*选主元的LU分解法为了考虑矩阵形式的LU分解，我们引入初等置换矩阵：11011Q11011kk第行()kkiik第行左乘行交换，右乘列交换！2.2.2*选主元的LU分解法1221:1,nnkADoolittleDoolittleALUAkDoolitPPPlePUtPA考虑矩阵的分解的矩阵表示形式分解的过程相当于矩阵不断左乘初等下三角阵：假设已执行完第步的分解于是有：121-1*121111211,,kkkkkkkkkkkkkkkPPPQAUkkiQPPPAUUkPPPPAPQQQUU在执行第步之前交换第行与第行上式两侧左乘以初等置换矩阵之后再进行第步分解k2.2.2*选主元的LU分解法*12111*1-1*1111111-1121121,,,kkkkkkkkkkkkkkkkkkiQPPPAUUQULLPPPPPQQQQPL在执行第步之前交换第行与第行上式两侧左乘以初等置换矩阵我们注意到乘以对矩阵的形式没有影响此时为*-1*1***111**-1-1121-1****1211-11()(),,{}()kkkkkkkkkkkkkkkkkLQLQLPPPLkPPPAUQALQQQUQQ非单位下三角阵。为保持的矩阵结构，左乘做一次行变换为单位下三角阵于是在执行第步之前相当于2.2.2*选主元的LU分解法-11112211,(1,2,,1)nnkkkPQPQPQPQAUQkn一般的，我们有这里为初等置换阵或单位阵，于是有：定理2.412Doolittle-1,rnnARQQAQALULQQQrnUQ若矩阵非奇异，则存在置换矩阵，使得可以作分解其中是单位下三角矩阵，是上三角矩阵阵。（置换矩）2.2.2*选主元的LU分解法证明：332332211332211332332123321**23231321233234,:()()()(QQQQnPQPQPQAUPQPQPQAUPQPQQQPQQQQQQAUPQPQPQQPQQQ我们以为例于是有上式可写成：于是有令，321**321*1*11123),,()()QQQQPPPQAULPPPL易知其仍为初等下三角阵令其为置换矩阵于是有令，为单位下三角矩阵。2.2.2*选主元的LU分解法11121111212221221,11,2111,1,12,112,1kknkknkkkkkkknkkkknnnknkkkknnnuuuuuluuuulluuuaaAlllaalll设矩阵A的Doolittle分解第k-1步已完成,于是有11,(,1,,)||max||,kkiiiikirrkrkiikkinsualuikknisski选行号使得交换第行与第行在LU分解过程中交换矩阵两行会对求解Ax=b造成什么影响？2.2.2*选主元的LU分解法111.1,2,,(1):(,1,,)(2)max,()(3),(,1,,),(1,2,,1)(4)DokkkkiiikittktkiikkinkiiikiiiknssaluikknissIpkiaaikknllikk对执行计算选主元:取使得记录主元行号交换交换执行第步11olittle(1,2,,)/kkkkkkkjkjkttjtikikkausualujkknlsu分解：选主元的Doolittle分解的过程！2.2.2*选主元的LU分解法2.1,2,,1,(1)()(2)(3)(3)itintIpiitbb对如果则转继续循环3./LyQbUxy使用向前后迭代求解选主元的Doolittle分解求解线性方程组Ax=bAxbQAxQbLyQbUxy在矩阵分解的过程中同时交换右端项！2.2.2*选主元的LU分解法例：用选主元的LU分解法求解下列一组方程组123[,,,,]nAxBbbbb12nALULyQbLyQbLyQbUxbUxbUxb只需要进行1次矩阵分解，再执行n次回带过程！比用n次选主元的Gauss消去法效率更高！谢谢！