2.3解线性方程组

文档摘要

2.3 解线性方程组在(2.3)中，我们介绍了方程组的一般形式，即 $$ a{1, 1}x1 + \cdots + a{1, n}xn = b1 \\ \vdots \\ a{m, 1}x1 + \cdots + a{m, n}xn = bm, \tag{2.37} $$ 其中 $a{i, j} \in \mathbb{R}$ 和 $bi \in \mathbb{R}$ 是已知常数，而 $xj$ 是未知数，$i = 1, \dots, m$，$j = 1, \dots, n$。到目前为止，我们已经看到矩阵可以作为一种紧凑的方式来表述线性方程组，从而可以写成 $Ax = b$，见(2.10)。此外，我们还定义了矩阵的基本运算，例如矩阵的加法和乘法。

2.3 解线性方程组

在(2.3)中，我们介绍了方程组的一般形式，即

a_{1, 1}x_1 + \cdots + a_{1, n}x_n = b_1 \\ \vdots \\ a_{m, 1}x_1 + \cdots + a_{m, n}x_n = b_m, \tag{2.37}

其中 a_{i, j} \in \mathbb{R} 和 b_i \in \mathbb{R} 是已知常数，而 x_j 是未知数，i = 1, \dots, m，j = 1, \dots, n。到目前为止，我们已经看到矩阵可以作为一种紧凑的方式来表述线性方程组，从而可以写成 Ax = b，见(2.10)。此外，我们还定义了矩阵的基本运算，例如矩阵的加法和乘法。在接下来的内容中，我们将专注于解线性方程组，并提供一种求矩阵逆的算法。

2.3.1 特解和通解

在讨论如何一般性地解线性方程组之前，我们先来看一个例子。考虑以下方程组：

\begin{bmatrix} 1 & 0 & 8 & -4 \\ 0 & 1 & 2 & 12 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} = \begin{bmatrix} 42 \\ 8 \end{bmatrix}. \tag{2.38}

该方程组有两条方程和四个未知数。因此，一般来说，我们期望有无穷多解。这个方程组的形式特别简单，前两列分别由1和0组成。我们希望找到标量 x_1, \dots, x_4，使得 \displaystyle \sum_{i=1}^4 x_i c_i = b，其中我们将矩阵的第 i 列定义为 c_i，而 b 是(2.38)的右侧。通过取42倍的第一列和8倍的第二列，可以立即找到(2.38)的一个解：

b = \begin{bmatrix} 42 \\ 8 \end{bmatrix} = 42 \begin{bmatrix} 1 \\ 0 \end{bmatrix} + 8 \begin{bmatrix} 0 \\ 1 \end{bmatrix}. \tag{2.39}

因此，一个解是 [42, 8, 0, 0]^\top。这个解被称为特解（或特殊解）。然而，这并不是这个线性方程组的唯一解。为了找到所有其他解，我们需要创造性地用矩阵的列以非平凡的方式生成 0：将 0 加到特解上不会改变特解。为此，我们用前两列（它们的形式非常简单）来表示第三列：

\begin{bmatrix} 8 \\ 2 \end{bmatrix} = 8 \begin{bmatrix} 1 \\ 0 \end{bmatrix} + 2 \begin{bmatrix} 0 \\ 1 \end{bmatrix}. \tag{2.40}

因此如果我们将原矩阵 \displaystyle \begin{bmatrix}1 & 0 & 8 & -4 \\0 & 1 & 2 & 12\end{bmatrix} 的所有列从左到右分别记作向量 c_1, c_2, c_3, c_4，我们可以写出：

0 = 8c_1 + 2c_2 - c_3 + 0c_4,

并且 (x_1, x_2, x_3, x_4) = (8, 2, -1, 0)。

事实上，将这个解按任意标量 \lambda_1 \in \mathbb{R} 缩放都会产生 0 向量，即

\begin{bmatrix} 1 & 0 & 8 & -4 \\ 0 & 1 & 2 & 12 \end{bmatrix} \begin{bmatrix} \lambda_1 \cdot 8 \\ \lambda_1 \cdot 2 \\ -\lambda_1 \\ 0 \end{bmatrix} = \lambda_1 (8c_1 + 2c_2 - c_3) = 0. \tag{2.41}

按照相同的思路，我们将矩阵的第四列用前两列表示，并生成另一组非平凡的 0：

\begin{bmatrix} 1 & 0 & 8 & -4 \\ 0 & 1 & 2 & 12 \end{bmatrix} \begin{bmatrix} \lambda_2 \cdot (-4) \\ \lambda_2 \cdot 12 \\ 0 \\ -\lambda_2 \end{bmatrix} = \lambda_2 (-4c_1 + 12c_2 - c_4) = 0, \tag{2.42}

对于任意 \lambda_2 \in \mathbb{R}。将所有内容放在一起，我们得到(2.38)方程组的所有解，称为通解：

\left\{ x \in \mathbb{R}^4 : x =\begin{bmatrix}42 \\ 8 \\ 0 \\ 0\end{bmatrix}+ \lambda_1\begin{bmatrix}8 \\ 2 \\ -1 \\ 0\end{bmatrix}+ \lambda_2\begin{bmatrix}-4 \\ 12 \\ 0 \\ -1\end{bmatrix}, \lambda_1, \lambda_2 \in \mathbb{R}\right\}.\tag{2.43}

注：我们遵循的一般方法包括以下三个步骤：

找到一个特解 Ax = b。
找到所有解 Ax = 0。
将步骤1和步骤2的解结合起来得到通解。

通解和特解都不是唯一的。（译者注：假如矩阵 A 的列向量线性相关，可能会有无穷多的特解和通解。）

在前面的例子中，方程组很容易解，因为矩阵(2.38)具有这种特别方便的形式，允许我们通过观察找到特解和通解。然而，一般方程组并不具有这种简单形式。幸运的是，存在一种构造性算法，可以将任何线性方程组转换为这种特别简单的形式：高斯消元法。高斯消元法的关键是线性方程组的初等变换，这些变换可以将方程组转换为更简单的形式，同时保持解集不变。然后，我们可以将这种简单形式应用到我们在(2.38)的例子中讨论的三个步骤。

2.3.2 初等变换

解线性方程组的关键是初等变换，这些变换可以保持方程组的解集不变，但可以将方程组转换为更简单的形式：

交换两个方程（矩阵中的行）。
将一个方程（行）乘以一个非零常数 \lambda \in \mathbb{R} \setminus \{0\}。
将两个方程（行）相加。

例2.6 对于 a \in \mathbb{R}，我们寻找以下方程组的所有解：

\begin{aligned} -2x_1 + 4x_2 - 2x_3 - x_4 + 4x_5 &= -3, \\ 4x_1 - 8x_2 + 3x_3 - 3x_4 + x_5 &= 2, \\ x_1 - 2x_2 + x_3 - x_4 + x_5 &= 0, \\ x_1 - 2x_2 - 3x_4 + 4x_5 &= a. \end{aligned} \tag{2.44}

我们首先将这个方程组转换为紧凑的矩阵形式 Ax = b。我们不再明确提及变量 x，并构建增广矩阵（形式为 [A \mid b]）：

\left[ \begin{matrix} -2 & 4 & -2 & -1 & 4 \\ 4 & -8 & 3 & -3 & 1 \\ 1 & -2 & 1 & -1 & 1 \\ 1 & -2 & 0 & -3 & 4 \end{matrix}\;\right| \left. \begin{matrix} -3 \\ 2 \\ 0 \\ a \end{matrix} \right].

其中我们用竖线分隔了(2.44)的左侧和右侧。我们用 \Rightarrow 表示通过初等变换对增广矩阵的转换。增广矩阵 [A \mid b] 紧凑地表示了线性方程组 Ax = b。

交换第 1 行和第 3 行后得到：

\left[\begin{matrix} 1 & -2 & 1 & -1 & 1 \\ 4 & -8 & 3 & -3 & 1 \\ -2 & 4 & -2 & -1 & 4 \\ 1 & -2 & 0 & -3 & 4 \end{matrix}\,\,\,\right| \left.\begin{matrix} 0 \\ 2 \\ -3 \\ a \end{matrix} \right].

接下来，我们对第 2 行、第 3 行和第 4 行分别进行以下变换：

第 2 行减去4倍的第 1 行；
第 3 行加上2倍的第 1 行；
第 4 行减去第 1 行。

得到：

\left[\begin{matrix} 1 & -2 & 1 & -1 & 1 \\ 0 & 0 & -1 & 1 & -3 \\ 0 & 0 & 0 & -3 & 6 \\ 0 & 0 & -1 & -2 & 3 \end{matrix}\,\,\,\right| \left.\begin{matrix} 0 \\ 2 \\ -3 \\ a \end{matrix} \right].

接着，我们对第 4 行进行以下变换：

第 4 行减去第 2 行；
第 4 行减去第 3 行。

得到：

\left[\begin{matrix} 1 & -2 & 1 & -1 & 1 \\ 0 & 0 & -1 & 1 & -3 \\ 0 & 0 & 0 & -3 & 6 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}\,\,\,\right| \left.\begin{matrix} 0 \\ 2 \\ -3 \\ a + 1 \end{matrix} \right].

最后，我们将第 2 行和第 3 行分别乘以 -1 和 \displaystyle -\frac{1}{3}，得到：

\left[\begin{matrix} 1 & -2 & 1 & -1 & 1 \\ 0 & 0 & 1 & -1 & 3 \\ 0 & 0 & 0 & 1 & -2 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}\,\,\,\right| \left.\begin{matrix} 0 \\ -2 \\ 1 \\ a + 1 \end{matrix} \right].

这个（增广）矩阵处于一个方便的形式，即行阶梯形式（REF）。将这个紧凑的表示形式重新转换为包含变量的显式形式，我们得到：

\begin{aligned} x_1 - 2x_2 + x_3 - x_4 + x_5 &= 0, \\ x_3 - x_4 + 3x_5 &= -2, \\ x_4 - 2x_5 &= 1, \\ 0 &= a + 1. \end{aligned} \tag{2.45}

只有当 a = -1 时，这个方程组才有解。一个特解是：

\begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} = \begin{bmatrix} 2 \\ 0 \\ -1 \\ 1 \\ 0 \end{bmatrix}. \tag{2.46}

通解（包含所有可能的解）是：

\left\{ x \in \mathbb{R}^5 : x = \begin{bmatrix} 2 \\ 0 \\ -1 \\ 1 \\ 0 \end{bmatrix} + \lambda_1 \begin{bmatrix} 2 \\ 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} + \lambda_2 \begin{bmatrix} 2 \\ 0 \\ -1 \\ 2 \\ 1 \end{bmatrix}, \lambda_1, \lambda_2 \in \mathbb{R} \right\}. \tag{2.47}

在接下来的内容中，我们将详细说明一种构造性方法来获得线性方程组的特解和通解。

注（主元和阶梯结构）： 按照上述方法将方程组化简完成后，某一行从左边开始的第一个非零数字称为主元，它总是严格位于其上方行的主元的右边。因此，任何处于行阶梯形式的方程组总是具有“阶梯”结构。♦

定义2.6（行阶梯形式）： 如果一个矩阵满足以下条件，则称其处于行阶梯形式：

所有只包含零的行位于矩阵的底部；相应地，所有至少包含一个非零元素的行位于只包含零的行的上方。
只考虑非零行，从左边开始的第一个非零数字（也称为主元或领先系数）总是严格位于其上方行的主元的右边。

在其他文献中，有时要求主元是1。

注（基本变量和自由变量）： 在行阶梯形式中，对应于主元的变量称为基本变量，其他变量称为自由变量。例如，在(2.45)中，x_1, x_3, x_4 是基本变量，而 x_2, x_5 是自由变量。♦

注（获得特解）： 行阶梯形式使我们的生活更简单，当我们需要确定一个特解时。为此，我们用主元列表示方程组的右侧，使得 b = \sum_{i=1}^P \lambda_i p_i，其中 p_i, i = 1, \dots, P，是主元列。通过从最右边的主元列开始，向左工作，可以最简单地确定 \lambda_i。在前面的例子中，我们将尝试找到 \lambda_1, \lambda_2, \lambda_3，使得

\lambda_1 \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} + \lambda_2 \begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \end{bmatrix} + \lambda_3 \begin{bmatrix} -1 \\ -1 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ -2 \\ 1 \\ 0 \end{bmatrix}. \tag{2.48}

从这里，我们直接找到 \lambda_3 = 1，\lambda_2 = -1，\lambda_1 = 2。当我们把所有内容放在一起时，我们不能忘记非主元列（译者注：非主元列是一列的所有元素都不是任意一行的主元的列），我们隐式地将系数设置为0。因此，我们得到特解 x = [2, 0, -1, 1, 0]^\top。♦

注（简化行阶梯形式）： 如果一个方程组处于简化行阶梯形式（也称为行简化阶梯形式或行规范形式），则：

它处于行阶梯形式。
每个主元是1。
主元是其列中唯一的非零元素。

简化行阶梯形式将在第2.3.3节中发挥重要作用，因为它允许我们以直接的方式确定线性方程组的通解。高斯消元法是一种执行初等变换以将线性方程组带入简化行阶梯形式的算法。♦

例2.7（简化行阶梯形式） 验证以下矩阵处于简化行阶梯形式（主元以粗体表示）：

A = \begin{bmatrix} \boldsymbol{1} & 3 & 0 & 0 & 3 \\ 0 & 0 & \boldsymbol{1} & 0 & 9 \\ 0 & 0 & 0 & \boldsymbol{1} & -4 \end{bmatrix}. \tag{2.49}

找到 Ax = 0 的解的关键思想是查看非主元列，我们需要将它们表示为（线性）组合的主元列。简化行阶梯形式使这相对直接，我们用它们左边的主元列的和与倍数来表示非主元列：第二列是第一列的3倍（我们可以忽略第二列右边的主元列）。因此，为了得到尽可能多的 0，我们做下面的操作

第二列减去三倍第一列：将第二列的 3 变成 0
第五列减去三倍第一列，减去九倍第三列，再加上四倍第四列

这样我们就得到了一个简化行阶梯形式的矩阵。总之，我们仍然在解一个齐次方程组 Ax = 0 其中 x \in \mathbb{R}^5。通过第一步，我们知道原方程的解集一定包含 [3, -1, 0, 0, 0]^\top；通过第二步，我们知道原方程的解集一定还包含 [3, 0, 9, -4, -1]^\top。做完这两步后矩阵已经化成了简化行阶梯形，因此原方程的解集为：

\left\{x \in \mathbb{R}^5 : x = \lambda_1\begin{bmatrix}3 \\ -1 \\ 0 \\ 0 \\ 0\end{bmatrix}+ \lambda_2\begin{bmatrix}3 \\ 0 \\ 9 \\ -4 \\ -1\end{bmatrix}, \lambda_1, \lambda_2 \in \mathbb{R}\right\}.\tag{2.50}

2.3.3 负一技巧

在接下来的内容中，我们介绍一个实用的技巧，用于读出齐次线性方程组 Ax = 0 的解，其中 A \in \mathbb{R}^{k \times n}，x \in \mathbb{R}^n。首先，我们假设 A 处于简化行阶梯形式，且没有只包含零的行，即

A = \begin{bmatrix} 0 & \cdots & 0 & \color{red}1 & * & \cdots & * & 0 & * & \cdots & * & 0 & * & \cdots & * \\ \vdots & & \vdots & 0 & 0 & \cdots & 0 & \color{red}1 & * & \cdots & * & \vdots & \vdots & & \vdots \\ \vdots & & \vdots & \vdots & \vdots & \cdots & \vdots & 0 & \vdots & \cdots & \vdots & \vdots & \vdots & & \vdots \\ \vdots & & \vdots & \vdots & \vdots & \cdots & \vdots & \vdots & \vdots & \cdots & \vdots & 0 & \vdots & & \vdots \\ 0 & \cdots & 0 & 0 & 0 & \cdots & 0 & 0 & 0 & \cdots & 0 & \color{red}1 & * & \cdots & * \\ \end{bmatrix}, \tag{2.51}

$alt text$

其中 * 可以是任意实数，条件是每行的第一个非零元素必须是1，且相应列中的所有其他元素必须是0。包含主元（以粗体标记）的列 j_1, \dots, j_k 是标准单位向量 e_1, \dots, e_k \in \mathbb{R}^k。我们通过添加 n - k 行的形式

\begin{bmatrix} 0 & \cdots & 0 & -1 & 0 & \cdots & 0 \end{bmatrix} \tag{2.52}

将这个矩阵扩展为 n \times n 矩阵 \tilde{A}，使得 \tilde{A} 的对角线上包含1或-1。然后，包含对角线上的-1的 \tilde{A} 的列是齐次方程组 Ax = 0 的解。更准确地说，这些列构成了 Ax = 0 的解空间的一个基，我们稍后将称其为核或零空间（见第2.7.3节）。

例2.8（负一技巧） 让我们重新审视已经处于简化REF的矩阵(2.49)：

A = \begin{bmatrix} 1 & 3 & 0 & 0 & 3 \\ 0 & 0 & 1 & 0 & 9 \\ 0 & 0 & 0 & 1 & -4 \end{bmatrix}. \tag{2.53}

我们通过在对角线上缺少主元的位置添加形式为(2.52)的行，将这个矩阵扩展为 5 \times 5 矩阵：

\tilde{A} = \begin{bmatrix} 1 & 3 & 0 & 0 & 3 \\ \color{red}0 & \color{red}-1 & \color{red}0 & \color{red}0 & \color{red}0 \\ 0 & 0 & 1 & 0 & 9 \\ 0 & 0 & 0 & 1 & -4 \\ \color{red}0 & \color{red}0 & \color{red}0 & \color{red}0 & \color{red}-1 \end{bmatrix}. \tag{2.54}

从这个形式中，我们可以直接读出 Ax = 0 的解，通过取 \tilde{A} 中对角线上包含-1的列：

\left\{ x \in \mathbb{R}^5 : x = \lambda_1 \begin{bmatrix} 3 \\ -1 \\ 0 \\ 0 \\ 0 \end{bmatrix} + \lambda_2 \begin{bmatrix} 3 \\ 0 \\ 9 \\ -4 \\ -1 \end{bmatrix}, \lambda_1, \lambda_2 \in \mathbb{R} \right\}, \tag{2.55}

这与我们在(2.50)中通过“洞察”得到的解完全一致。

计算逆矩阵

为了计算 A^{-1}，其中 A \in \mathbb{R}^{n \times n}，我们需要找到一个矩阵 X，使得 AX = I_n。然后，X = A^{-1}。我们可以将此写成一组同时线性方程 AX = I_n，其中我们解 X = [x_1 | \dots | x_n]。我们使用增广矩阵（译者注：就是把线性方程组中的所有数都写成一个矩阵，等号左边的系数矩阵放在左边，等号右边的数字放在右边）表示法来紧凑地表示这组方程组：

[A \mid I_n] \Rightarrow \dots \Rightarrow [I_n \mid A^{-1}]. \tag{2.56}

这意味着，如果我们将增广方程组带入简化行阶梯形式，我们可以在方程组的右侧直接读出逆矩阵。因此，确定矩阵的逆等同于解线性方程组。

例2.9（通过高斯消元法计算逆矩阵） 为了确定

A = \begin{bmatrix} 1 & 0 & 2 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 2 & 0 & 1 \\ 1 & 1 & 1 & 1 \end{bmatrix} \tag{2.57}

的逆矩阵，我们写下增广矩阵

\left[\begin{matrix} 1 & 0 & 2 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 2 & 0 & 1 \\ 1 & 1 & 1 & 1 \end{matrix}\,\,\,\right| \left.\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix} \right].

并使用高斯消元法将其带入简化行阶梯形式：

\left[\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}\,\,\,\right| \left.\begin{matrix} -1 & 2 & -2 & 2 \\ 1 & -1 & 2 & -2 \\ 1 & -1 & 1 & -1 \\ -1 & 0 & -1 & 2 \end{matrix} \right],

因此，所需的逆矩阵是其右侧：

A^{-1} = \begin{bmatrix} -1 & 2 & -2 & 2 \\ 1 & -1 & 2 & -2 \\ 1 & -1 & 1 & -1 \\ -1 & 0 & -1 & 2 \end{bmatrix}. \tag{2.58}

我们可以通过执行乘法 AA^{-1} 并观察我们是否恢复 I_4 来验证(2.58)确实是逆矩阵。

2.3.4 解线性方程组的算法

在接下来的内容中，我们将简要讨论解决形式为 Ax = b 的线性方程组的方法。我们假设存在解。如果没有解，我们需要诉诸于近似解，这在本章中没有涵盖。解决近似问题的一种方法是使用线性回归的方法，我们将在第9章中详细讨论。在特殊情况下，我们可能能够确定逆 A^{-1}，使得解 Ax = b 为 x = A^{-1}b。然而，这只在 A 是方阵且可逆的情况下才可能，然而这并不常见。否则在较弱的条件下（即 A 需要具有线性独立的列），我们可以使用变换

Ax = b \Leftrightarrow A^\top A x = A^\top b \Leftrightarrow x = (A^\top A)^{-1} A^\top b, \tag{2.59}

并使用 Moore-Penrose 伪逆 (A^\top A)^{-1} A^\top 来确定解 Ax = b，这对应于最小范数最小二乘解。计算矩阵-矩阵乘积和 A^\top A 的逆所需的计算量较大。此外，由于数值精度的原因，通常不推荐计算逆或伪逆。因此，在接下来的内容中，我们将简要讨论解线性方程组的其他方法。高斯消元法在计算行列式（第4.1节）、检查一组向量是否线性独立（第2.5节）、计算矩阵的逆（第2.2.2节）、计算矩阵的秩（第2.6.2节）以及确定线性空间的基（第2.6.1节）中发挥重要作用。高斯消元法是一种直观且构造性的方法，用于解决具有数千个变量的线性方程组。然而，对于具有数百万变量的系统，这种方法是不切实际的，因为所需的算术运算次数与联立方程的数量呈立方关系。在实践中，具有许多线性方程的系统通常通过间接方法解决，例如固定迭代方法，如 Richardson 方法、Jacobi 方法、Gauss-Seidel 方法和逐次超松弛迭代法，或 Krylov 子空间方法，如共轭梯度法、广义最小残差法或双共轭梯度法。我们推荐参考 Stoer 和 Burlirsch (2002)、Strang (2003) 和 Liesen 和 Mehrmann (2015) 的书籍以获取更多详细信息。设 x^* 是 Ax = b 的解。这些迭代方法的关键思想是设置一个迭代形式

x^{(k+1)} = Cx^{(k)} + d \tag{2.60}

对于合适的 C 和 d，以减少每一步的残差误差 \|x^{(k+1)} - x^*\| 并收敛到 x^*。我们将在第3.1节中介绍范数 \|\cdot\|，它允许我们计算向量之间的相似性。