高斯消元法

1. 高斯消元法概述

1.1 基本思想

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

1.2 线性方程组的矩阵表示

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

$(A|b)=\left(\begin{array}{ccccc}{a}_{11}& a_{12}& \cdots & a_{1n}& b_1\\ a_{21}& a_{22}& \cdots & a_{2n}& b_2\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}& b_m\end{array}\right)$

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

2. 行阶梯形矩阵

2.1 定义

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

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

示例：

$\left(\begin{array}{cccc}\boxed{2}& 3& 1& 4\\ 0& \boxed{1}& 2& 5\\ 0& 0& \boxed{3}& 6\\ 0& 0& 0& 0\end{array}\right)$

其中 ​ 标记的是主元。

2.2 行最简形矩阵

行阶梯形进一步满足：

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

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

示例：

$\left(\begin{array}{cccc}1& 0& 0& 1\\ 0& 1& 0& 1\\ 0& 0& 1& 2\\ 0& 0& 0& 0\end{array}\right)$

3. 高斯消元法的步骤

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

步骤：

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

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

增广矩阵：

$\left(\begin{array}{cccc}1& 2& 1& 2\\ 2& 5& 3& 7\\ 1& 3& 3& 5\end{array}\right)$

$\stackrel{r_2-2r_1,r_3-r_1}{\to }\left(\begin{array}{cccc}1& 2& 1& 2\\ 0& 1& 1& 3\\ 0& 1& 2& 3\end{array}\right)$

$\stackrel{r_3-r_2}{\to }\left(\begin{array}{cccc}1& 2& 1& 2\\ 0& 1& 1& 3\\ 0& 0& 1& 0\end{array}\right)$

3.2 回代过程

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

由行阶梯形：

$\{\begin{array}{l}{x}_1+2x_2+x_3=2\\ x_2+x_3=3\\ x_3=0\end{array}$

回代：$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 高斯-约当消元法（化为行最简形）

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

$\left(\begin{array}{cccc}1& 2& 1& 2\\ 0& 1& 1& 3\\ 0& 0& 1& 0\end{array}\right)\stackrel{r_2-r_3,r_1-r_3}{\to }\left(\begin{array}{cccc}1& 2& 0& 2\\ 0& 1& 0& 3\\ 0& 0& 1& 0\end{array}\right)\stackrel{r_1-2r_2}{\to }\left(\begin{array}{cccc}1& 0& 0& -4\\ 0& 1& 0& 3\\ 0& 0& 1& 0\end{array}\right)$

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

4. 主元选取策略

4.1 部分主元选取

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

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

4.2 全主元选取

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

优点：数值稳定性最好。

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

4.3 主元选取的重要性

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

示例：

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

不选主元：$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. 稀疏矩阵可以使用特殊存储格式加速