矩阵分解 矩阵分解（如
L U ~\mathbf{LU}~ LU 分解、
Q R \mathbf{QR}~ QR 分解等）可以将一个矩阵分解成若干具有特定结构（如上三角、下三角或正交矩阵）的矩阵，从而简化后续的计算。矩阵分解在某些计算任务中，尤其是在解线性方程组、求逆、特征值计算等场景下，通常比矩阵分块更高效。
1. 矩阵分解的概念 矩阵分解是将一个矩阵表示为多个矩阵乘积的方法。它对复杂的矩阵进行预处理，简化数据的计算和处理。在计算机科学中，矩阵分解是一项常用技术，通过将矩阵拆分为具有特定结构的部分，提高了矩阵运算的效率，特别适用于大规模数据处理和数值计算。请看下面的矩阵分解过程：
上面这种分解方式将矩阵 A ~\mathbf{A}~ A L o w e r t r i a n g u l a r m a t r i x ~\textcolor{red}{L}ower~triangular~matrix L o w er t r ian gu l a r ma t r i x L \mathbf{L}~ L U p p e r t r i a n g u l a r m a t r i x ~\textcolor{red}{U}pper~triangular~matrix U pp er t r ian gu l a r ma t r i x U \mathbf{U}~ U L U ~\mathbf{LU}~ LU 分解 。示例中的下三角矩阵 L ~\mathbf{L}~ L 1 ~1~ 1 单位下三角矩阵 ，满足这个条件的分解法就是标准的 L U ~\mathbf{LU}~ LU 分解算法 。在矩阵运算中，将原始矩阵转化为三角矩阵可以显著提升计算效率。
由于上三角矩阵
L ~\mathbf{L}~ L 和下三角矩阵
U ~\mathbf{U}~ U 的标准定义是基于方阵的，所以
L U ~\mathbf{LU}~ LU ，也就是
A ~\mathbf{A}~ A 必须是
n × n ~n\times n~ n × n 的方阵。对非方阵的分解，采用
Q R ~\mathbf{QR}~ QR 分解、 奇异值分解（
S V G \mathbf{SVG} SVG ） 等其他矩阵分解方法更为适合。
2. L U ~\mathbf{LU}~ LU L U ~\mathbf{LU}~ LU L U ~\mathbf{LU}~ LU
在实际的工业和科研应用中，
解线性方程组 是非常常见的任务，尤其是多个方程组共享相同的系数矩阵的情况。例如：
A x = b 1 , A x = b 2 , … , A x = b p \mathbf{Ax} = \mathbf{b}_1, \quad \mathbf{Ax} = \mathbf{b}_2, \quad \dots, \quad \mathbf{Ax} = \mathbf{b}_p Ax = b 1 , Ax = b 2 , … , Ax = b p 此时，矩阵
A ~\mathbf{A}~ A 是相同的，而向量(
b 1 , b 2 , … , b p ~\mathbf{b}_1,\mathbf{b}_2, \dots, \mathbf{b}_p~ b 1 , b 2 , … , b p ) 是不同的。传统方法是通过直接行列式或高斯消元法来求解每个方程组，但这种方法效率较低，特别是当方程组数量
p ~p~ p 较大时。通过
L U ~\mathbf{LU}~ LU 分解，可以将矩阵
A ~\mathbf{A}~ A 分解为两个简单的三角矩阵
L ~\mathbf{L}~ L 和
U ~\mathbf{U}~ U ，然后在第一次求解时进行一次分解，后续的方程组只需要基于这个分解进行较为简单的运算即可。这样，解每个方程组的效率大大提高。具体来说，
L U ~\mathbf{LU}~ LU 分解允许我们将方程组
A x = b ~\mathbf{Ax}=\mathbf{b}~ Ax = b 转化为两个更容易求解的方程组：
A x = ( L U ) x = L ( U x ) = b ⇒ L y = b , U x = y \begin{align*}\mathbf{Ax}=(\mathbf{LU})\mathbf{x} = \mathbf{L}(\mathbf{Ux})=\mathbf{b} \\[2ex] \Rightarrow \quad \mathbf{Ly}=\mathbf{b},\quad \mathbf{Ux} = \mathbf{y} \end{align*} Ax = ( LU ) x = L ( Ux ) = b ⇒ Ly = b , Ux = y 这两个方程组可以通过
前代 和
回代 来分别求解，复杂度远低于直接求解原方程组。请看下面案例：
首先，我们将矩阵
A ~\mathbf{A}~ A 分解为下三角矩阵
L ~\mathbf{L}~ L 和上三角矩阵
U ~\mathbf{U}~ U ，使得：
A = L U ~\mathbf{A}=\mathbf{LU}~ A = LU ，对于矩阵
A ~\mathbf{A}~ A ，通过
L U ~\mathbf{LU}~ LU 分解得到：
L = [ 1 0 0 2 1 0 3 3 1 ] , U = [ 2 3 1 0 1 0 0 0 2 ] \mathbf{L} = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 3 & 1 \end{bmatrix}, \quad \mathbf{U} = \begin{bmatrix} 2 & 3 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 2 \end{bmatrix} L = 1 2 3 0 1 3 0 0 1 , U = 2 0 0 3 1 0 1 0 2 我们要先求解方程
L y = b ~\mathbf{Ly}=\mathbf{b}~ Ly = b ，这是一个
前代 问题，因为
L ~L~ L 是下三角矩阵。方程形式如下：
[ 1 0 0 2 1 0 3 3 1 ] [ y 1 y 2 y 3 ] = [ 5 10 20 ] ⇒ y = [ 5 0 5 ] \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 3 & 3 & 1 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} = \begin{bmatrix} 5 \\ 10 \\ 20 \end{bmatrix}\quad \Rightarrow \quad \mathbf{y}=\begin{bmatrix} 5 \\ 0 \\ 5 \end{bmatrix} 1 2 3 0 1 3 0 0 1 y 1 y 2 y 3 = 5 10 20 ⇒ y = 5 0 5 求解方程
U x = y ~\mathbf{Ux}=y~ Ux = y ，这是一个
回代 问题，因为
U ~\mathbf{U}~ U 是上三角矩阵。方程形式如下：
[ 2 3 1 0 1 0 0 0 2 ] [ x 1 x 2 x 3 ] = [ 5 0 5 ] ⇒ x = [ 5 / 4 0 5 / 2 ] \begin{bmatrix} 2 & 3 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 5 \\ 0 \\ 5 \end{bmatrix}\quad \Rightarrow \quad \mathbf{x}=\begin{bmatrix}5/4 \\ 0 \\ 5/2 \end{bmatrix} 2 0 0 3 1 0 1 0 2 x 1 x 2 x 3 = 5 0 5 ⇒ x = 5/4 0 5/2 3. L U ~\mathbf{LU}~ LU L U \mathbf{LU}~ LU 分解可以通过初等行变换来实现。我们不断地对矩阵
A ~\mathbf{A}~ A 施加初等行变换（左乘初等矩阵）先得到上三角矩阵
U ~\mathbf{U}~ U ：
( E p … E 1 ) A = U (\mathbf{E}_p \dots \mathbf{E}_1)\mathbf{A}=\mathbf{U} ( E p … E 1 ) A = U 我们在上面的等式两边乘以初等矩阵乘积的逆，就可以分解出
L , U ~\mathbf{L},\mathbf{U}~ L , U ：
A = ( E p … E 1 ) − 1 U = L U \mathbf{A}=\textcolor{red}{(\mathbf{E}_p\dots \mathbf{E}_1)^{-1}}\mathbf{U}=\textcolor{red}{\mathbf{L}}\mathbf{U} A = ( E p … E 1 ) − 1 U = L U 请观察下面分解矩阵
A ~\mathbf{A}~ A 的过程：
观察上面的分解过程可以发现，对
A ~\mathbf{A}~ A 进行
L U ~\mathbf{LU}~ LU 分解时，我们只使用了
行倍加 变换
( row replacements ) ~(~\text{row replacements}~)~ ( row replacements ) ，这样做是为了保证
L U ~\mathbf{LU}~ LU 分解是
唯一的 。要满足只使用行倍加进行矩阵行化简的条件，我们就要保证在矩阵化简的过程中不能出现零主元（也就是矩阵
U ~\mathbf{U}~ U 的主元不能出现零），这种方法可以归类为
一般的 L U ~\mathbf{LU}~ LU 。
方阵
A ~\mathbf{A}~ A 可逆并不能保证它可以进行
L U ~\mathbf{LU}~ LU 分解，例如：
A = [ 0 1 1 0 ] ~\mathbf{A}=\begin{bmatrix}0&1\\1&0\end{bmatrix}~ A = [ 0 1 1 0 ] 可逆，但它不能进行
L U ~\mathbf{LU}~ LU 分解。
4. P L U ~\mathbf{PLU}~ PLU 在实际分解过程中，我们通常会遇到主元为零或过小导致无法继续进行分解、或产生数值不稳定的情况。这时，我们会使用到
行交换 ( row interchanges ) ~(~\textbf{row interchanges}~)~ ( row interchanges ) 来进行
L U ~\mathbf{LU}~ LU 分解，这种分解方式是
带行交换的 L U ~\mathbf{LU}~ LU 分解 。它的分解形式为：
A = P L U \mathbf{A}=\mathbf{PLU} A = PLU
，所以通常我们称这种分解法为
P L U ~\mathbf{PLU}~ PLU 分解，其中
P ~\mathbf{P}~ P 表示
置换矩阵 ( Permutation matrix ) ~(~\textbf{Permutation~matrix}~)~ ( Permutation matrix ) 。请观察下面的示例：
上面这个矩阵 A ~\mathbf{A}~ A 0 ~0~ 0 P L U ~\mathbf{PLU}~ PLU U ~\mathbf{U}~ U 0 ~0~ 0 P ~\mathbf{P}~ P L , U ~\mathbf{L},\mathbf{U}~ L , U
上面的这次分解中，我们选择不同的置换矩阵，得到了不同的分解结果。除非，我们固定主元选取的策略，例如每次总是选择绝对值最大的元素（对于相等的元素设置固定的选择规则）进行行交换，那么 P L U ~\mathbf{PLU}~ PLU P L U ~\mathbf{PLU}~ PLU P L U ~\mathbf{PLU}~ PLU
上面的分解过程是一般的 L U ~\mathbf{LU}~ LU P L U ~\mathbf{PLU}~ PLU P ~\mathbf{P}~ P A ~\mathbf{A}~ A L U ~\mathbf{LU} LU P L U \mathbf{PLU} PLU L U ~\mathbf{LU} LU P L U \mathbf{PLU}~ PLU L U ~\mathbf{LU} LU P L U \mathbf{PLU} PLU
5. L U ~\mathbf{LU}~ LU 解线性方程组
A x = b ~\mathbf{Ax}=\mathbf{b}~ Ax = b 的传统方法是高斯消元法，其计算复杂度大约
O ( n 3 ) ~O(n^3)~ O ( n 3 ) 。这意味着对于一个大小为
n × n ~n\times n~ n × n 的矩阵，计算量是随矩阵维度
n ~n~ n 的三次方增长的。这在处理大规模矩阵时会变得非常昂贵，尤其是当矩阵规模较大（如数千维度的矩阵）时，计算时间和资源消耗会急剧增加。
L U \mathbf{LU}~ LU 分解的
复杂度也是 O ( n 3 ) ~O(n^3)~ O ( n 3 )
，与高斯消元法相同，但一旦
L U ~\mathbf{LU}~ LU 分解完成，后续的多次求解只需
O ( n 2 ) ~O(n^2)~ O ( n 2 ) 的计算量。下面的图表可以直观展示两种不同算法的对比：
上面两张图表展示了当方程组的系数矩阵大小分别为 10 × 10 ~10\times 10~ 10 × 10 100 × 100 ~100\times 100~ 100 × 100 O ( p ⋅ n 3 ) ~O(p\cdot n^3)~ O ( p ⋅ n 3 ) L U ~\mathbf{LU}~ LU O ( n 3 ) + p ⋅ O ( n 2 ) ~O(n^3)+p\cdot O(n^2)~ O ( n 3 ) + p ⋅ O ( n 2 ) p ~p~ p n ~n~ n L U ~\mathbf{LU}~ LU
