在
线性代数中, LU分解(LU Factorization)是
矩阵分解的一种,可以将一个矩阵分解为一个
下三角矩阵和一个
上三角矩阵的乘积(有时是它们和一个
置换矩阵的乘积)。LU分解主要应用在
数值分析中,用来解
线性方程、求反矩阵或计算
行列式。
将
系数矩阵A转变成等价两个矩阵L和U的乘积 ,其中L和U分别是单位下三角矩阵和上三角矩阵。当A的所有
顺序主子式都不为0时,矩阵A可以唯一地分解为A=LU。其中L是下三角矩阵,U是上三角矩阵。
LU分解在本质上是
高斯消元法的一种表达形式。实质上是将A通过初等行变换变成一个上三角矩阵,其
变换矩阵就是一个单位下三角矩阵。这正是所谓的杜尔里特算法(Doolittle
algorithm):从下至上地对矩阵A做初等行变换,将
对角线左下方的元素变成零,然后再证明这些行变换的效果等同于
左乘一系列单位下三角矩阵,这一系列单位下三角矩阵的乘积的逆就是L矩阵,它也是一个单位下三角矩阵。这类算法的
复杂度一般在(三分之二的n三次方) 左右。
对于
非奇异矩阵(任n阶
顺序主子式不全为0)的方阵A,都可以进行Doolittle分解,得到A=LU,其中L为单位下三角矩阵,U为上三角矩阵;这里的Doolittle分解实际就是Gauss变换;
对于非奇异矩阵的方阵A,采用列主元三角分解,得到PA=LU,其中P为一个
置换矩阵,L,U与Doolittle分解的规定相同;
追赶法是针对
带状矩阵(尤其是
三对角矩阵)这一大
稀疏矩阵的特殊结构,得出的一种保带性分解的公式推导,实质结果也是LU分解;因为大稀疏矩阵在工程领域应用较多,所以这部分内容需要特别掌握。
(vii)Cholesky分解法(平方根法)和改进的
平方根法Cholesky分解法是是针对
正定矩阵的分解,其结果是 A=LDLT=LD(1/2)D(1/2)LT=L1L1T。如何得到L1,实际也是给出了
递归公式。