关于矩阵的LU分解(LU Decomposition)

一、LU分解

将系数矩阵A转变成等价两个矩阵L和U的乘积 ，其中L和U分别是下三角和上三角矩阵。当A的所有顺序主子式都不为0时，矩阵A可以分解为A=LU，但不唯一。其中L是单位下三角矩阵，U是上三角矩阵。

二、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消元法 。