线性代数04：矩阵LU分解

上一篇文章我们深入讨论了矩阵乘法和逆矩阵，今天我们来学习矩阵LU分解。这是线性代数中非常重要的一种矩阵分解方式，在数值计算和工程应用中被广泛使用。

通过前面文章的学习，我们知道高斯消元法的本质就是对矩阵进行一系列初等行变换。而LU分解就是把这些初等行变换用矩阵乘法的形式优雅地表示出来。

知识概要

本文会涵盖以下内容：

  • 逆矩阵和转置矩阵的重要性质
  • 从消元矩阵的角度理解LU分解
  • LU分解的计算方法和优越性
  • 置换矩阵的概念和性质

逆矩阵与转置的性质补充

在进入LU分解的正题之前，我们先补充两个关于逆矩阵的重要性质，这对后面的推导很有帮助。

乘积的逆矩阵

第一个问题：如果矩阵 $A$ 和 $B$ 都是可逆方阵，那么它们的乘积 $AB$ 的逆矩阵是什么？

我们从逆矩阵的定义出发，要求 $(AB)^{-1}$ 满足：

我们来试一下 $B^{-1}A^{-1}$，看看它是否满足条件：

完美！因此我们得到结论：

这个规律可以推广到多个矩阵相乘：乘积的逆等于逆的逆序乘积。

转置与逆的关系

接下来我们介绍转置矩阵，然后看看转置和逆之间有什么关系。

转置矩阵就是将原矩阵的各行转换为各列所得到的新矩阵，记为 $A^T$。例如：

我们已经知道 $AA^{-1} = I$，现在对等式两边同时做转置运算。根据转置的运算法则，$(AB)^T = B^T A^T$，所以：

这个等式告诉我们什么呢？既然 $(A^{-1})^T$ 乘以 $A^T$ 等于单位矩阵，根据逆矩阵的定义，$(A^{-1})^T$ 就是 $A^T$ 的逆矩阵！

因此我们得到非常重要的关系式：

💡 核心结论：对于可逆方阵，转置和取逆两个运算的顺序可以互换。

矩阵的LU分解

现在我们进入正题——LU分解。我们都熟悉高斯消元法通过初等行变换将矩阵化为上三角形式。而LU分解的思想就是：把所有的消元步骤用矩阵乘法表示出来。

从消元矩阵到LU分解

回顾一下，每一步初等行变换都等价于左乘一个消元矩阵。假设我们从可逆矩阵 $A$ 出发，通过一系列初等行变换将其变为上三角矩阵 $U$，那么整个过程可以写成：

这里 $E_1, E_2$ 等等都是消元矩阵。由于消元矩阵都是可逆的，我们可以把它们都逆过去得到：

这就是 $A = LU$ 分解！其中：

  • $L$ 是下三角矩阵（lower triangular）
  • $U$ 是上三角矩阵（upper triangular）

所以说，LU分解本质上就是把高斯消元的过程用矩阵乘法重新表达了一遍。

一个具体的例子

我们通过一个例题来理解L矩阵有什么特别的性质。假设我们已经有：

已知：

$E_{31} = I$，求 $A = LU$ 分解后的 $L$。

思路：

  1. 我们有 $E{32}E{21}A = U$，两边同时左乘 $(E{32}E{21})^{-1}$ 得到：

    所以 $L = E{21}^{-1}E{32}^{-1}$

  2. 求逆矩阵：

    注意：这里逆矩阵和原矩阵的区别仅仅是消元乘数符号相反。

  3. 计算 $L$：

看到了吗？一个非常神奇的现象发生了！消元乘数 $2$ 和 $5$ 正好出现在L矩阵对应的位置，丝毫不差。

✨ 这就是LU分解最大的优点：我们不需要真的去计算一系列矩阵的逆和乘积，只需要把消元过程中得到的乘数直接放到L矩阵对应的位置就可以了！

这个结论告诉我们一个非常简便的构造方法：

在LU分解中，L矩阵记录了消元过程中所有的乘数信息。消元时用了多少倍数消去某个位置，L矩阵就在那个位置放上那个倍数。

LU分解的计算流程

我们用流程图总结一下LU分解的完整过程：

LU分解的意义

为什么我们需要LU分解呢？它直接求解线性方程组 $Ax = b$ 有什么优势？

当我们把 $A$ 分解为 $A = LU$ 后，原方程组 $Ax = b$ 变为：

我们令 $y = Ux$，那么可以分两步求解：

  1. 先解 $Ly = b$ —— $L$ 是下三角矩阵，用前代法很容易求解
  2. 再解 $Ux = y$ —— $U$ 是上三角矩阵，用回代法很容易求解

相比于直接对增广矩阵 $[A | b]$ 做消元，LU分解的优势在于：如果我们需要对同一个矩阵A求解多个不同的右端项b，那么只需要做一次LU分解，之后每次只需要前代+回代即可，大大减少计算量。

这在工程实践中非常有用，比如在迭代法求解非线性问题时，每次迭代只更新右端项，这时LU分解的优势就体现出来了。

消元的运算量估计

我们来估计一下，对一个 $n \times n$ 的满矩阵进行LU分解，需要多少次运算？

我们从第一列开始：

  • 第一列消元完成后，需要处理的矩阵从 $n \times n$ 变为 $(n-1) \times (n-1)$
  • 这一步大约需要 $n^2$ 次运算

以此类推，总的运算量大约是：

对于大的 $n$，我们可以用积分近似求和：

所以对 $n$ 阶矩阵做LU分解，运算量大约是 $\boxed{\frac{1}{3}n^3}$ 次浮点运算。记住这个结果，我们后面讨论矩阵数值计算的时候还会用到。

置换矩阵

我们之前提到过，在高斯消元过程中，如果主元位置是0，我们需要交换两行。这个行交换操作对应的矩阵就是置换矩阵。

什么是置换矩阵

置换矩阵就是将单位矩阵 $I$ 的各行重新排列后得到的矩阵。左乘一个置换矩阵的效果就是交换矩阵的行。

我们来看一个例子：对于 $3 \times 3$ 的单位矩阵，所有可能的置换矩阵有哪些？

一共有 $3! = 6$ 个置换矩阵：

这6个矩阵构成了一个很有意思的集合：任取两个置换矩阵相乘，结果仍然是这个集合中的某个置换矩阵，它们形成了一个置换群。

置换矩阵的重要性质

置换矩阵有一个非常优美的性质：

置换矩阵的逆等于它的转置：$P^{-1} = P^T$

换句话说，置换矩阵都是正交矩阵。为什么会这样呢？我们可以直观理解：置换矩阵P是把单位矩阵的行重新排列，那么 $P^T P$ 正好是计算各行的内积，结果必然还是单位矩阵。所以 $P^T P = I$，说明 $P^{-1} = P^T$。

推广到一般情况：

  • $n$ 阶置换矩阵一共有 $n!$ 个（n的阶乘个）
  • 每一个置换矩阵的逆都等于它的转置

当我们需要选主元的时候，实际上就是在做行交换，行交换等价于左乘一个置换矩阵P。因此更完整的LU分解应该写成：

这里 $P$ 记录了我们所有的行交换操作。这就是选主元的LU分解。

笔者感悟

作为一名IC设计工程师，我发现LU分解在工程中的应用比我想象的要广泛得多：

  • 电路仿真：在SPICE电路仿真中，我们需要反复求解线性方程组来更新节点电压，系数矩阵A变化很慢，只需要更新右端项b，这时预先做好LU分解可以大大提高仿真速度。
  • 控制理论：在状态空间方法中，系统的可控性和可观测性判断涉及到矩阵分解，LU分解是很多更复杂分解的基础。
  • 信号处理：在滤波器设计和信号重建中，很多迭代算法每一步都需要解线性方程组，LU分解是基础操作。
  • 芯片设计中的物理分析：在电源网格分析中，需要求解大规模线性方程组，利用稀疏矩阵的LU分解可以高效得到解。

有意思的是，在实际工程中我们很少对满矩阵做LU分解。大部分工程问题产生的矩阵都是稀疏矩阵（大部分元素是0），专门针对稀疏矩阵优化的LU分解算法在EDA工具中至关重要，直接决定了芯片仿真的速度。

Gilbert Strang教授在这门课中从消元矩阵引入LU分解的思路非常巧妙，它让你明白LU分解不是什么神秘的新东西，就是我们天天在用的高斯消元的矩阵表示而已。这种”把过程结果化”的思想在数学中很常见——把一系列操作打包成一次矩阵乘法，这给后续理论分析带来了极大方便。

总结

本文要点回顾：

概念 核心结论
乘积的逆 $(AB)^{-1} = B^{-1}A^{-1}$，逆序相乘
转置与逆 $(A^T)^{-1} = (A^{-1})^T$，转置和取逆可以交换顺序
LU分解定义 $A = LU$，L是下三角矩阵（对角线全1），U是上三角矩阵
L矩阵构造 L矩阵记录了所有消元乘数，消元时用了多少乘数，直接放到对应位置
求解方程组 $Ax=b \to Ly=b$（前代）$\to Ux=y$（回代）
运算量估计 $n$阶矩阵LU分解大约需要 $\frac{1}{3}n^3$ 次浮点运算
置换矩阵 由单位矩阵交换行得到，满足 $P^{-1} = P^T$
带主元LU分解 $PA = LU$，P记录了所有行交换

最后放一张学习笔记留作纪念：

matrix_lu_xmind