矩阵的三角分解

第十讲矩阵的三角分解一、Gauss消元法的矩阵形式n元线性方程组1111221nn12112222nn2n11n22nnnnaaabaaabaaabAxbijT12nT12nA(a)x[,,]b[b,bb]设0ijnnAAa,设A的k阶顺序主子式为k，若(0)111a0，可以令(0)i1i1011aca并构造Frobenius矩阵211n1nn10c1Lc012111n110c1Lc01计算可得(0)(0)(0)11121n(1)(1)(1)1(0)222n1(1)(1)n2nnaaaaaALA0aa(0)(1)1ALA初等变换不改变行列式，故0121122aa，若20，则122a0，又可定义(1)i2i2(1)22ac(i3,4,n)a，并构造Frobenius矩阵232n211Lcc11232n211Lcc1(0)(0)(0)(0)1112131n(1)(1)(1)22232n(2)1(1)(2)(2)2333n(2)(2)n3nnaaaaaaaALAaaaa(1)(2)2ALA依此类推，进行到第(r-1)步，则可得到(0)(0)(0)(0)111r11r1n(r2)(r2)(r2)(r1)r1r1r1rr1n(r1)(r1)rrrn(r1)(r1)nrnnaaaaaaaAaaaa（r＝2,3,,n-1）则A的r阶顺序主子式(0)(1)(r2)r1r1122r1r1rraaaa，若r0，则r1rra0可定义r1irirr1rraca，并构造Frobenius矩阵rr11nr11Lc1c11rr11nr11Lc1c1(0)(0)(0)(0)111r1r11n(r1)(r1)(r1)(r)1r1rrrr1rnr(r)(r)r1r1r1n(r)(r)nr1nnaaaaaaaALAaaaa(r1)(r)rALA（r＝2,3,,n-1）直到第（n－1）步，得到(0)(0)(0)11121n(1)(1)(n1)222nn1nnaaaaaAa则完成了消元的过程而消元法能进行下去的条件是r0（r＝1,2,,n-1）二、LU分解与LDU分解(0)(1)(2)(n1)112123n1AALALLALLLLA容易求出2112n1n11n12n1n2nn11c1LLLLcc1ccc1为下三角矩阵令(n1)UA为上三角矩阵，则ALU（L:lowerU:upperL:leftR:right）以上将A分解成一个单位下三角矩阵与上三角矩阵的乘积，就称为LU分解或LR分解。LU分解不唯一，显然，令D为对角元素不为零的n阶对角阵，则1ALULDDULU可以采用如下的方法将分解完全确定，即要求（1）L为单位下三角矩阵或（2）U为单位上三角矩阵或（3）将A分解为LDU，其中L，U分别为单位下三角，单位上三角矩阵，D为对角阵A＝diag[12nd,d,d]，而kkk1d（k=1,2,…n）,01，n阶非奇异矩阵A有三角分解LU或LDU的充要条件是A的顺序主子式r0（r=1,2，,n）n个顺序主子式全不为零的条件实际上是比较严格的，特别是在数值计算中，(k-1)kka很小时可能会带来大的计算误差。因此，有必要采取选主元的消元方法，这可以是列主元（在(k-1)kka，(k-1)k1ka，…(k-1)nka中选取模最大者作为新的(k-1)kka）、行主元（在(k-1)kka，(k-1)kk1a，…(k-1)kna中选取模最大者作为新的(k-1)kka）全主元（在所有(k-1)ija（ki,jn）中选模最大者作为新的(k-1)kka）。之所以这样做，其理论基础在于对于任何可逆矩阵A，存在置换矩阵P使得PA的所有顺序主子式全不为零。列主元素法：在矩阵的某列中选取模值最大者作为新的对角元素，选取范围为对角线元素以下的各元素。比如第一步：找第一个未知数前的系数i1|a|最大的一个，将其所在的方程作为第一个方程，即交换矩阵的两行，自由项也相应变换；第二步变换时，找i2|a|(i2)中最大的一个，然后按照第一步的方法继续。行主元素法：在矩阵的某行中选取模值最大者作为新的对角元素，选取范围为对角线元素以后的各元素，需要记住未知数变换的顺序，最后再还原回去。因此需要更多的存储空间，不如列主元素法方便。全主元素法：若某列元素均较小或某行元素均较小时，可在各行各列中选取模值最大者最为对角元素。与以上两种方法相比，其计算稳定性更好，精度更高，计算量增大。AxbALULybUxy两个三角形方程回代即可三、其他三角分解1.定义设A具有唯一的LDU分解（1）若将D，U结合起来得ALU（UDU），则称为A的Doolittle分解（2）若将L，D结合起来得ALU（LLD），则称为A的Crout分解2.算法（1）Crout分解，设112122n1n2nnlllLlll，121n3n1uu1uU1由ALU乘出得（1）i1i1la(1)i1,2,3,n(A,L1)第列（）第列（2）1j1j11au(1)j2,3,n(A,U1)l第行（）第行（3）i2i2i112lalu(2)(i2,3,n)(A,L2)第列第列（4）2j2j211j221ualuj3,4,n(A,U2)l（）第行（5）一般地，对A,L的第k列运算，有k1ikikimmkm1lalu(k1,2,n;ik1,k2;n)（6）对A，U的第k行运算，有k1kjkjkmmjm1kk1u(alu)(k1,2,n1;jk1,k2,n)l直至最后，得到的ijijl,u恰可排成1112131n2122232n3132333nn1n2n3nnluuulluulllullll先算列后算行3.厄米正定矩阵的Cholesky分解HAGG1i122iiikk1j1ijijikikk1jjagij1g(agg)ijg0ij理论上，Cholesky具有中间量ijg可以控制（ijiiga）的好处，应较稳健，但实际计算中发现，对希尔伯特矩阵问题，不如全主元方法。作业：p1952、3