矩阵分析之 实矩阵分解（2）LU，PLU分解

前言

之前提到了特征分解和奇异值分解两种矩阵分解的方法，其中特征分解要求n阶方阵且具有n个线性无关的特征向量；SVD分解对矩阵没有要求，但是分解的速度很慢。为了提升分解的效率，可以使用LU分解法。

LU分解（Doolittle杜立特解法） 分解条件

对于可逆方阵 A A A，可以将其分解为下三角矩阵 L L L和上三角矩阵 U U U的乘积： A = L U A x = [ l 11 l 21 l 22 l 31 l 32 l 33 ] A=LU \\ \quad \\ Ax=\begin{bmatrix} l_{11} & \\ l_{21} & l_{22} \\ l_{31} & l_{32} & l_{33} \\ \end{bmatrix} A=LUAx=⎣⎡​l11​l21​l31​​l22​l32​​l33​​⎦⎤​ 上下三角矩阵对于方程组求解有良好的求解性质，例如： A x = [ l 11 l 21 l 22 l 31 l 32 l 33 ] x = [ b 1 b 2 b 3 ] x 1 = b 1 / l 11 x 2 = ( b 2 − l 21 x 1 ) / l 22 x 3 = ( b 3 − l 31 x 1 − l 32 x 2 ) / l 33 Ax=\begin{bmatrix} l_{11} & \\ l_{21} & l_{22} \\ l_{31} & l_{32} & l_{33} \\ \end{bmatrix}x = \begin{bmatrix} b_1 \\ b_2 \\ b_3 \\ \end{bmatrix} \\ \quad \\ x_1=b_1/l_{11} \\ x_2=(b_2-l_{21}x_1)/l_{22} \\ x_3=(b3-l_{31}x_1-l_{32}x_2)/l_{33} Ax=⎣⎡​l11​l21​l31​​l22​l32​​l33​​⎦⎤​x=⎣⎡​b1​b2​b3​​⎦⎤​x1​=b1​/l11​x2​=(b2​−l21​x1​)/l22​x3​=(b3−l31​x1​−l32​x2​)/l33​ 三角矩阵求解的时间复杂度为 O ( n 2 ) O(n^2) O(n2)

分解方法

由于矩阵 A A A可逆，可通过高斯消元法将 A A A化为上三角矩阵，例如： A = [ 1 1 2 2 1 1 1 2 1 ] [ 1 0 0 0 1 0 − 1 0 1 ] A = [ 1 1 2 2 1 1 0 1 − 1 ] [ 1 0 0 − 2 1 0 0 0 1 ] [ 1 0 0 0 1 0 − 1 0 1 ] A = [ 1 1 2 0 − 1 − 3 0 1 − 1 ] [ 1 0 0 0 1 0 0 1 1 ] [ 1 0 0 − 2 1 0 0 0 1 ] [ 1 0 0 0 1 0 − 1 0 1 ] A = [ 1 1 2 0 − 1 − 3 0 0 − 4 ] A=\begin{bmatrix} 1 & 1 & 2\\ 2 & 1 & 1 \\ 1 & 2 & 1 \\ \end{bmatrix} \\ \quad \\ \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ -1 & 0 & 1 \\ \end{bmatrix}A =\begin{bmatrix} 1 & 1 & 2\\ 2 & 1 & 1 \\ 0 & 1 & -1 \\ \end{bmatrix} \\ \quad \\ \begin{bmatrix} 1 & 0 & 0\\ -2 & 1 & 0 \\ 0& 0 & 1 \\ \end{bmatrix} \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ -1 & 0 & 1 \\ \end{bmatrix}A=\begin{bmatrix} 1 & 1 & 2\\ 0 & -1 & -3 \\ 0 & 1 & -1 \\ \end{bmatrix} \\ \quad \\ \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ 0& 1 & 1 \\ \end{bmatrix} \begin{bmatrix} 1 & 0 & 0\\ -2 & 1 & 0 \\ 0& 0 & 1 \\ \end{bmatrix} \begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ -1 & 0 & 1 \\ \end{bmatrix}A= \begin{bmatrix} 1 & 1 & 2\\ 0 & -1 & -3 \\ 0 & 0 & -4 \\ \end{bmatrix} A=⎣⎡​121​112​211​⎦⎤​⎣⎡​10−1​010​001​⎦⎤​A=⎣⎡​120​111​21−1​⎦⎤​⎣⎡​1−20​010​001​⎦⎤​⎣⎡​10−1​010​001​⎦⎤​A=⎣⎡​100​1−11​2−3−1​⎦⎤​⎣⎡​100​011​001​⎦⎤​⎣⎡​1−20​010​001​⎦⎤​⎣⎡​10−1​010​001​⎦⎤​A=⎣⎡​100​1−10​2−3−4​⎦⎤​ 可以看出， A A A经过几次行变换后，就化为了上三角矩阵，可记为： L 3 L 2 L 1 A = U A = L 1 − 1 L 2 − 1 L 3 − 1 U L_3L_2L_1A=U \\ \quad \\ A=L_1^{-1}L_2^{-1}L_3^{-1}U L3​L2​L1​A=UA=L1−1​L2−1​L3−1​U 于是， A A A就可以写成行变换矩阵乘积的逆与上三角矩阵的乘积了。行变换矩阵的逆还是行变换矩阵，因此行变换矩阵乘积的逆仍然是行变换矩阵，并且是下三角矩阵。

因此，LU分解实际上就是通过初等行变换将矩阵变为上三角矩阵，并将行变换的乘积取逆的过程。

分解的唯一性

如果矩阵 A A A可以进行LU分解，则可能分解出多种 L , U L,U L,U矩阵组合；但是如果 L L L是单位下三角矩阵，或 U U U是单位上三角矩阵，则LU分解的结果是唯一的。

唯一性的证明可以这么考虑：在高斯消元时，依次将每列在对角线上的元素考虑为主元，那么行变换就是固定的，则矩阵 L L L就是唯一的。

此外， L , U L,U L,U矩阵的对角线元素必然不为零，证明方法也很简单： A A A可逆， ∣ A ∣ = ∣ L ∣ ∣ U ∣ ≠ 0 |A|=|L||U|\ne 0 ∣A∣=∣L∣∣U∣​=0，则 ∣ L ∣ ≠ 0 , ∣ U ∣ ≠ 0 |L|\ne0,|U|\ne0 ∣L∣​=0,∣U∣​=0，则对角线必没有零元素。

复杂度

可以看出，将第一列化为主元列时，需要对每行(n)的每个元素(n)进行操作，n列都要化为主元列，则时间复杂度为 O ( n 3 ) O(n^3) O(n3)

PLU分解

上面的示例中，矩阵 A A A通过行变换进行分解，采用的是高斯消元的思想。然而，如果有这么一个可逆矩阵： A = [ 0 1 1 − 2 0 1 0 0 1 ] A=\begin{bmatrix} 0 & 1 & 1\\ -2 & 0 & 1 \\ 0& 0 & 1 \\ \end{bmatrix} A=⎣⎡​0−20​100​111​⎦⎤​ 按照上面所说， A A A可逆则可LU分解，然而在高斯消元时，默认第一列的主元值为0，这样就没法通过行增减变换消元了。这时候，需要使用行置换的方法，将第一列的主元换为-2。这就是PLU分解： A = P L U A=PLU A=PLU 其中，P是一个行置换矩阵（也是初等行变换），L是下三角矩阵，U是上三角矩阵。

具体的分解方法与LU分解非常类似，在此就不重复记录了。

PLU分解的稳定性明显优于LU分解，因此在实际中使用LU方法时，往往默认采用PLU矩阵分解。