第31章 高斯消元法与高斯-约当消元法

高斯消元法与高斯-约当消元法

矩阵记法

用矩阵来实施消元法求解方程组更为高效。矩阵是一个排列在括号中的数的矩形阵列，例如：

\[\begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14} \\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \end{bmatrix}\]

矩阵中的数称为元素。上面的矩阵有三行四列，称为 \(3 \times 4\) 矩阵。元素用两个下标表示：第 \(i\) 行第 \(j\) 列的元素为 \(a_{ij}\)。一般地，有 \(m\) 行 \(n\) 列的矩阵称为 \(m \times n\) 矩阵。

行等价矩阵

两个矩阵称为行等价的，若其中一个可通过以下初等行变换的若干次应用变换为另一个：

  1. 互换两行（符号：\(R_i \leftrightarrow R_j\)）
  2. 用某行的非零倍数替换该行（符号：\(kR_i \to R_i\)）
  3. 用某行加上另一行的倍数的结果替换该行（符号：\(kR_i + R_j \to R_j\)）

这些操作与产生等价方程组的操作完全对应（参见第30章）。

例 31.1 对矩阵 \(\begin{bmatrix} 5 & -2 \\ 2 & 6 \end{bmatrix}\)，依次执行：

  1. \(R_1 \leftrightarrow R_2\)：互换两行，得 \(\begin{bmatrix} 2 & 6 \\ 5 & -2 \end{bmatrix}\)

  2. \(\frac{1}{2}R_1 \to R_1\)：新第一行各元素乘以 \(\frac{1}{2}\)，得 \(\begin{bmatrix} 1 & 3 \\ 5 & -2 \end{bmatrix}\)

  3. \(-5R_1 + R_2 \to R_2\)：新第二行各元素加上 \(-5\) 倍第一行的对应元素，得 \(\begin{bmatrix} 1 & 3 \\ 0 & -17 \end{bmatrix}\)

矩阵与线性方程组

对 \(m\) 个方程 \(n\) 个变量的标准形式线性方程组，对应一个 \(m \times (n+1)\) 的矩阵，称为方程组的增广矩阵。例如方程组：

\[3x + 5y - 2z = 4, \quad -2x - 3y = 6, \quad 2x + 4y + z = -3\]

对应增广矩阵：

\[\begin{bmatrix} 3 & 5 & -2 & \mid & 4 \\ -2 & -3 & 0 & \mid & 6 \\ 2 & 4 & 1 & \mid & -3 \end{bmatrix}\]

竖线仅用于将变量系数与常数项分开，无数学意义。

行阶梯形

满足以下条件的矩阵称为行阶梯形：

  1. 每行第一个非零数为 1；
  2. 每行第一个非零数所在列，在下方各行第一个非零数所在列的左边；
  3. 全零行位于所有非零行的下方。

例 31.2 对矩阵 \(\begin{bmatrix} 1 & -1 & 3 \\ 3 & 2 & -1 \end{bmatrix}\) 进行行变换至行阶梯形：

\[\begin{bmatrix} 1 & -1 & 3 \\ 3 & 2 & -1 \end{bmatrix} \xrightarrow{-3R_1 + R_2 \to R_2} \begin{bmatrix} 1 & -1 & 3 \\ 0 & 5 & -10 \end{bmatrix} \xrightarrow{\frac{1}{5}R_2 \to R_2} \begin{bmatrix} 1 & -1 & 3 \\ 0 & 1 & -2 \end{bmatrix}\]

高斯消元法

高斯消元法（含回代）的求解过程如下：

  1. 将方程组化为标准形式；
  2. 写出方程组的增广矩阵；
  3. 对增广矩阵进行行变换，得到行阶梯形；
  4. 写出与该矩阵对应的方程组；
  5. 从最后一个非零方程开始，逐步回代求解。

例 31.3 用高斯消元法求解 \(x - y = 3\)，\(3x + 2y = -1\)。

增广矩阵化为行阶梯形：\(\begin{bmatrix} 1 & -1 & \mid & 3 \\ 0 & 1 & \mid & -2 \end{bmatrix}\)

对应方程组：\(x - y = 3\)，\(y = -2\)。由 \(y = -2\) 代入第一方程得 \(x = 1\)。解为 \((1, -2)\)。

简化行阶梯形

若矩阵满足行阶梯形的条件，且每行第一个 1 所在列的上方元素也全为 0，则称为简化行阶梯形（reduced row-echelon form）。

例 31.4 对 \(\begin{bmatrix} 1 & -1 & 3 \\ 0 & 1 & -2 \end{bmatrix}\) 进行行变换至简化行阶梯形：

\[\begin{bmatrix} 1 & -1 & 3 \\ 0 & 1 & -2 \end{bmatrix} \xrightarrow{R_2 + R_1 \to R_1} \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & -2 \end{bmatrix}\]

解可直接读出：\(x = 1\)，\(y = -2\)。

高斯-约当消元法

高斯-约当消元法的求解过程如下：

  1. 将方程组化为标准形式；
  2. 写出方程组的增广矩阵；
  3. 对增广矩阵进行行变换，得到简化行阶梯形；
  4. 写出与该矩阵对应的方程组；
  5. 若有唯一解，直接读出；若有无穷多解，对不确定变量赋任意实数值后即可得到其他变量的值。

解题示例

31.1. 对矩阵

\[\begin{bmatrix} 5 & 3 & -2 & 3 \\ -3 & 6 & 12 & -3 \\ 1 & 0 & -4 & 5 \end{bmatrix}\]

分别执行：(a) \(R_1 \leftrightarrow R_3\)；(b) \(-\frac{1}{3}R_2 \to R_2\)；(c) \(2R_2 + R_1 \to R_1\)。

  1. 互换第 1、3 行：\(\begin{bmatrix} 1 & 0 & -4 & 5 \\ -3 & 6 & 12 & -3 \\ 5 & 3 & -2 & 3 \end{bmatrix}\)

  2. 第 2 行乘以 \(-\frac{1}{3}\)：\(\begin{bmatrix} 5 & 3 & -2 & 3 \\ 1 & -2 & -4 & 1 \\ 1 & 0 & -4 & 5 \end{bmatrix}\)

  3. 第 1 行加上 2 倍第 2 行：\(\begin{bmatrix} -1 & 15 & 22 & -3 \\ -3 & 6 & 12 & -3 \\ 1 & 0 & -4 & 5 \end{bmatrix}\)

31.2. 将矩阵 \(\begin{bmatrix} 1 & 2 & -2 & 3 \\ 2 & 5 & 0 & -7 \\ 3 & 7 & -2 & -4 \end{bmatrix}\) 化为行阶梯形。

\[\xrightarrow{R_2 + (-2)R_1 \to R_2,\ R_3 + (-3)R_1 \to R_3} \begin{bmatrix} 1 & 2 & -2 & 3 \\ 0 & 1 & 4 & -13 \\ 0 & 1 & 4 & -13 \end{bmatrix} \xrightarrow{R_3 + (-1)R_2 \to R_3} \begin{bmatrix} 1 & 2 & -2 & 3 \\ 0 & 1 & 4 & -13 \\ 0 & 0 & 0 & 0 \end{bmatrix}\]

31.3. 将任意方程组的矩阵化为行阶梯形的一般策略：

  1. 必要时互换行，使第一行第一个位置为非零元素，再将该行化为以 1 开头；
  2. 用该 1 消去下方各行第一个位置的元素；
  3. 若出现全零行（竖线左侧），将其移至底部；
  4. 对第二行重复上述过程；
  5. 依此递推直至处理完所有行。

31.4. 用高斯消元法求解 \(x + 2y - 2z = 3\)，\(2x + 5y = -7\)，\(3x + 7y - 2z = -4\)。

增广矩阵化为行阶梯形（由题 31.2 结果）：

\[\begin{bmatrix} 1 & 2 & -2 & 3 \\ 0 & 1 & 4 & -13 \\ 0 & 0 & 0 & 0 \end{bmatrix} \leftrightarrow \begin{cases} x + 2y - 2z = 3 \\ y + 4z = -13 \\ 0 = 0 \end{cases}\]

有无穷多解。令 \(z = r\)，则 \(y = -13 - 4r\)，\(x = 10r + 29\)。所有解为 \((10r + 29,\ -13 - 4r,\ r)\)，\(r\) 为任意实数。

31.5. 将矩阵

\[\begin{bmatrix} 1 & 0 & -1 & 1 & 2 & 2 \\ 1 & 1 & 0 & 2 & -3 & -4 \\ 2 & 0 & -1 & 1 & 3 & 3 \\ 0 & -2 & -1 & -3 & 9 & 11 \end{bmatrix}\]

化为简化行阶梯形。（详细行变换过程见原题）最终结果为：

\[\begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 2 & -4 & -5 \\ 0 & 0 & 1 & -1 & -1 & -1 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}\]

31.6. 用高斯-约当消元法求解：

\[x_1 - x_3 + x_4 + 2x_5 = 2, \quad x_1 + x_2 + 2x_4 - 3x_5 = -4\]

\[2x_1 - x_3 + x_4 + 3x_5 = 3, \quad -2x_2 - x_3 - 3x_4 + 9x_5 = 11\]

增广矩阵化为简化行阶梯形（题 31.5 结果）：

\[x_1 + x_5 = 1, \quad x_2 + 2x_4 - 4x_5 = -5, \quad x_3 - x_4 - x_5 = -1\]

有无穷多解。令 \(x_5 = r\)，\(x_4 = s\)，则 \(x_3 = r + s - 1\)，\(x_2 = 4r - 2s - 5\)，\(x_1 = 1 - r\)。所有解为 \((1-r,\ 4r-2s-5,\ r+s-1,\ s,\ r)\)，\(r\)，\(s\) 为任意实数。

31.7. 水泵 A、B、C 共同工作可在 2 小时内注满水箱；只用 A 和 C 需 4 小时；只用 B 和 C 需 3 小时。每台泵单独工作各需多长时间？

设 \(t_1\)，\(t_2\)，\(t_3\) 分别为 A、B、C 单独工作所需时间，对应速率 \(r_i = 1/t_i\)：

\[2r_1 + 2r_2 + 2r_3 = 1, \quad 4r_1 + 4r_3 = 1, \quad 3r_2 + 3r_3 = 1\]

增广矩阵化为简化行阶梯形后得 \(r_1 = 1/6\)，\(r_2 = 1/4\)，\(r_3 = 1/12\)。

因此：A 单独工作需 6 小时，B 单独工作需 4 小时，C 单独工作需 12 小时。

31.8. 投资者有 80 万美元，分别以 6%（存单）、10%（共同基金）、12%（成长股）、14%（风险资本）投资，计划年回报 78000 美元，且其他投资总额为存单投资额的三倍，应如何分配投资？

设 \(x_i\) 分别为各项投资额，建立方程组后，增广矩阵化为简化行阶梯形，得：

\[x_1 = 200000, \quad x_2 - x_4 = 300000, \quad x_3 + 2x_4 = 300000\]

有无穷多解。令 \(x_4 = r\)，则 \(x_1 = 200000\)，\(x_2 = 300000 + r\)，\(x_3 = 300000 - 2r\)。例如令 \(r = 100000\)，则存单 20 万，共同基金 40 万，成长股 10 万，风险资本 10 万。

补充习题

31.9. 化为行阶梯形：

  1. \(\begin{bmatrix} 2 & 5 & 3 \\ 4 & -2 & -6 \end{bmatrix}\)；(b) \(\begin{bmatrix} 2 & 5 & 3 \\ 4 & 10 & -6 \end{bmatrix}\)；(c) \(\begin{bmatrix} 2 & 5 & 3 \\ 4 & 10 & 6 \end{bmatrix}\)

答： (a) \(\begin{bmatrix} 1 & 5/2 & 3/2 \\ 0 & 1 & 1 \end{bmatrix}\)；(b) \(\begin{bmatrix} 1 & 5/2 & 3/2 \\ 0 & 0 & -12 \end{bmatrix}\)；(c) \(\begin{bmatrix} 1 & 5/2 & 3/2 \\ 0 & 0 & 0 \end{bmatrix}\)

31.10. 用上题信息求解方程组：

  1. \(2x + 5y = 3\)，\(4x - 2y = -6\)；(b) \(2x + 5y = 3\)，\(4x + 10y = -6\)；(c) \(2x + 5y = 3\)，\(4x + 10y = 6\)

答： (a) \((-1, 1)\)；(b) 无解；(c) \(\left(\dfrac{3-5r}{2}, r\right)\)，\(r\) 为任意实数

31.11. 化为简化行阶梯形（略，参见原题）

31.12. 用上题信息求解方程组（略，参见原题）

31.13. 140 磅坚果混合物由每磅 4 美元的杏仁、每磅 6 美元的山核桃、每磅 7.5 美元的巴西坚果组成，混合物售价为每磅 5.5 美元，有哪些可能的组合？

答： 若 \(t\) = 巴西坚果磅数，则可取 \(105 - 1.75t\) 磅山核桃和 \(35 + 0.75t\) 磅杏仁，要求三者均为正数，即 \(0 < t < 60\)。