第4课-a-的-lu-分解
Course: 线性代数 MIT 18.06 Linear Algebra Date: October 21, 2025 4:00 PM (GMT+8)
🎓 第4课 A 的 LU 分解
🎮 课程概览 · 本节目标
- 👤 主讲：吉尔伯特（MIT 18.06）
- 📝 本节主题：把高斯消元的步骤用矩阵因式分解表示，得到 (A=LU) 的结构；理解初等消去矩阵 (E)、下三角矩阵 (L)、上三角矩阵 (U)、以及置换矩阵 (P) 的角色；估算计算代价与多右端向量的优势。
- 🎯 学习目标：
- 看懂消元步骤如何对应一系列初等矩阵，及如何把它们合并成 (L) 与 (U)；
- 理解当不需行交换时 (A=LU) 的成立与构造方法；
- 认识置换矩阵 (P)（行交换）出现的情形以及 (PA=LU) 的常见形式；
- 估算作法的运算量（复杂度）与对多右端向量（多个 (b)）的益处。
📚 基本事实回顾（逆与转置的简短提醒）
🔁 乘积的逆：若 (A) 与 (B) 都可逆，则 ((AB)^{-1} = B^{-1} A^{-1})。顺序“反过来”。
🔄 转置与逆：((A^T)^{-1} = (A^{-1})^T)（转置与取逆可以按任意顺序进行，结果一致）。
（这些事实在后面推导 LU、消除矩阵与逆时会用到。）
🏛 消元矩阵（初等矩阵）与 (L,U) 的直观来源
🔧 每一步“用第 (i) 行消第 (j) 行的某列项”都等价于左乘一个初等消除矩阵 (E)。例如把第2行减去 4×第1行，对应：
[
E=\begin{pmatrix}1&0-4&1\end{pmatrix},\quad E\cdot A\ \text{就完成了对应的行操作}.
]
🔗 把消元的所有步骤按顺序表示为矩阵乘法：若做了 (k) 步消元，有若干初等矩阵 [E_1,E_2,\dots,E_k]，则
[
E_k\cdots E_2 E_1 A = U,
]
其中 (U) 是消元得到的上三角矩阵（或阶梯形）。
✅ 因为每个初等矩阵都可逆（逆矩阵很容易得到：把减法改为加法），我们可以把上式两边同时左乘这些逆矩阵的乘积，得到：
[
A = [E_1^{-1} E_2^{-1} \cdots E_k^{-1}], U.
]
把 [L:=E_1^{-1} E_2^{-1} \cdots E_k^{-1}]，于是得到经典分解
[
\boxed{A = L,U},
]
其中 (L) 是下三角（对角一般为 1）的矩阵，(U) 是上三角矩阵。
🧩 直接 2×2 示例（课堂演示，便于理解）
设
[
A=\begin{pmatrix}2 & 1[4pt]8 & 7\end{pmatrix}.
]
第一步：用第1行消去第2行的首项。倍数 (=8/2=4)。
执行：第2行 ← 第2行 − 4×第1行，得到上三角
[
U=\begin{pmatrix}2 & 1[4pt]0 & 3\end{pmatrix}.
]
那么对应的初等矩阵是 [E=\begin{pmatrix}1&0-4&1\end{pmatrix}]，满足 (E A = U)。
于是 (A = E^{-1} U)，而 [E^{-1}=\begin{pmatrix}1&0\4&1\end{pmatrix}]（把 −4 变为 +4）。定义 (L=E^{-1})，得到
[
A = L,U,\qquad L=\begin{pmatrix}1&0\4&1\end{pmatrix},\ U=\begin{pmatrix}2&1\0&3\end{pmatrix}.
]
✅ 这正是 LU 分解的标准构造：下三角 (L) 的下三角元素正好是消元时用到的倍数（乘数）。
⚙️ 为什么 (L) 的下三角就是消元乘数（直观）
- 当做消元时，你用第一行乘以某系数去减第二、第三行 —— 这些系数正是 (L) 的下三角元素（不含对角的 1）。
- 初等矩阵的逆把减法改回加法（符号反向），因此把这些逆矩阵连乘起来便得到 (L)。
- 重要：这个构造需要“在枢轴位置不为 0 的情况下且没有行交换”的简单情形；若需要交换行，则要引入置换矩阵 (P)（见下）。
🔁 含置换的通用形式（当出现行交换时）
在实际消元中，若枢轴为 0 或为数值不稳小值，常需做行交换（pivoting）。每次行交换也对应一个置换矩阵 (P)（单位矩阵的行重排）。
通常形式写作
[
P,A = L,U
]
或有时写成 (A = P^T L U)。置换矩阵保证每一步可以找到合适的（非零、稳定的）枢轴。
⚠️ 注意：行交换是乘在左边（左乘 (P)），而列交换则是乘在右边（右乘某个置换）。行与列操作不能随便互换顺序。
🔗 初等矩阵的逆很简单（符号翻转）
- 每个消元初等矩阵 (E)（如在第 j 行第 i 列放置 −m 以表示“减去 m×第 i 行”）都有显而易见的逆：把 −m 改成 +m（就是把减法改回加法）。因此构造 (L)（初等矩阵逆的连乘）很直接。
📦 LU 的优点（尤其对多个右端向量）
- 若要解 (A x = b) 且 (A = L U)，分两步解：
- 解 (L y = b)（向前替代，成本 [O(n^2)]）；
- 解 (U x = y)（向后替代，成本 [O(n^2)]）。
- 若有多个右端列（例如多个 (b)：矩阵 (B)），只需做一次 LU（约 [O(n^3)] 的成本），随后每个右端解成本约 [O(n^2)]。因此对多 RHS 场景非常划算。
⚡ 运算量（复杂度）估算 — 为什么是约 [\tfrac{1}{3}n^3]？
消元的核心工作是把第1列下面变为 0（约 [(n-1)\times n] 次乘加），然后第2列下面（约 [(n-2)\times n]），……，总计等价于求和
[
\sum_{k=1}^{n} k^2 \sim \frac{n^3}{3}\quad[\text{主阶项}],
]
因此总的乘加次数主阶为 [\displaystyle \tfrac{1}{3}n^3]。
精确讲：Gaussian elimination（不含 pivoting 的理想估算）主成本是 [\tfrac{1}{3}n^3 + O(n^2)]。
右端向量每一个 RHS 的额外成本约为 [O(n^2)]（前向+后向替代）。因此当有很多 RHS 时，先做 LU 再回代很划算。
🪂 数值实现须知（实务/鲁棒性）
- ✅ 若枢轴接近 0 或太小，需行交换（partial pivoting）以避免数值不稳定。实践中常用 partial pivoting（在当前列在下面行中选最大绝对值的元素与当前行交换）。
- ✅ 带置换的分解通常报告为 (PA=LU)（(P) 为置换矩阵）。实际软件（MATLAB/NumPy）返回 (L,U,P) 或以其他相容格式给出。
- ✅ 当矩阵奇异或近奇异时（行列式为 0 或接近 0），LU 分解会失败或产生数值不准的结果。
🔎 小结（将课堂要点浓缩）
- 📌 高斯消元的每一步对应一个初等矩阵 (E)。这些 (E) 的逆连乘给出 (L)，消元结果就是 (U)。因此（无行交换时）(A=LU)。
- 📌 若有必要进行行交换，则使用置换矩阵 (P)，一般写作 (PA=LU)。
- 📌 LU 的实际价值：一次分解（约 [\tfrac{1}{3}n^3]）+ 每个右端向量 [O(n^2)]；适合解多个 RHS。
- 📌 初等矩阵可逆且逆易得； (L) 的下三角元素恰为消元时的乘数（倍数），对理解与实现非常直观。
📝 推荐练习（可直接放在 Notion 复习卡）
- 🔁 练习 1：按课堂 2×2 示例（[A=\begin{pmatrix}2&1\8&7\end{pmatrix}]）手算并写出对应的 (E, E^{-1}, L, U)。验证 (A=LU)。
- 🔁 练习 2：用增广矩阵形式做一次有行交换的 3×3 消元，记录置换矩阵 (P)，验证 (PA=LU)。
- 🔁 练习 3：编程（MATLAB/NumPy）实现简单 LU 分解（不带 pivot），并与内置
lu或numpy.linalg.lu（含 pivot）比较结果与误差。 - 🔁 练习 4：估算并比较直接用高斯（每个 RHS 重新消元）与先 LU 再回代在多个 RHS 下的总运算量（以 (n) 和 (m)（RHS 个数）表示）。