消元 = 分解
消元法不仅是求解工具，更是把矩阵分解为 \(L\) 和 \(U\) 的过程。\(L\) 记录"怎么消"，\(U\) 记录"消成什么"。
18.06 · 第 4 课
消元法的最终形态不是上三角矩阵 \(U\)，而是把原矩阵 \(A\) 分解为下三角矩阵 \(L\) 和上三角矩阵 \(U\) 的乘积。LU 分解把"如何做消元"和"消元的结果是什么"清晰地分开，是数值线性代数中最重要的矩阵分解之一。
回顾第 2 课的消元过程。每一步消元对应一个初等矩阵：
\[ E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ -\frac32 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix},\; E_{31} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1 \end{bmatrix},\; E_{32} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -4 & 1 \end{bmatrix}. \]消元的最终结果是上三角矩阵 \(U\)：
\[ E_{32} E_{31} E_{21} A = U = \begin{bmatrix} 2 & 1 & -1 \\ 0 & \frac12 & \frac12 \\ 0 & 0 & -1 \end{bmatrix}. \]把等式两边左乘这些初等矩阵的逆：
\[ A = (E_{21}^{-1} E_{31}^{-1} E_{32}^{-1}) U = LU. \]关键在于：每个消元矩阵的逆只是把乘子的符号翻转。例如
\[ E_{21}^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ \frac32 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}. \]把这些逆矩阵相乘，得到下三角矩阵 \(L\)：
\[ L = \begin{bmatrix} 1 & 0 & 0 \\ \frac32 & 1 & 0 \\ 1 & 4 & 1 \end{bmatrix}. \]\(L\) 的结构极其简单。 \(L\) 的对角线全是 1，位置 \((i,j)\)（其中 \(i>j\)）上的元素恰好是消元时使用的乘子 \(l_{ij}\)。不需要矩阵乘法就能写出 \(L\)——直接从消元过程中读取。
验证：
\[ LU = \begin{bmatrix} 1 & 0 & 0 \\ \frac32 & 1 & 0 \\ 1 & 4 & 1 \end{bmatrix} \begin{bmatrix} 2 & 1 & -1 \\ 0 & \frac12 & \frac12 \\ 0 & 0 & -1 \end{bmatrix} = \begin{bmatrix} 2 & 1 & -1 \\ -3 & -1 & 2 \\ -2 & 1 & 2 \end{bmatrix} = A. \]假设我们需要对同一个矩阵 \(A\) 求解多个不同右端向量 \(\mathbf{b}_1, \mathbf{b}_2, \dots\) 的方程组。消元法对每个 \(\mathbf{b}\) 都要重复整个消元过程——这很浪费。
有了 \(A = LU\)，求解 \(A\mathbf{x} = \mathbf{b}\) 分两步：
分解 \(A=LU\) 只做一次（\(\sim \frac23 n^3\) 运算），之后每个新 \(\mathbf{b}\) 只需前代和回代（\(\sim 2n^2\) 运算）。当 \(n\) 很大且 \(\mathbf{b}\) 很多时，节省显著。
当消元需要行交换时，标准 LU 分解不再适用。行交换可以用置换矩阵 (permutation matrix) \(P\) 表示——把行交换移到最左边：
\[ PA = LU. \]置换矩阵 \(P\) 是把单位矩阵的行重新排列得到的矩阵。它满足 \(P^{-1} = P^T\)（第 5 课会证明）。
把 \(U\) 的对角线元素（主元）单独提出来，得到对角矩阵 \(D\)：
\[ U = D \cdot U' \]其中 \(D = \operatorname{diag}(d_1, d_2, \dots, d_n)\) 包含主元，\(U'\) 是对角线全为 1 的上三角矩阵。于是
\[ A = L D U', \]其中 \(L\) 和 \(U'\) 的对角线都是 1。这种分解称为LDU 分解，对称性更好。
主元不能为零。 如果某个主元为零且无法通过行交换补救，LU 分解不存在（矩阵奇异）。数值计算中，即使主元非零但很小，也会导致严重的舍入误差，因此需要选主元 (pivoting) 策略。
\(A=LU\) 分解的运算量约为 \(\frac23 n^3\)，与消元相同。前代和回代的运算量约为 \(2n^2\)。对于单个 \(\mathbf{b}\)，LU 并不比直接消元快；但对于多个 \(\mathbf{b}\)，分解一次、多次使用前代/回代，优势明显。
问题 1： 在 \(A = LU\) 分解中，矩阵 \(L\) 的对角线元素是：
问题 2： 利用 \(A = LU\) 求解 \(A\mathbf{x} = \mathbf{b}\) 的正确步骤是：
问题 3： 对 \(n\times n\) 矩阵做 LU 分解的运算量约为：
问题 4： 当消元需要行交换时，标准分解形式变为：
消元法不仅是求解工具，更是把矩阵分解为 \(L\) 和 \(U\) 的过程。\(L\) 记录"怎么消"，\(U\) 记录"消成什么"。
\(L\) 的对角线是 1，下三角位置直接是消元乘子。无需矩阵乘法，直接从消元过程读取。
对多个右端向量，\(A=LU\) 只需做一次，之后每个新 \(\mathbf{b}\) 只需前代和回代，运算量从 \(\frac23 n^3\) 降到 \(2n^2\)。
\(PA=LU\) 处理行交换；LDU 分解把主元单独提出，对称性更好。这些变形在实际计算中都有其用武之地。
lecture_slides/lecture_04.pdflecture_summaries/lecture_1_4_summary.pdf