解线性方程组的矩阵三角分解法

1第五章解线性方程组的直接方法计算方法——矩阵三角分解法2本讲内容一般线性方程组LU分解与PLU分解对称正定线性方程组平方根法－－Cholesky分解对角占优三对角线性方程组追赶法3LU分解将一个矩阵分解成结构简单的三角形矩阵的乘积矩阵的三角分解ALU矩阵的LU(Doolittle)分解矩阵的LDR分解ALDR克洛脱(Crout)分解ALU4计算LU分解利用矩阵乘法直接计算LU分解111211112121222212221,112111nnnnnnnnnnnnnuuuaaaluuaaalluaaaLU=A比较等式两边的第一行得：u1j=a1j比较等式两边的第一列得：1111iilau比较等式两边的第二行得：22211jjjualu比较等式两边的第二列得：2211222iiilaluu(j=1,…,n)(i=2,…,n)(j=2,…,n)(i=3,…,n)U的第一行L的第一列U的第二行L的第二列5计算LU分解第k步：此时U的前k-1行和L的前k-1列已经求出直到第n步，便可求出矩阵L和U的所有元素。比较等式两边的第k行得：11111,1,kkjkiijikjkjkjkkkjualulualu(j=k,…,n)比较等式两边的第k列得：11,11,11ikikikiiikijjkkkkjkkkklaluluualuu(i=k+1,…,n)6LU分解算法算法：(LU分解)fork=1ton-11,kkjkjkiijiualu11,kikikijjkkkjlaluuendj=k,…,ni=k+1,…,nMatlab程序参见：ex51.mkjaika乘除法运算量：(n3-n)/3为了节省存储空间，通常用A的绝对下三角部分来存放L(对角线元素无需存储)，用A的上三角部分来存放U7PLU分解PALU矩阵的PLU分解fork=1ton-11,kikikijjkjaaaaendi=k,k+1,…,nmax,Ip()kikikkkinaaki,kkjijaaj=1,2,…,n,ikikkkaaa11,kkjkjkiijiaaaai=k+1,…,nj=k+1,…,nMatlab程序：上机练习-1111kkjkjkiijikikikijjkkkjualulaluu8Cholesky分解对称正定矩阵的三角分解－－Cholesky分解定理：设A是对称矩阵，若A的所有顺序主子式都不为0，则A可唯一分解为其中L为单位下三角阵，D为对角矩阵A=LDLT定理：（Cholesky分解）若A对称正定，则A可唯一分解为其中L为下三角实矩阵，且对角元素都大于0A=LLT9计算Cholesky分解Cholesky分解的计算直接比较等式两边的元素1111211111212122222212221,112nnnnnnnnnnnnnnnllllaaallllaaallllaaa111jnijikjkikjkjjijkkallllll计算公式10Cholesky分解算法forj=1tonend11221,jjjjjjkklali=j+1,…,n11,jijijikjkjjklalll算法：(Cholesky分解)111jnijikjkikjkjjijkkallllll11平方根法AxbA对称正定算法：(解对称正定线性方程组的平方根法)计算A的Cholesky分解解方程：Ly=b和LTx=yi=2,3,…,n111111,,iiiikkiikyblyblyli=n-1,…,2,11,nnnnniikikiikixylxylxl12改进的Cholesky分解121121221,1111111nTnnnnndllldlALDLlld计算公式111jnijikkjkikkjkijjjjkkaldlldlldl改进的Cholesky分解13改进的Cholesky分解forj=1tonend121,jjjjjkkkdaldi=j+1,…,n11,jijijikkjkjklaldld算法：(改进的Cholesky分解)优点：避免开方运算111jnijikkjkikkjkijjjjkkaldlldlldl14改进的平方根法AxbA对称正定算法：(解对称正定线性方程组的改进的平方根法)计算改进的Cholesky分解解方程：Ly=b和DLTx=yi=2,3,…,n1111,,iiiikkkybyblyi=n-1,…,2,11,,nnnniiikikkixydxydlx15追赶法111122211111nnnnnnbcaacaab对角占优的三对角矩阵的LU分解计算公式1111111,bccb1nnnnba1iiiiba1iiiiiiiccbai=2,3,…,n-116追赶法AxfA三对角矩阵（对角占优）算法：(追赶法)i=2,3,…,n11111,iiiiiiiyfbyfaybai=n-1,…,2,11,nniiiixyxyx1111,iiiiiiicbccbai=2,3,…,n-1运算量：5n-42n–3次2n次n–1次