在线性代数中, LU分解(LU Decomposition)是矩阵分解的一种,可以将一个矩阵分解为一个下三角矩阵和一个上三角矩阵的乘积(有时是它们和一个置换矩阵的乘积)。LU分解主要应用在数值分析中,用来解线性方程、求反矩阵或计算行列式。
编辑摘要LU分解在本质上是 高斯消元法的一种表达形式。实质上是将A通过 初等行变换变成一个上三角矩阵,其 变换矩阵就是一个单位下三角矩阵。这正是所谓的杜尔里特算法(Doolittle algorithm):从下至 上地对矩阵A做 初等行变换,将对角线左下方的元素变成零,然后再证明这些行变换的效果等同于左乘一系列单位下三角矩阵,这一系列单位下三角矩阵的乘积的逆就是L矩阵,它也是一个单位下三角矩阵。这类算法的 复杂度一般在(三分之二的n三次方) 左右。
(i)Doolittle分解
对于 非奇异矩阵(任n阶 顺序主子式不全为0)的方阵A,都可以进行Doolittle分解,得到A=LU,其中L为单位下三角矩阵,U为上三角矩阵;这里的Doolittle分解实际就是Gauss变换;
(ii)Crout分解
对于 非奇异矩阵(任n阶 顺序主子式不全为0)的方阵A,都可以进行Crout分解,得到A=LU,其中L为下三角矩阵,U为单位上三角矩阵;
(iii)列主元三角分解
对于 非奇异矩阵的方阵A,采用列主元三角分解,得到PA=LU,其中P为一个 置换矩阵,L,U与Doolittle分解的规定相同;
(iv)全主元三角分解
对于非奇异矩阵的方阵A,采用全主元三角分解,得到PAQ=LU,其中P,Q为置换矩阵,L,U与Doolittle分解的规定相同;
(v)直接三角分解
对于非奇异矩阵的方阵A,利用直接三角分解推导得到的 公式(Doolittle分解公式或者Crout分解公式),可以进行递归操作,以便于计算机编程实现;
(vi)“追赶法”
追赶法是针对带状矩阵(尤其是 三对角矩阵)这一大 稀疏矩阵的特殊结构,得出的一种保带性分解的 公式推导,实质结果也是LU分解;因为大稀疏矩阵在工程领域应用较多,所以这部分内容需要特别掌握。
(vii)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 消元法 。
联系客服