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

解线性方程组的矩阵三角分解法第一页，共十六页，编辑于2023年，星期五2本讲内容一般线性方程组

LU分解与PLU分解对称正定线性方程组

平方根法－－Cholesky分解对角占优三对角线性方程组

追赶法第二页，共十六页，编辑于2023年，星期五3LU分解将一个矩阵分解成结构简单的三角形矩阵的乘积矩阵的三角分解矩阵的LU(Doolittle)分解矩阵的LDR

分解克洛脱(Crout)分解第三页，共十六页，编辑于2023年，星期五4计算LU分解利用矩阵乘法直接计算LU分解LU=A比较等式两边的第一行得：u1j=a1j比较等式两边的第一列得：比较等式两边的第二行得：比较等式两边的第二列得：(j=1,…,n)(i=2,…,n)(j=2,…,n)(i=3,…,n)U

的第一行L

的第一列U

的第二行L

的第二列第四页，共十六页，编辑于2023年，星期五5计算LU分解第k

步：此时U

的前k-1行和

L

的前k-1列已经求出直到第n

步，便可求出矩阵L

和U

的所有元素。比较等式两边的第k行得：(j=k,…,n

)比较等式两边的第k列得：(i=k+1,…,n

)第五页，共十六页，编辑于2023年，星期五6LU分解算法算法：(LU分解

)fork=1tonendj=k,…,ni=k+1,…,nMatlab程序参见：ex51.m乘除法运算量：(n3-n)/3为了节省存储空间，通常用A

的绝对下三角部分来存放L(对角线元素无需存储)，用

A

的上三角部分来存放U

第六页，共十六页，编辑于2023年，星期五7PLU分解矩阵的PLU

分解fork=1tonendi=k,k+1,…,nj=1,

2,…,ni=k+1,…,nj=k+1,…,nMatlab程序：上机练习

第七页，共十六页，编辑于2023年，星期五8Cholesky分解对称正定矩阵的三角分解－－Cholesky

分解定理：设A

是对称矩阵，若A

的所有顺序主子式都不为0，则A

可唯一分解为其中L

为单位下三角阵，D

为对角矩阵A=LDLT定理：（Cholesky分解）若A

对称正定，则A

可唯一分解为其中L

为下三角实矩阵，且对角元素都大于0A=LLT第八页，共十六页，编辑于2023年，星期五9计算Cholesky分解

Cholesky

分解的计算直接比较等式两边的元素

计算公式第九页，共十六页，编辑于2023年，星期五10Cholesky分解算法for

j=1tonendi=j+1,…,n算法：(Cholesky分解

)第十页，共十六页，编辑于2023年，星期五11平方根法A

对称正定算法：(解对称正定线性方程组的平方根法

)计算A

的Cholesky分解解方程：Ly=b

和LTx=yi=2,3,…,ni=n-1,…,2,1第十一页，共十六页，编辑于2023年，星期五12改进的Cholesky分解计算公式改进的Cholesky

分解第十二页，共十六页，编辑于2023年，星期五13改进的Cholesky分解for

j=1tonendi=j+1,…,n算法：(改进的Cholesky分解

)

优点：避免开方运算第十三页，共十六页，编辑于2023年，星期五14改进的平方根法A

对称正定算法：(解对称正定线性方程组的改进的平方根法

)计算改进的Cholesky分解解方程：Ly=b

和DLTx=yi=2,3,…,ni=n-1,…,2,1第十四页，共十六页，编辑于2023年，星期五15追赶法对角占优的三对角矩阵的LU分解

计算公式i=2,3,…,n-1第十五页，共十六页，编辑于2023年，星期五16追赶法A

三对角矩阵（对角占优）算法：(追赶法

)i=