高斯消元与线性方程组

线性方程组 $Ax=b$ 是线性代数的原点问题。高斯消元用「行变换把矩阵化成上三角」求解，而消元过程的副产品——一组记录变换的下三角矩阵——正是LU 分解的来源。

消元流程

对增广矩阵 $[A|b]$ 做三种行变换（交换两行、某行乘非零常数、某行加另一行的倍数），化成行阶梯形：

1. 选第一列主元，消去下方各行
2. 右下子块递归进行，得 $U$（上三角）
3. 回代：从最后一行向上解出 $x$

复杂度 $O(n^3)$。主元为零则换行；列主元法（每步选该列绝对值最大的元素做主元）顺带抑制舍入误差放大，是数值稳定性的标准做法。

消元的矩阵语言

每次消元 = 左乘一个初等下三角矩阵 $L_i$：

$$L_k\cdots L_{1}A=U⟹A=LU$$

消元不是一次性算法，而是因子分解——解一次 $Ax=b$ 花 $O(n^3)$，但拿到 $LU$ 后，新右端 $b^{\prime }$ 只需两次三角回代（$O(n^2)$）。这正是LU 分解的存在理由。

解的存在与结构

判定全看矩阵的秩：

| $\mathrm{rank}(A)$ vs $\mathrm{rank}([A|b])$ | 解 | |---|---| | 相等且 $=n$ | 唯一解 | | 相等且 $<n$ | 通解 = 特解 + 零空间，自由变量 $n-r$ 个 | | 前者小 | 无解，$b\notin \mathrm{col}(A)$——求最优近似转伪逆与最小二乘 |

克拉默法则（$x_i=\det A_i/\det A$，见行列式）理论上漂亮，计算上 $O(n!)$，只作理解工具。

相关笔记

• LU 分解 — 消元的矩阵化沉淀
• 矩阵的秩 — 解结构判据
• 行列式 — 主元之积；克拉默法则的理论角色