Lecture 4: Factorization into A = LU

目录 · ← l3 · l5 →

Lecture 4: Factorization into A = LU

概述

上一讲我们学会了用高斯消元（Gaussian elimination）把矩阵 $A$ 变成上三角矩阵 $U$。本讲要把这个过程本身写成一个恒等式：$A = LU$。这是整个 18.06 里第一个真正意义上的矩阵分解，也是后面所有分解（$A=QR$、$A=S\Lambda S^{-1}$、$A=U\Sigma V^{\mathsf T}$）的模板。

核心问题是：消元做了这么多行变换，能不能把它们”打包”成一次乘法？答案是能，而且打包出来的下三角矩阵 $L$ 有个惊人的性质——它的非对角元素就是我们一路用掉的消元乘数（multipliers），不需要额外计算。本讲大部分篇幅就是在讲清楚”为什么不需要额外计算”，以及当必须换行时公式如何变成 $PA = LU$。

位置：讲次 1-5 构成”消元与分解”单元。这一讲把讲次 2 的算法升级为代数结构，为讲次 6-10 的四个基本子空间铺路（$U$ 的行阶梯形直接给出秩与主元列）。

核心概念的几何直觉

消元矩阵（elimination matrix）$E_{ij}$

• 定义与目的：$E_{ij} = I - \ell_{ij}\,\mathbf{e}i\mathbf{e}_j^{\mathsf T}$，左乘 $A$ 的作用是”把第 $i$ 行的 $\ell{ij}$ 倍从第 $j$ 行中减去”。它是单位矩阵被改了一个元素。（这里 $\mathbf{e}_i$ 是第 $i$ 个标准基向量，$\mathbf{e}_i\mathbf{e}_j^{\mathsf T}$ 是只在 $(i,j)$ 位置为 1 的矩阵。）
• 几何直觉（它在空间中是什么样子？）：$E_{21}$ 是一个剪切变换（shear）。它把一个正方形沿水平方向”推斜”，体积不变（对角元素全为 1，行列式为 1）。它的逆 $E_{21}^{-1} = I + \ell_{21}\mathbf{e}_2\mathbf{e}_1^{\mathsf T}$ 就是反方向的剪切——把减掉的加回来，因此只有符号翻转。
• 具体示例：$\ell_{21}=\tfrac12$ 时 \(E_{21}=\begin{bmatrix}1&0&0\\-\tfrac12&1&0\\0&0&1\end{bmatrix},\qquad E_{21}^{-1}=\begin{bmatrix}1&0&0\\\tfrac12&1&0\\0&0&1\end{bmatrix}.\)

下三角矩阵 $L$（lower triangular with unit diagonal）

• 定义与目的：$L=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}$，是把消元”倒着撤销”的结果。$L$ 的对角线全是 1，非对角元素就是乘数 $\ell_{ij}$。
• 几何直觉：$L$ 是一台”造回来“的机器。$U$ 是被消元压扁后的骨架，$L$ 负责把被剪掉的部分一片片贴回去，还原出 $A$。乘数 $\ell_{ij}$ 衡量”第 $i$ 行里掺了多少第 $j$ 行的成分”，所以 $L$ 的元素天然记录行与行之间的依赖份额。
• 具体示例：见下方示例二，$L=\begin{bmatrix}1&0&0\\ \tfrac12&1&0\\ 0&\tfrac23&1\end{bmatrix}$。

上三角矩阵 $U$（row echelon form）

• 定义与目的：$U$ 是消元的终点，主元（pivots）落在对角线上。
• 几何直觉：$U$ 是阶梯形，它把方程组变成”从最后一行往上逐层可解”。$U$ 的对角线就是主元序列，$U$ 的零行数 = 自由度个数。
• 具体示例：$\det A=\det L\cdot\det U=1\cdot(d_1d_2d_3)$，所以主元乘积等于行列式。

为什么 $L$ 的乘法顺序是”逆序”

这是本讲最容易被忽略的一点。消元从左到右执行：

要解出 $A$，必须从右往左依次乘逆矩阵：

注意逆序：最后做的 $E_{32}$ 的逆最先出现在 $L$ 里。这不是巧合，而是”撤销一个动作序列要按相反顺序”的必然结果——就像穿衣服要先穿袜子再穿鞋，脱的时候必须先脱鞋。

置换矩阵 $P$（本讲只是登场，讲次 5 详论）

• 定义与目的：每行每列恰有一个 1 的方阵。它表示”换行”这一操作，使得即使 $a_{11}=0$ 也能继续消元。
• 几何直觉：$P$ 是坐标轴的重排（可能带镜像），它不拉伸也不旋转——保持长度 $\vert P\mathbf x\vert =\vert \mathbf x\vert $。所以 $P$ 属于正交矩阵家族。
• 具体示例：交换 1、3 两行的 $P_{13}=\begin{bmatrix}0&0&1\\0&1&0\\1&0&0\end{bmatrix}$，满足 $P_{13}^{\mathsf T}=P_{13}=P_{13}^{-1}$。

分解的”尺寸账本”（为什么 $A=LU$ 不浪费信息）

$A$ 有 $n^2$ 个数。$L$（单位对角）有 $n(n-1)/2$ 个自由数（严格下三角），$U$ 的上三角有 $n(n+1)/2$ 个。合计

刚好等于 $n^2$——这就是 $A=LU$ 能够”无损”存储 $A$ 的算术理由。相比之下，如果把 $L$ 的对角线也当成未知（一般下三角矩阵），参数就变成 $n(n+1)/2+n(n+1)/2=n^2+n$，比 $A$ 多出 $n$ 个自由度；正是”$L$ 对角恒为 1”这条约定消掉了这 $n$ 个多余参数，使分解唯一。这解释了下面”关键要点”中的唯一性：约束数刚好等于多出的自由度。

“为什么可以假定 $L$ 对角为 1”——消元从不缩放行

高斯消元只用一种操作：把一行的倍数从另一行减去（$R_i\leftarrow R_i-\ell R_j$）。这种操作从不乘除某一行本身，所以它保留了两条性质：(a) 每一行的”缩放因子”不变，因此可以约定 $L$ 的对角为 1；(b) 行列式不变，因此 $\det U=\det A$。如果我们允许”把一行乘 3”这种操作，$L$ 的对角就会出现 3，而 $\det$ 也要相应记录缩放因子——这就是为什么教科书的 $LU$ 总是约定 $L$ 单位对角：它对应”只用最干净的那一类行操作”。 同理，如果消元过程中必须”行与行交换”，我们就不能把这个操作吸收进三角矩阵（交换会破坏三角结构），只能单独拿出来记成 $P$——这就是 $A=LU$ 与 $PA=LU$ 的分野。

计算步骤与手算演示

先看全景图：$A=LU$ 的结构长什么样

在动手之前，先用一张 ASCII 图把”分解在做什么”钉在脑子里：

                    A          =        L        *        U
              (n x n, 稠密)        (单位下三角)      (上三角)

   [ x x x x x ]              [ 1 . . . . ]     [ d1 x x x x ]
   [ x x x x x ]              [ l 1 . . . ]     [ .  d2 x x x ]
   [ x x x x x ]      =       [ l l 1 . . ]  *  [ .  .  d3 x x ]
   [ x x x x x ]              [ l l l 1 . ]     [ .  .  .  d4 x ]
   [ x x x x x ]              [ l l l l 1 ]     [ .  .  .  .  d5]

   右上角全乱，              "x" 的位置 =        "x" 的位置 =
   要 n^2 个数存储            消元乘数(抄来的)     消元后的剩余元素

  关键: L 的对角线恒为 1  ->  存储 L 只要 n(n-1)/2 个数
        U 的上三角           ->  存储 U 只要 n(n+1)/2 个数
        两者合计 = n^2       ->  和 A 一样多，不浪费也不丢失

  消元过程的"一个位置一个位置"填格:
    step 1: 用 d1 消掉第 1 列下方的 l21,l31,l41,...  -> L 第 1 列填好
    step 2: 用 d2 消掉第 2 列下方的 l32,l42,...      -> L 第 2 列填好
    ...
    step n-1: 只剩 d_n 和最后一格                        -> U 完工

示例一：2×2 热身（先把乘数抄写规则看一遍）

取 $A=\begin{bmatrix}2&1\\6&4\end{bmatrix}$。

乘数 $\ell_{21}=\dfrac{a_{21}}{a_{11}}=\dfrac{6}{2}=3$。消元 $R_2\leftarrow R_2-3R_1$：

于是

$\det A=2\cdot1=2$（与 $2\cdot4-1\cdot6=2$ 一致 ✓）。

【计算机制解说】：这个 $2\times2$ 例子把”抄乘数”讲得最清楚。$A$ 的第 2 行 $(6,4)$ 可以写成”$3\times$ 第 1 行 $+$ 新的第 2 行”：$3(2,1)+(0,1)=(6,4)$ ✓。这正是 $L$ 的第 2 行 $\begin{bmatrix}3&1\end{bmatrix}$ 乘 $U$ 的结果。乘数 3 不是算出来的新东西，它就是 $6/2$——我们为了消元本来就要算 $6/2$，现在顺手把它写进 $L$ 而已。这就是”$L$ 免计算”的最朴素形态。

示例二：对称三对角矩阵的 $A=LU$（乘数 $\tfrac12,\tfrac23$）

取

这是 $1$ 维 Laplace 算子（弦振动、热传导）的离散版本，是全书最重要的矩阵之一。

步骤 1：写出增广形式，准备消元。

初始状态（同时记录乘数）：
[  2   1   0 ]   <- 主元行 1，主元 d1 = 2
[  1   2   1 ]   <- 要消掉 (2,1) 的 1
[  0   1   2 ]

步骤 2：消去 $(2,1)$ 位置。 乘数

执行 $R_2 \leftarrow R_2 - \tfrac12 R_1$：

R2: [ 1  2  1 ] - (1/2)*[ 2  1  0 ]
  = [ 1  2  1 ] - [ 1  0.5  0 ]
  = [ 0  1.5  1 ]

[  2    1    0 ]
[  0    1.5  1 ]
[  0    1    2 ]

步骤 3：消去 $(3,2)$ 位置。 此时 $(3,1)$ 已经是 0，跳过。乘数

执行 $R_3 \leftarrow R_3 - \tfrac23 R_2$：

R3: [ 0  1  2 ] - (2/3)*[ 0  1.5  1 ]
  = [ 0  1  2 ] - [ 0  1  0.6667 ]
  = [ 0  0  1.3333 ]

U = [  2    1     0   ]
    [  0   1.5    1   ]
    [  0    0   4/3    ]

步骤 4：写出 $L$。 把乘数直接填入单位下三角矩阵：

步骤 5：验证 $LU=A$。 逐元素算：

• 第 1 行：$1\cdot(2,1,0)=(2,1,0)$ ✓
• 第 2 行：$\tfrac12\cdot(2,1,0)+1\cdot(0,\tfrac32,1)=(1,\tfrac12,0)+(0,\tfrac32,1)=(1,2,1)$ ✓
• 第 3 行：$0\cdot(2,1,0)+\tfrac23\cdot(0,\tfrac32,1)+1\cdot(0,0,\tfrac43)=(0,1,\tfrac23)+(0,0,\tfrac43)=(0,1,2)$ ✓

【计算机制解说】：为什么 $L$ 的元素恰好等于乘数、不需要任何计算？关键在于 $L$ 的每一行都是一个”配方”。$A$ 的第 $i$ 行可以写成 $U$ 的前 $i$ 行的线性组合，而组合系数正是消元时从上面各行”借”来的倍数。消元时第 2 行被改成 $R_2-\ell_{21}R_1$，等价于原始 $R_2 = \ell_{21}R_1 + (\text{新}R_2)$。所以原始行 = 乘数 × 上层 $U$ 行 + 当前 $U$ 行——这恰好就是 $A = LU$ 的第 $i$ 行展开式。乘数在消元时被”用掉”的位置，正好就是它在 $L$ 中该出现的位置。这就是本讲的核心洞察：$L$ 不是被算出来的，是被抄下来的。

示例三：为什么 $L$ 比 $E$ 好（”垃圾元素”问题）

用同一组乘数，我们把三个消元矩阵和三个逆矩阵都写出来对照。

先按消元顺序把它们乘起来（这正是 $U=E_{32}E_{31}E_{21}A$ 左边的样子）：

注意 $(3,1)$ 位置冒出来了 $\tfrac13$！这个 $\tfrac13=\ell_{32}\ell_{21}=\tfrac23\cdot\tfrac12$ 是”消元顺序”产生的副产品，它既不是 $\ell_{31}$（本来是 0），也不是任何有意义的乘数——这就是 Strang 说的 “垃圾元素”（junk）。

再按逆序乘逆矩阵（这正是 $L$ 的样子）：

干干净净，$\tfrac13$ 消失了。

【计算机制解说】：用标准基写出来就一目了然。记 $E_{21}=I-\ell_{21}\mathbf{e}2\mathbf{e}_1^{\mathsf T}$，$E{32}=I-\ell_{32}\mathbf{e}_3\mathbf{e}_2^{\mathsf T}$。

消元顺序（$E_{32}E_{21}$）：

因为 $\mathbf{e}_2^{\mathsf T}\mathbf{e}_2=1$，交叉项存活下来，往 $(3,1)$ 塞进了 $\tfrac13$。

逆序（$E_{21}^{-1}E_{32}^{-1}$）：

交叉项死掉了，因为不同下标的基向量正交（$\mathbf{e}_1^{\mathsf T}\mathbf{e}_3=0$）。于是 $L$ 里只剩纯乘数，位置互不干扰。一句话：逆序相乘让交叉项自动湮灭，所以 $L$ 是”免计算”的。

示例四：需要换行时的 $PA=LU$

取

第一个主元 $a_{11}=0$，消元立刻卡住。必须换行。

步骤 1：选主元并置换。 第 1 列最大的元素在第 3 行（值 4），把第 1 行与第 3 行互换。置换矩阵

（$P$ 的每行每列恰有一个 1。注意 $P^{\mathsf T}=P=P^{-1}$，因为交换两次就回来了。）

步骤 2：消去 $(2,1)$。

$(3,1)$ 本来就是 0，所以 $\ell_{31}=0$。

[  4    1     8  ]
[  0   0.5   -1  ]     <- 新第 2 行
[  0    2     1  ]

步骤 3：消去 $(3,2)$。 乘数

步骤 4：组装 $L$ 并验证。

行分解验证：第 2 行 $\tfrac12(4,1,8)+(0,\tfrac12,-1)=(2,\tfrac12,4)+(0,\tfrac12,-1)=(2,1,3)$ ✓；第 3 行 $0\cdot R_1+4(0,\tfrac12,-1)+(0,0,5)=(0,2,-4)+(0,0,5)=(0,2,1)$ ✓。

【计算机制解说】：置换矩阵是”行的搬运工“。$P$ 左乘 $A$ 就是按 $P$ 中 1 的位置重排 $A$ 的行：$P$ 的第 $i$ 行在第 $j$ 列为 1，则 $(PA)$ 的第 $i$ 行 = $A$ 的第 $j$ 行。所以 $PA=LU$ 的含义是：先把行摆到正确位置，再做干净的 $LU$ 分解。为什么要换行？因为 $a_{11}=0$ 时 $\ell_{21}=a_{21}/a_{11}$ 会除以 0。换行的另一个（更重要的）理由是数值稳定性：选绝对值最大的主元可以把乘数压到 $\vert \ell\vert \le 1$，误差不被放大。这就是”部分选主元（partial pivoting）”。另外注意 $\det P=-1$，所以 $\det(PA)=-\det A$：上面 $A$ 的行列式是 $-10$，而 $\det(PA)=\det L\det U=1\cdot(4\cdot\tfrac12\cdot5)=10$，符号正好翻过来。

示例五：把模式推广到 4×4——主元与乘数的规律

示例二的对称三对角矩阵不是偶然。取更大的同型矩阵

按同样的流程消元（每一步只消正下方的一个元素，因为三对角结构不会被破坏）：

第 1 步: l21 = 1/2  ->  第2行变成 [0, 3/2, 1, 0]
第 2 步: l32 = 1/(3/2) = 2/3  ->  第3行变成 [0, 0, 4/3, 1]
第 3 步: l43 = 1/(4/3) = 3/4  ->  第4行变成 [0, 0, 0, 5/4]

乘数:  l21 = 1/2,  l32 = 2/3,  l43 = 3/4
主元:  d1 = 2,     d2 = 3/2,   d3 = 4/3,   d4 = 5/4
        (规律: d_k = (k+1)/k,  乘数 l_{k+1,k} = k/(k+1))

逐元素验证 $LU=A_4$ 的部分：

• 第 1 行：$1\cdot(2,1,0,0)=(2,1,0,0)$ ✓
• 第 2 行：$\tfrac12(2,1,0,0)+(0,\tfrac32,1,0)=(1,\tfrac12,0,0)+(0,\tfrac32,1,0)=(1,2,1,0)$ ✓
• 第 3 行：$\tfrac23(0,\tfrac32,1,0)+(0,0,\tfrac43,1)=(0,1,\tfrac23,0)+(0,0,\tfrac43,1)=(0,1,2,1)$ ✓
• 第 4 行：$\tfrac34(0,0,\tfrac43,1)+(0,0,0,\tfrac54)=(0,0,1,\tfrac34)+(0,0,0,\tfrac54)=(0,0,1,2)$ ✓

$\det A_4=d_1d_2d_3d_4=2\cdot\tfrac32\cdot\tfrac43\cdot\tfrac54=5$。由于 $A_4$ 对称，同样有 $U=DL^{\mathsf T}$：

【计算机制解说】：这个例子展示了消元在稀疏结构上的传播现象。三对角矩阵消元后仍然是三对角（填入（fill-in）只发生在原有带宽内），所以乘数只在次对角线上，$L$ 也是三对角。主元序列 $2,\tfrac32,\tfrac43,\tfrac54,\dots$ 单调递减趋向 1，永远为正——这正是 $A$（三对角、对角占优）正定的数值证据（讲次 25 会证明：全部主元 $d_k>0\iff$ 对称正定）。规律 $d_k=\frac{k+1}{k}$ 可以这样推：$d_{k+1}=2-\ell_{k+1,k}\cdot 1=2-\frac{1}{d_k}$，代入 $d_1=2$ 得 $d_2=2-\tfrac12=\tfrac32$，$d_3=2-\tfrac23=\tfrac43$ ✓——这是一个递推，每个主元只依赖前一个，所以计算量是 $O(n)$ 而不是 $O(n^3)$！稀疏矩阵的 $LU$ 之所以是工业核心（结构力学、电路、PDE 求解），根源就在这里。另外注意 $\det A_4=5$ 与 $n=3$ 时的 $\det A_3=4$ 相比，序列 $2,3,4,5$（对应 $n=1,2,3,4$）是 $n+1$——这是三对角 Toeplitz 行列式的经典结果。

示例六：一次分解、多次回代（分解的实用价值）

对示例二的 $A$，假设我们要解三个不同的右端项：$\mathbf b_1=(1,2,3)$、$\mathbf b_2=(6,0,0)$、$\mathbf b_3=(0,0,7)$。

步骤 1：前代 $L\mathbf c=\mathbf b$（forward substitution）。

$L$ 是单位下三角，从第 1 行往下解：

• $\mathbf b_1$：$c_1=1$；$\tfrac12c_1+c_2=2\Rightarrow c_2=2-\tfrac12=\tfrac32$；$\tfrac23c_2+c_3=3\Rightarrow c_3=3-1=2$。得 $\mathbf c_1=(1,\tfrac32,2)$。
• $\mathbf b_2$：$c_1=6$；$3+c_2=0\Rightarrow c_2=-3$；$\tfrac23(-3)+c_3=0\Rightarrow c_3=2$。得 $\mathbf c_2=(6,-3,2)$。
• $\mathbf b_3$：$c_1=0$；$0+c_2=0\Rightarrow c_2=0$；$0+c_3=7\Rightarrow c_3=7$。得 $\mathbf c_3=(0,0,7)$。

一般公式：$c_i=b_i-\sum_{j<i}\ell_{ij}c_j$。

步骤 2：回代 $U\mathbf x=\mathbf c$（back substitution）。

从最后一行往上解：

• $\mathbf c_1=(1,\tfrac32,2)$：$\tfrac43x_3=2\Rightarrow x_3=\tfrac32$；$\tfrac32x_2+x_3=\tfrac32\Rightarrow \tfrac32x_2=0\Rightarrow x_2=0$；$2x_1+x_2=1\Rightarrow x_1=\tfrac12$。

  \[\mathbf x_1=\left(\tfrac12,\ 0,\ \tfrac32\right),\qquad A\mathbf x_1=(2\cdot\tfrac12+0,\ \tfrac12+0+\tfrac32,\ 0+\tfrac32)=(1,2,3)=\mathbf b_1. \checkmark\]

• $\mathbf c_2=(6,-3,2)$：$\tfrac43x_3=2\Rightarrow x_3=\tfrac32$；$\tfrac32x_2+\tfrac32=-3\Rightarrow x_2=-3$；$2x_1+x_2=6\Rightarrow x_1=\tfrac92$。

  \[\mathbf x_2=\left(\tfrac92,\ -3,\ \tfrac32\right),\qquad A\mathbf x_2=(9-3,\ \tfrac92-6+\tfrac32,\ -3+\tfrac32)=(6,0,0)=\mathbf b_2. \checkmark\]

• $\mathbf c_3=(0,0,7)$：$\tfrac43x_3=7\Rightarrow x_3=\tfrac{21}{4}$；$\tfrac32x_2+\tfrac{21}{4}=0\Rightarrow x_2=-\tfrac72$；$2x_1+x_2=0\Rightarrow x_1=\tfrac74$。

  \[\mathbf x_3=\left(\tfrac74,\ -\tfrac72,\ \tfrac{21}{4}\right),\qquad A\mathbf x_3=\left(\tfrac72-\tfrac72,\ \tfrac74-7+\tfrac{21}{4},\ -\tfrac72+\tfrac{21}{2}\right)=(0,0,7)=\mathbf b_3. \checkmark\]

【计算机制解说】：注意 $L$ 与 $U$ 只算了一次，三个 $\mathbf b$ 各自只花了两次三角回代。这就是分解的全部卖点。”前代+回代”为什么快？因为三角系统的每一行只含一个新未知量，所以每个 $x_i$ 只需一次除法，前面已求出的分量直接代入。复杂度上：消元阶段对 $n\times n$ 矩阵约需

而每次三角回代约需 $n^2/2$ 次乘法，两次合起来 $\approx n^2$。当 $n=1000$ 时这是 $3.3\times 10^8$ 对 $10^6$ ——差三百多倍。工程上（有限元、结构分析、电路仿真）矩阵固定而右端项不断变化，$LU$ 分解是标准做法。反过来说：如果只解一个 $\mathbf b$，何必分解？因为分解还给出行列式（$\det A=\prod d_i$）、秩、主元列，这些副产品本身就值这个价。

汇总对比：同一组乘数，$E$ 与 $L$ 的信息含量

              消元过程的三条"信息通道"对比（以 A=[[2,1,0],[1,2,1],[0,1,2]] 为例）

  通道              具体矩阵                      元素含义            可否直接用?
  ------------------------------------------------------------------------------
  E 顺序连乘   E32*E21 = [ 1    0   0 ]      (3,1) = l32*l21       否
                         [-1/2  1   0 ]        = 1/3 "垃圾"
                         [ 1/3 -2/3 1 ]       (2,1) = -l21
                                              (3,2) = -l32
  ------------------------------------------------------------------------------
  L 逆序连乘   E21^-1 E32^-1 = [ 1    0  0 ]  (2,1) = l21 = 1/2    是（免计算）
                             [ 1/2  1  0 ]   (3,2) = l32 = 2/3
                             [ 0   2/3 1 ]   (3,1) = 0 干净
  ------------------------------------------------------------------------------
  U 单独存放   U = [ 2   1    0 ]           对角 = 主元 d_i      是
                   [ 0  3/2   1 ]          上三角 = 剩余
                   [ 0   0   4/3]           零行数 = 自由度
  ------------------------------------------------------------------------------

  结论: L 是"消元过程的压缩包"——信息量与 E 的连乘积相同,
        但表示形式让乘数保持原样、互不污染。这就是为什么要
        定义 L 而不是直接用 E。

注意 $E_{32}E_{21}$ 与 $L$ 的信息量完全相同（都是”$A=(\cdot)U$”的合法表示），差别只在表示形式：$L$ 用一个位置存一个乘数，$E$ 的连乘积把乘数混在一起（$\tfrac13$ 是 $\tfrac23\cdot\tfrac12$ 的产物）。这就像同一个数用分数 $\tfrac23$ 表示还是用小数 $0.666\ldots$ 表示——前者保留了”它是 $2/3$”的结构信息，后者丢了。$L$ 保留了结构，所以它对后续计算（回代、$LDL^{\mathsf T}$、Cholesky）都友好。

矩阵分解的核心思想

本讲引入 $A=LU$（必要时 $PA=LU$），这是课程中第一种也是最基本的分解。

形式：$A$ 被拆成”结构简单的两块”。$L$ 的对角线全是 1，$U$ 的下三角全是 0，两者一共只有约 $n^2$ 个自由参数（而 $A$ 有 $n^2$ 个），剩下的约束来自”$L$ 单位对角”这一选定。

含义（揭示的结构性质）：

1. 乘数即 $L$：$L$ 编码了 $A$ 各行之间的依赖关系，且是消元过程的无损耗记录。
2. $\det A=\det U=\prod_i d_i$：行列式就是主元之积（$L$ 的行列式为 1）。这给出了行列式的算法定义，不用余子式展开。
3. $U$ 直接读出秩与主元列：$U$ 的非零行数就是 $\operatorname{rank}(A)$。
4. 唯一性：若 $A$ 可逆且不需要换行，$A=LU$（$L$ 单位对角）是唯一的。证明：设 $L_1U_1=L_2U_2$，则 $L_2^{-1}L_1=U_2U_1^{-1}$，左边是单位下三角、右边是上三角，同时成立的只有 $I$，故 $L_1=L_2$，$U_1=U_2$。

5. 对称特例 $A=LDL^{\mathsf T}$：若 $A=A^{\mathsf T}$ 且不需要换行，则 $U$ 与 $L$ 不是独立的：$U=DL^{\mathsf T}$，其中 $D=\operatorname{diag}(d_1,\dots,d_n)$ 是主元对角阵。于是

   \[A=L\,D\,L^{\mathsf T}.\]

   对本讲的 $A$，$D=\operatorname{diag}\!\left(2,\ \tfrac32,\ \tfrac43\right)$，且 $\tfrac32=2-\tfrac12\cdot1$、$\tfrac43=2-\tfrac23\cdot1$ 正好是”对角元素减去乘数乘上层元素”。这个形式在讲次 25（对称正定矩阵）会成为判据：$A$ 正定 $\iff$ 所有 $d_i>0$。

应用价值：一次 $O(n^3)$ 分解 → 每个新右端项只需 $O(n^2)$；同时免费得到 $\det$、秩、主元、以及对称情形的正定性判据。这是”分解思想”的第一次胜利：把难题变成若干个简单问题的复合。

代价的精确账本与盈亏平衡点

把”$n^3/3$ 对 $n^2$”这句口号算成具体数字：

                 消元/分解            一次前代+回代        比值
  n       n^3/3 (乘法数)          ~ n^2 (乘法数)       elim/sub
  ---------------------------------------------------------------
   3            9                     9                 1.0
  10          333                   100                 3.3
 100      333,333                10,000                33
1000  333,333,333             1,000,000               333

 盈亏平衡: 解 k 个右端项的"分解法"总代价 = n^3/3 + k*n^2
           不用分解、每次重新消元        = k * n^3/3
           令两者相等:
              n^3/3 + k*n^2 = k*n^3/3
           两边除以 n^2:
              n/3 + k = k*n/3
           移项:
              n/3 = k*(n/3 - 1) = k*(n-3)/3
           解得:
              k* = n / (n-3)          <- 只需 2 个右端项左右就划算

 最大加速比 (k -> 无穷):  speedup -> (n^3/3) / n^2 = n/3

 结论: n=1000 时，只要右端项 k >= 2，分解法就已经划算；
       右端项很多时，加速比趋于 n/3 ~= 333 倍。

注意上表口径：表中按”$n^3/3$ 与 $n^2$”的量级估算。若用精确计数，对 $n\times n$ 矩阵，消元阶段实际乘法数（只算 $R_i\leftarrow R_i-\ell R_j$ 的乘，不含除法）是

$n=3$ 时得 $5$（而非 $9$）；一次三角回代是 $\sum_{k=1}^{n}k=n(n+1)/2\approx n^2/2$，两次就是 $n^2$。所以”$n^3/3$ 与 $n^2$”是量级而非精确等式，但量级正是工程上唯一关心的。盈亏平衡的结论（$k^*=n/(n-3)\approx 2$，加速比上限 $n/3$）用精确常数重算后量级不变。

【计算机制解说】：为什么消元是 $n^3$ 而回代只有 $n^2$？因为它们的嵌套层数不同。消元是一个双重循环（外层选主元列，内层更新一块 $(n-k)\times(n-k)$ 的子矩阵），循环体里做乘加 → 代价 $n^3$。回代是单个循环（每行只解一个新未知量），代价 $n^2$。换句话说：分解要把矩阵”看很多遍”，而回代只”扫一遍”。这也解释了为什么稀疏矩阵的技术重点是保住 $L,U$ 的稀疏性：如果消元产生大量 fill-in，$n^3$ 的常数会爆炸。工程上求解大规模 PDE 时，重排未知量顺序（等价于选一个置换 $P$，即 $PAP^{\mathsf T}$）来最小化 fill-in，是比选主元更重要的优化。

补充演示：秩亏情形下 $LU$ 会发生什么

取

步骤 1：先直接消元，看会发生什么。 $\ell_{21}=\tfrac21=2$、$\ell_{31}=\tfrac11=1$：

\(R_2\leftarrow R_2-2R_1:\ (2,4,6)-(2,4,6)=(0,0,0),\) \(R_3\leftarrow R_3-1R_1:\ (1,1,1)-(1,2,3)=(0,-1,-2).\)

[ 1   2   3 ]
[ 0   0   0 ]   <- 第 2 行整行变成 0！主元位置是 0
[ 0  -1  -2 ]

步骤 2：主元为 0，必须换行。 交换第 2、3 行（$P$ 为交换 2、3 的置换矩阵）后重新消元。注意此时要对 $PA$ 消元：

新的乘数：$\ell_{21}=\tfrac11=1$、$\ell_{31}=\tfrac21=2$。

\(R_2\leftarrow R_2-1R_1:\ (1,1,1)-(1,2,3)=(0,-1,-2),\) \(R_3\leftarrow R_3-2R_1:\ (2,4,6)-(2,4,6)=(0,0,0).\)

步骤 3：写出 $L$ 并验证 $LU=PA$。 $\ell_{32}=\tfrac{0}{-1}=0$（第 3 行第 2 列已经是 0，无需再消）：

$U$ 的最后一行为零 ⇔ $A$ 奇异（$U$ 只有 2 个非零主元，$n-r=3-2=1$ 个自由度）。

【计算机制解说】：秩亏时 $LU$ 分解依然可以进行，只是 $U$ 会出现零行，主元个数少于 $n$。这给出一个极其实用的判据：$A$ 可逆 $\iff$ $U$ 的所有主元非零（没有零行）。注意本例中换行是必需的：$A$ 的 $(2,2)$ 在第一次消元后就变成了 0，若不交换第 2、3 行，第 2 列就没有可用的主元。这也说明”$A$ 奇异”与”需要换行”是两件独立的事：奇异可能不需要换行（如 $A=\begin{bmatrix}1&1\\1&1\end{bmatrix}$），需要换行也可能矩阵可逆（如示例四）。另外，$L$ 不受影响——它只记录”我们做了哪些行减行”，即使某一行变成零行，$L$ 依然单位下三角，且 $\ell_{32}=0$ 如实记录了”这一步没做事”。

这也说明$A=LU$ 不需要 $A$ 可逆：可逆性只影响 $U$ 是否可逆，$U$ 出现零行时 $A$ 就不可逆，但分解式 $PA=LU$ 仍然成立。$\det A=(\det P)\prod_{i=1}^{n}d_i=0$ 自动报出奇异性——这是 $LU$ 免费附赠的”可逆性测试”，比算行列式的余子式展开（$O(n!)$）快得多。最后注意一个细节：换行会改变乘数。本例对 $A$ 直接消元得到 $(\ell_{21},\ell_{31})=(2,1)$，而对 $PA$ 消元得到 $(1,2)$——两套乘数不同，$L$ 也不同。所以记录 $L$ 时必须明确”是对哪个矩阵消元得到的”，这正是 $PA=LU$ 中”$L$ 属于 $PA$”这句话的含义。

与其他讲次的关联

• 讲次 2（消元）：本讲把那里的逐步行操作升格为矩阵恒等式。消元的三个”合法操作”中，只有”行减去另一行的倍数”进入 $E$；换行进入 $P$。
• 讲次 3（矩阵乘法/逆）：$E_{ij}^{-1}$ 只需符号翻转（因为 $E_{ij}=I-\ell\mathbf e_i\mathbf e_j^{\mathsf T}$ 是幂零扰动，$(I-N)^{-1}=I+N$），本讲大量使用。
• 讲次 5（转置/置换）：$PA=LU$ 里的 $P$ 是置换矩阵，其性质 $P^{-1}=P^{\mathsf T}$ 下一讲证明；$LDL^{\mathsf T}$ 直接用到转置。
• 讲次 6-10（四个基本子空间）：$U$ 的主元直接给出 $\operatorname{rank}(A)$、主元列、以及 $N(A)$ 的自由变量结构。没有 $LU$，就没有求零空间的系统算法。
• 讲次 18-20（行列式）：$\det A=\prod d_i$ 与 $\det P=\pm1$ 会与”体积”解释汇合；$P$ 的符号就是置换的奇偶性。
• 讲次 25（对称正定）：$A=LDL^{\mathsf T}$ → $A=R^{\mathsf T}R$（Cholesky），是 $LU$ 在对称正定情形的进化版。
• 讲次 16（最小二乘）：正规方程 $A^{\mathsf T}A\mathbf x=A^{\mathsf T}\mathbf b$ 要用 Cholesky/LU 求解，正是”一次分解、多次回代”的工业级应用。

关键要点

1. 消元即分解：$E_{32}E_{31}E_{21}A=U\ \Longrightarrow\ A=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}U=LU$。乘逆矩阵必须倒序。
2. $L$ 免计算法则：$L$ 的对角线全为 1，非对角元素 $\ell_{ij}$ 就是消元时用掉的乘数 $a_{ij}^{(j)}/d_j$，直接抄下即可。原因是 $E_{21}^{-1}E_{32}^{-1}$ 的交叉项因 $\mathbf e_1^{\mathsf T}\mathbf e_3=0$ 而湮灭，而 $E_{32}E_{21}$ 的交叉项存活（产生垃圾 $\ell_{32}\ell_{21}$）。所以永远不要写 $A=E^{-1}U$ 的连乘积形态，要用 $L$。
3. 需要换行时：$A=LU$ 升级为 $PA=LU$，$P$ 是置换矩阵（每行每列恰一个 1），$P^{-1}=P^{\mathsf T}$。$\det P=\pm1$，$\det(PA)=\det L\det U=\prod d_i$。
4. 代价对比：分解 $\approx n^3/3$ 次乘法；每个右端项的回代 $\approx n^2$ 次。一次分解、多次回代是 $LU$ 的存在理由。
5. 对称情形：$A=A^{\mathsf T}$（不需换行）$\Rightarrow A=LDL^{\mathsf T}$，$U=DL^{\mathsf T}$；且 $\det A=\prod d_i$，正定 $\iff$ 全部 $d_i>0$。

常见误区与注意事项

1. 把 $L$ 写成 $E$ 的连乘积。 常见错误：$A=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}U$ 写成 $A=E_{21}^{-1}E_{32}^{-1}E_{31}^{-1}U$（顺序照抄）。逆矩阵的顺序必须完全反过来。另一种错误是把 $L$ 写成 $E_{21}E_{31}E_{32}$（忘了取逆），那样会得到符号相反的乘数并混入垃圾项。
2. 以为换行后还是 $A=LU$。 一旦用了 $P$，等式左边是 $PA$ 而不是 $A$。若坚持写 $A$，应写成 $A=P^{\mathsf T}LU$（因为 $P^{-1}=P^{\mathsf T}$）。并且 $L$ 是对 $PA$ 做消元得到的 $L$，不是对 $A$。
3. 忘记 $L$ 的对角线是 1。 消元从不改变对角线的”单位”性质（我们只做行减行，不缩放行），所以 $L_{ii}=1$ 永远成立。若你算出的 $L$ 对角线不是 1，一定是把某个缩放步骤误当成消元了。
4. 乘数顺序错位。 $\ell_{32}$ 是”消去 $(3,2)$ 时用的倍数”，即（当时的）$a_{32}/a_{22}$，用的是更新后的元素（本例 $\tfrac{2}{3}=1/1.5$），不是原矩阵的 $\tfrac11=1$。这是最常算错的一步。
5. 把 $U$ 和 $A$ 的行阶梯形混淆。 $U$ 必须是消元后的最终上三角；如果中途停下或做了列交换，就不再是 $U$（列交换会引入右侧置换，需要 $PAQ=LU$，本课程不展开）。
6. 误以为 $LU$ 总能做。 若某个主元位置为 0 且其下方也全为 0，则 $A$ 奇异，$U$ 会出现零行，$L$ 仍然存在但 $U$ 不可逆——此时仍可写 $PA=LU$，只是 $A$ 不可逆。

思考题（带答案）

Q1.（纯计算） 对 $A=\begin{bmatrix}1&2&1\\2&5&3\\1&3&4\end{bmatrix}$ 求 $A=LU$，并验证 $LU=A$、计算 $\det A$。（提示：$\ell_{21}=2$，$\ell_{31}=1$。）

Q2.（概念） 消元矩阵满足 $E_{32}E_{21}=\begin{bmatrix}1&0&0\\-\ell_{21}&1&0\\ \ell_{32}\ell_{21}&-\ell_{32}&1\end{bmatrix}$ 而 $E_{21}^{-1}E_{32}^{-1}=\begin{bmatrix}1&0&0\\ \ell_{21}&1&0\\0&\ell_{32}&1\end{bmatrix}$。请解释为什么前者出现乘积项 $\ell_{32}\ell_{21}$ 而后者没有，并说明这与”$L$ 免计算”的关系。

Q3.（计算 + 应用） 已知 $A=\begin{bmatrix}2&1&0\\1&2&1\\0&1&2\end{bmatrix}=LU$（示例二），求 $A^{-1}$ 的第一列。