高斯消元法

1. 高斯消元法概述

1.1 基本思想

高斯消元法（Gaussian Elimination）是求解线性方程组最基本的方法，通过初等行变换将增广矩阵化为行阶梯形或行最简形，从而求出方程组的解。

1.2 线性方程组的矩阵表示

线性方程组 $Ax = b$ 的增广矩阵为：

$(A | b) = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} & b_1 \\ a_{21} & a_{22} & \cdots & a_{2n} & b_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} & b_m \end{pmatrix}$

对增广矩阵施行初等行变换，不改变方程组的解集。

2. 行阶梯形矩阵

2.1 定义

矩阵称为行阶梯形（Row Echelon Form, REF），若满足：

1. 零行（元素全为零的行）位于矩阵底部
2. 每个非零行的首非零元（主元）的列标严格递增
3. 主元下方的元素全为零

示例：

$\begin{pmatrix} \boxed{2} & 3 & 1 & 4 \\ 0 & \boxed{1} & 2 & 5 \\ 0 & 0 & \boxed{3} & 6 \\ 0 & 0 & 0 & 0 \end{pmatrix}$

其中 $\boxed{}$ 标记的是主元。

2.2 行最简形矩阵

行阶梯形进一步满足：

1. 每个主元为 $1$
2. 每个主元所在列的其他元素全为 $0$

称为行最简形（Reduced Row Echelon Form, RREF）。

示例：

$\begin{pmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{pmatrix}$

3. 高斯消元法的步骤

3.1 前向消元（化为行阶梯形）

步骤：

1. 选取第一列中非零元素作为主元（若第一列全为零，则看第二列）
2. 若需要，交换行使主元位于第一行
3. 用主元消去其下方所有元素
4. 对右下角的子矩阵重复上述过程

示例：解方程组 $\begin{cases} x_1 + 2x_2 + x_3 = 2 \\ 2x_1 + 5x_2 + 3x_3 = 7 \\ x_1 + 3x_2 + 3x_3 = 5 \end{cases}$

增广矩阵：

$\begin{pmatrix} 1 & 2 & 1 & 2 \\ 2 & 5 & 3 & 7 \\ 1 & 3 & 3 & 5 \end{pmatrix}$

$\xrightarrow{r_2 - 2r_1, r_3 - r_1} \begin{pmatrix} 1 & 2 & 1 & 2 \\ 0 & 1 & 1 & 3 \\ 0 & 1 & 2 & 3 \end{pmatrix}$

$\xrightarrow{r_3 - r_2} \begin{pmatrix} 1 & 2 & 1 & 2 \\ 0 & 1 & 1 & 3 \\ 0 & 0 & 1 & 0 \end{pmatrix}$

3.2 回代过程

从最后一个非零行开始，逐步回代求出各未知量。

由行阶梯形：

$\begin{cases} x_1 + 2x_2 + x_3 = 2 \\ x_2 + x_3 = 3 \\ x_3 = 0 \end{cases}$

回代：$x_3 = 0$，$x_2 = 3 - 0 = 3$，$x_1 = 2 - 6 - 0 = -4$。

解为 $x_1 = -4, x_2 = 3, x_3 = 0$。

3.3 高斯-约当消元法（化为行最简形）

继续消元，将主元上方的元素也消为零：

$\begin{pmatrix} 1 & 2 & 1 & 2 \\ 0 & 1 & 1 & 3 \\ 0 & 0 & 1 & 0 \end{pmatrix} \xrightarrow{r_2 - r_3, r_1 - r_3} \begin{pmatrix} 1 & 2 & 0 & 2 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & 0 \end{pmatrix} \xrightarrow{r_1 - 2r_2} \begin{pmatrix} 1 & 0 & 0 & -4 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & 0 \end{pmatrix}$

直接读出解：$x_1 = -4, x_2 = 3, x_3 = 0$。

4. 主元选取策略

4.1 部分主元选取

在每一步消元中，选取当前列中绝对值最大的元素作为主元，交换行使之到达主元位置。

目的：减少舍入误差的传播，提高数值稳定性。

4.2 全主元选取

在剩余子矩阵中选取绝对值最大的元素作为主元，可能需要同时交换行和列。

优点：数值稳定性最好。

缺点：计算量增大，且列交换需要记录未知量的顺序。

4.3 主元选取的重要性

不选主元时，若主元非常小，消元过程中会产生大数，导致严重的舍入误差。

示例：

$\begin{cases} 0.001x_1 + x_2 = 1 \\ x_1 + x_2 = 2 \end{cases}$

不选主元：$r_2 - 1000r_1$，会产生大系数，增大误差。

选主元：交换两行后消元，数值更稳定。

5. 高斯消元法的计算量

5.1 时间复杂度

• 前向消元：$O(n^3/3)$ 次乘除法
• 回代过程：$O(n^2/2)$ 次乘除法
• 总计：$O(n^3)$

5.2 与克莱姆法则的比较

高斯消元法远比克莱姆法则高效。

6. 高斯消元法的程序实现思路

6.1 伪代码

for k = 1 to n-1:
    // 选主元
    找到第k列中 |a_{ik}| 最大的行 i_max (i >= k)
    交换第k行和第i_max行
    // 消元
    for i = k+1 to m:
        factor = a_{ik} / a_{kk}
        for j = k to n+1:
            a_{ij} = a_{ij} - factor * a_{kj}

6.2 注意事项

1. 主元为零或接近零时需要特殊处理
2. 浮点运算中要注意数值稳定性
3. 稀疏矩阵可以使用特殊存储格式加速