2.1 高斯消去与列主元

对应教材 2.1.1–2.1.2、定理 2.1–2.2、例 1；对应老师第 3 讲 §一、§四、§五。 本节把“会算”推进到“知道什么时候不能算”：顺序消去的充要条件、列主元为什么必要、计算量怎么估。

2.1.0 先修：矩阵范数与可逆性判据（老师第 3 讲 §一–§二）

老师在第 3 讲先用矩阵范数给出一个“不算行列式”的可逆性判据：

• $\lVert A\rVert_1=\max_j\sum_i\lvert a_{ij}\rvert$（最大列和），$\lVert A\rVert_\infty=\max_i\sum_j\lvert a_{ij}\rvert$（最大行和）；
• 若存在某个矩阵范数使 $\lVert A\rVert\lt1$，则 $I\pm A$ 可逆，且 $$\lVert(I-A)^{-1}\rVert\le\frac{1}{1-\lVert A\rVert}.$$

证明是反证：若 $(I-A)x=0$ 有 $x\ne0$，则 $\lVert x\rVert=\lVert Ax\rVert\le\lVert A\rVert\lVert x\rVert\lt\lVert x\rVert$，矛盾。这条判据是第 2.4 节迭代法收敛性的钥匙；本节先记住“找一个范数即可，不必碰行列式”。

2.1.1 顺序 Gauss 消去

对方程组 $A\boldsymbol x=\boldsymbol b$，令增广矩阵 $[A,\boldsymbol b]$。第 $k$ 步用第 $k$ 行消去下面各行的第 $k$ 列：

$$m_{ik}=\frac{a_{ik}^{(k)}}{a_{kk}^{(k)}},\qquad a_{ij}^{(k+1)}=a_{ij}^{(k)}-m_{ik}a_{kj}^{(k)},\qquad b_i^{(k+1)}=b_i^{(k)}-m_{ik}b_k^{(k)}$$

（$i=k+1,\dots,n$，$j=k+1,\dots,n$）。消元完成后回代：

$$x_i=\frac{b_i^{(i)}-\sum_{j=i+1}^n a_{ij}^{(i)}x_j}{a_{ii}^{(i)}},\qquad i=n,n-1,\dots,1.$$

计算量：消元约 $\frac{n^3}{3}$ 次乘除法，回代约 $\frac{n^2}{2}$ 次；主导项是 $O(n^3)$。这就是为什么大规模问题要利用结构（见 2.2.3–2.2.4）或改用迭代法（见 2.4）。

定理 2.1（顺序消去的充要条件）：顺序 Gauss 消去的前 $n-1$ 个主元素 $a_{kk}^{(k)}\ (k=1,\dots,n-1)$ 均不为零，当且仅当 $A$ 的前 $n-1$ 个顺序主子式

$$D_k=\begin{vmatrix} a_{11}&\cdots&a_{1k}\ \vdots&&\vdots\ a_{k1}&\cdots&a_{kk} \end{vmatrix}\ne0,\qquad k=1,\dots,n-1.$$

证明要点：消元不改变顺序主子式（行变换 $R_i\leftarrow R_i-m_{ik}R_k$ 把第 $k$ 行倍数减到第 $i$ 行，主子式不变）。消到第 $k$ 步时，$D_k=a_{11}^{(1)}a_{22}^{(2)}\cdots a_{kk}^{(k)}$；故 $D_k\ne0\iff$ 前 $k$ 个主元全不为零。取 $k=n-1$ 即得。$\blacksquare$

例 1（教材 2.1，四位十进制）：教材用 $$\begin{cases} 0.012x_1+0.010x_2+0.167x_3=0.6781,\ 1.000x_1+0.8334x_2+5.910x_3=12.10,\ 3200x_1+1200x_2+4.200x_3=981.0 \end{cases}$$ 说明：顺序消去时第一个主元 $0.012$ 很小，乘数 $m_{21}\approx83.3$、$m_{31}\approx2.7\times10^5$，舍入误差被剧烈放大，四位十进制下结果不可信；改用列主元后，先把绝对值最大的 $3200$ 换到主元位，乘数被控制住，结果可靠。这个例子不是“算错”，而是算法不稳定。

2.1.2 列主元素 Gauss 消去

第 $k$ 步先在当前第 $k$ 列的第 $k,\dots,n$ 行中选绝对值最大者：

$$i_k=\arg\max_{k\le i\le n}\lvert a_{ik}^{(k)}\rvert,$$

交换第 $k$ 行与第 $i_k$ 行（增广列一起换），再做消元。这样所有乘数满足 $\lvert m_{ik}\rvert\le1$，避免“小主元当分母”。

定理 2.2：若 $A$ 非奇异，则列主元 Gauss 消去的各个列主元素 $a_{kk}^{(k)}\ (k=1,\dots,n-1)$ 均不为零。

证明要点：反设某个 $r$ 处列主元为零，则当前第 $r$ 列从第 $r$ 行往下全为零；由行列式按列展开（或行交换不改变非奇异性）推出 $\det A=0$，与 $A$ 非奇异矛盾。$\blacksquare$

算法（列主元）：

1. 对 $k=1,\dots,n-1$：选 $i_k$，交换行；对 $i=k+1,\dots,n$ 算 $m_{ik}$ 并更新第 $i$ 行。
2. 回代。

计算量与顺序消去同阶（$O(n^3)$），但数值稳定性好得多；代价是每步一次列扫描和行交换。列主元不是可选项，是默认动作——尤其当主元可能很小时。

2.1.3 例题与数值实验

例 2.1.1（顺序 vs 列主元）：取 $$A=\begin{pmatrix}10^{-3}&1\1&1\end{pmatrix},\qquad \boldsymbol b=\begin{pmatrix}1\2\end{pmatrix}.$$ 精确解约为 $(0.9990,1.0010)^{\mathrm T}$。

• 顺序消去：$m_{21}=10^3$，第二步主元 $1-10^3\approx-999$，在三位有效数字下右端变成 $2-10^3$，回代得到严重失真的解；
• 列主元：先交换两行，主元为 $1$，乘数 $10^{-3}$，三步得到 $(1.00,1.00)^{\mathrm T}$。

实验建议：用 NumPy 的 float32 复现：顺序消去与 np.linalg.solve（内部列主元）对比，观察误差量级；再换 float64 看误差是否被压住。结论不是“float64 更好”，而是算法不稳定性不会因为多几位精度就消失。

2.1.4 习题（教材习题 1–3）