lu分解(高斯消元法的一种表达形式)
温馨提示:这篇文章已超过534天没有更新,请注意相关的内容是否还可用!
lu分解
高斯消元法的一种表达形式
在线性代数中,LU分解(LU Decomposition)是矩阵分解的一种,可以将一个矩阵分解为一个下三角矩阵和一个上三角矩阵的乘积(有时是它们和一个置换矩阵的乘积)。LU分解主要应用在数值分析中,用来解线性方程、求反矩阵或计算行列式。
中文名 | lu分解 |
外文名 | LU Decomposition |
本质 | 高斯消元法的一种表达形式 |
学科 | 线性代数 |
应用 | 数值分析 |
算法
LU分解在本质上是高斯消元法的一种表达形式。实质上是将A通过初等行变换变成一个上三角矩阵,其变换矩阵就是一个单位下三角矩阵。这正是所谓的杜尔里特算法(Doolittlealgorithm):从下至上地对矩阵A做初等行变换,将对角线左下方的元素变成零,然后再证明这些行变换的效果等同于左乘一系列单位下三角矩阵,这一系列单位下三角矩阵的乘积的逆就是L矩阵,它也是一个单位下三角矩阵。这类算法的复杂度一般在(三分之二的n三次方)左右。
改进
Doolittle分解
对于非奇异矩阵(任n阶顺序主子式不全为0)的方阵A,都可以进行Doolittle分解,得到A=LU,其中L为单位下三角矩阵,U为上三角矩阵;这里的Doolittle分解实际就是Gauss变换。
Crout分解
对于非奇异矩阵(任n阶顺序主子式不全为0)的方阵A,都可以进行Crout分解,得到A=LU,其中L为下三角矩阵,U为单位上三角矩阵。
列主元三角分解
对于非奇异矩阵的方阵A,采用列主元三角分解,得到PA=LU,其中P为一个置换矩阵,L,U与Doolittle分解的规定相同。
全主元三角分解
对于非奇异矩阵的方阵A,采用全主元三角分解,得到PAQ=LU,其中P,Q为置换矩阵,L,U与Doolittle分解的规定相同。
直接三角分解
对于非奇异矩阵的方阵A,利用直接三角分解推导得到的公式(Doolittle分解公式或者Crout分解公式),可以进行递归操作,以便于计算机编程实现。
“追赶法”
追赶法是针对带状矩阵(尤其是三对角矩阵)这一大稀疏矩阵的特殊结构,得出的一种保带性分解的公式推导,实质结果也是LU分解;因为大稀疏矩阵在工程领域应用较多,所以这部分内容需要特别掌握。
Cholesky分解法(平方根法)和改进的平方根法
Cholesky分解法是是针对正定矩阵的分解,其结果是A=LDLT=LD(1/2)D(1/2)LT=L1L1T。如何得到L1,实际也是给出了递归公式。
改进的平方根法是Cholesky分解的一种改进。为避免公式中开平方,得到的结果是A=LDLT=TLT,同样给出了求T,L的公式。
小结:
1、从(i)~(iv)是用手工计算的基础方法,(v)~(vi)是用计算机辅助计算的算法公式指导。
2、这些方法产生的目的是为了得到线性方程组的解,本质是高斯Gauss消元法。
参考资料
1.MATLAB学习笔记——线性方程与线性系统·IT610