高斯消元法简介

尽管使用矩阵逆（我们将在下一节讨论）提供了一种巧妙的理论方法来将 $Ax = b$ 的解表示为 $x = A^{-1}b$，但对于大型系统而言，这通常不是实际求得解 $x$ 的计算效率最高或数值最稳定的方式。解决线性方程组的一种更基本且常用的算法是高斯消元法。你可能以前接触过这种方法，也许是在不同的背景下。高斯消元法是一种系统化的矩阵方程变换步骤。

高斯消元法的核心思想是将原始方程组变换为一个更容易求解的等价系统。‘等价’意味着新系统与原始系统拥有相同的解集。我们通过对增广矩阵应用一系列初等行变换来实现这种变换。

增广矩阵

首先，我们使用增广矩阵来表示系统 $Ax = b$。这只是将矩阵 $A$ 附加向量 $b$ 作为额外一列。我们通常画一条竖线来在视觉上区分它们，但这只是一种约定。

对于像这样的系统：

$$\begin{alignedat}{4} 2x_1 & {}+{} & x_2 & {}-{} & x_3 & {}={} & 8 \\ -3x_1 & {}-{} & x_2 & {}+{} & 2x_3 & {}={} & -11 \\ -2x_1 & {}+{} & x_2 & {}+{} & 2x_3 & {}={} & -3 \end{alignedat}$$

对应的矩阵方程 $Ax=b$ 是：

$$\begin{bmatrix} 2 & 1 & -1 \\ -3 & -1 & 2 \\ -2 & 1 & 2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 8 \\ -11 \\ -3 \end{bmatrix}$$

该系统的增广矩阵是：

$$\left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{array} \right]$$

初等行变换

高斯消元法通过对该增广矩阵应用三种初等行变换进行：

1. 交换两行： 交换第 $i$ 行和第 $j$ 行。（对应于交换两个方程）。
2. 缩放一行： 将第 $i$ 行中的所有元素乘以一个非零标量 $c$。（对应于将一个方程乘以 $c$）。
3. 将一行的倍数加到另一行： 将第 $i$ 行的 $c$ 倍加到第 $j$ 行。（对应于将一个方程的倍数加到另一个方程）。

重要的是，这些操作都不会改变线性系统的解集。

目标：行阶梯形

应用这些操作的目标是将增广矩阵的系数部分（左侧）变换为上三角形式，也称为行阶梯形。一个矩阵处于行阶梯形如果：

1. 所有全零行都在底部。
2. 每个非零行的第一个非零元素（“主元”或“枢轴”）严格位于其上方行的主元的右侧。

对于我们的示例增广矩阵，一个可能的行阶梯形可能如下所示（确切的值取决于所选择的操作）：

$$\left[ \begin{array}{ccc|c} \blacksquare & * & * & * \\ 0 & \blacksquare & * & * \\ 0 & 0 & \blacksquare & * \end{array} \right]$$

其中 $\blacksquare$ 表示一个非零主元，而 $*$ 表示任意值（包括零）。

过程：向前消元和反向代入

高斯消元法通常包括两个阶段：

1. 向前消元： 系统地使用行操作，从左向右移动，在每列主元下方引入零。这实现了行阶梯形。
2. 反向代入： 一旦矩阵处于行阶梯形，对应的方程组就容易求解。最后一个方程直接给出最后一个变量的值。然后可以将此值代回倒数第二个方程，求解倒数第二个变量，以此类推，向上进行。

让我们用我们的例子说明：

$$\left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{array} \right]$$

• 步骤 1： 目标是在第一个主元（第一行第一列的 '2'）下方置零。
  • 将第 1 行的 $\frac{3}{2}$ 倍加到第 2 行：$R_2 \leftarrow R_2 + \frac{3}{2}R_1$
  • 将第 1 行的 $1$ 倍加到第 3 行：$R_3 \leftarrow R_3 + R_1$
  $$\left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & 1/2 & 1/2 & 1 \\ 0 & 2 & 1 & 5 \end{array} \right]$$
• 步骤 2： 目标是在第二个主元（第二行第二列的 '1/2'）下方置零。
  • 将第 2 行的 $-4$ 倍加到第 3 行：$R_3 \leftarrow R_3 - 4R_2$
  $$\left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & 1/2 & 1/2 & 1 \\ 0 & 0 & -1 & 1 \end{array} \right]$$

该矩阵现在处于行阶梯形。

• 步骤 3： 反向代入。转换回方程： $$\begin{alignedat}{4} 2x_1 & {}+{} & x_2 & {}-{} & x_3 & {}={} & 8 \\ & & \tfrac{1}{2}x_2 & {}+{} & \tfrac{1}{2}x_3 & {}={} & 1 \\ & & & & -x_3 & {}={} & 1 \end{alignedat}$$
  • 根据最后一个方程：$-x_3 = 1 \implies x_3 = -1$。
  • 将 $x_3=-1$ 代入第二个方程：$\frac{1}{2}x_2 + \frac{1}{2}(-1) = 1 \implies \frac{1}{2}x_2 - \frac{1}{2} = 1 \implies \frac{1}{2}x_2 = \frac{3}{2} \implies x_2 = 3$。
  • 将 $x_2=3$ 和 $x_3=-1$ 代入第一个方程：$2x_1 + (3) - (-1) = 8 \implies 2x_1 + 4 = 8 \implies 2x_1 = 4 \implies x_1 = 2$。

因此，解是 $x = \begin{bmatrix} 2 \\ 3 \\ -1 \end{bmatrix}$。

一个简化流程图，说明了高斯消元法的主要阶段：通过行操作将增广矩阵变换为行阶梯形（向前消元），随后进行反向代入以求得解向量。

相关性与局限性

高斯消元法提供了一种求解 $Ax=b$ 的具体算法。理解此过程有益，原因如下：

1. 依据： 它是数值线性代数库中许多实用算法的依据，尽管实际实现通常使用变体（例如我们稍后会涉及的 LU 分解）以提高效率和稳定性。
2. 思想： 它强化了将问题变换为等价、更简单形式的理念。
3. 分析： 它有助于理解矩阵秩以及解的存在性和唯一性等方面（例如，系数部分出现全零行但右侧为非零值表示无解）。

虽然手动进行高斯消元法对于小型系统是可行的，但对于大型系统而言，它会变得繁琐且容易出现数值误差（尤其是在涉及除以小数时）。在实际操作中，我们依赖于 NumPy 和 SciPy 等库中提供的优化实现，这些实现通常使用源于这些原理的更高级技术。

在接下来的章节中，我们将考察矩阵逆，以及它如何提供另一种代数方法来思考求解 $Ax=b$，同时也会介绍如何使用计算工具进行计算。