图

高斯消元法解线性方程组

预备知识 矩阵

   线性方程组(有 $x_1\dots x_n$ 这 $n$ 个未知量, 所以也叫 $\boldsymbol{n}$ 元一次方程组

\begin{equation} \leftgroup{ &a_{1,1}x_1 + a_{1,2}x_2 + \dots + a_{1,n}x_n&=\quad &y_1\\ &a_{2,1}x_1 + a_{2,2}x_2 + \dots + a_{2,n}x_n&=\quad &y_2\\ &\qquad \qquad \dots \qquad \dots \qquad \dots\\ &a_{m,1}x_1 + a_{m,2}x_2 + \dots + a_{m,n}x_n&=\quad &y_m}\\ \end{equation}
可以写成矩阵和列矢量相乘的形式
\begin{equation} \mat A \bvec x = \bvec y \end{equation}
其中 $\mat A$ 是维度 $m \times n$ 的矩阵,称为系数矩阵
\begin{equation} \mat A= \begin{pmatrix} a_{1,1} &a_{1,2} &\cdots &a_{1,n} \\ a_{2,1} &a_{2,2} &\cdots &a_{2,n} \\ \vdots &\vdots &\ddots &\vdots \\ a_{m,1} &a_{m,2} &\cdots &a_{m,n} \\ \end{pmatrix} \end{equation}
$\bvec x$ 是 $n$ 维列矢量 $(x_1,x_2,\dots,x_m,\dots,x_n)\Tr$. $\bvec y$ 是 $m$ 维列矢量 $(y_1,y_2,\dots,y_m)\Tr$,称为常数列. $\mat A$ 和 $\bvec y$ 通常看做已知的,而 $\bvec x$ 看做未知的, 即方程组待求的. 下面我们介绍一种解线性方程组的简单的方法, 高斯消元法(Gauss elimination). 先来看一个简单的例子.

例1 

   我们先回顾一下初中阶段如何解线性方程组, 例如

\begin{equation} \leftgroup{ &2x + 3y = 21\\ &5x - 2y = 5 }\end{equation}
一种方法是将第一条等式两边除以 2 再移项得到
\begin{equation} x = - \frac32 y + \frac{21}{2} \end{equation}
再代入第二个条式消去 $x$ 得
\begin{equation} -\frac{19}{2} y + \frac{105}{2} = 5 \end{equation}
解得 $y = 5$, 再代入第一条等式得 $x = 3$.

   另一种更方便的解法是, 将第一条等式(两边)乘以 $-5/2$, 加到第二条上消去 $x$ 得

\begin{equation} -\frac{19}{2} y = -\frac{95}{2} \end{equation}
解得 $y = 5$, 再代入第一条等式得 $x = 3$. 为什么可以这么做? 简单来说是因为如果两条等式都成立, 将它们两边相加得到的新的等式同样成立. 下面我们来详细讲解第二种方法.

   为了书写简单, 我们可以用所谓的增广矩阵(augmented matrix)来表示矩阵和常数列, 即把式 4 记为

\begin{equation} \qtyRound{ \begin{array}{cc|c} 2 & 3 & 21 \\ 5 & -2 & 5 \end{array} }\end{equation}
同样把第一行乘以 $-5/2$, 加到第二行上得
\begin{equation} \qtyRound{ \begin{array}{cc|c} 2 & 3 & 21 \\ 0 & -19/2 & -95/2 \end{array} }\end{equation}

   如果这个方程有多个未知数, 且方程的数量和未知数相同(系数矩阵为方阵), 理想情况下我们可以用第一行消去所有 $i > 1$ 行的第一个系数, 再用第二行消去所有 $i > 2$ 行的第 2 个系数, 以此类推, 最后得到一个三角形系数矩阵. 三角形系数矩阵的最后一行只有最后一个变量的系数不为零, 我们求出这个变量后, 再代入倒数第二行(只有两个未知量)求出另一个未知量, 最后就可以得到所有未知量的值. 这个过程叫做反向迭代(backward substitution). 注意这只是一种理想的情况, 如果在处理第 $i$ 行的时候发现 $a_{i,i} = 0$, 则该方法无法进行下去. 为此我们需要稍微复杂一些的方法, 也就是高斯消元法的一般步骤.

一般步骤

   我们将式 1 形式的方程组用增广矩阵表示为

\begin{equation} \mat B=(\mat A ,\bvec y)={ \qtyRound{ \begin{array}{cccc|c} a_{1,1} &a_{1,2} &\cdots &a_{1,n} &y_1 \\ a_{2,1} &a_{2,2} &\cdots &a_{2,n} &y_2 \\ \vdots &\vdots &\ddots &\vdots &\vdots \\ a_{m,1} &a_{m,2} &\cdots &a_{m,n} &y_m \\ \end{array} }} \end{equation}

   定义以下三种矩阵(或增广矩阵)变换为初等行变换. 初等行变换不改变方程组的解1

  1. 对调矩阵中的第 $i$ 行与第 $j$ 行, 记作 $\bvec r_i \leftrightarrow \bvec r_j$
  2. 将矩阵第 $i$ 行的所有元素乘以一个非零数 $k$, 记作 $\bvec r_i \times k$
  3. 把矩阵第 $i$ 行的所有元素乘以数 $k$ 后加到第 $j$ 行上, 记作 $\bvec r_i + \bvec r_j \times k$

   任何非零矩阵(或增广矩阵)经过有限次初等行变换后总可以使系数矩阵 $\mat A$ 转化为梯形矩阵(echelon form). 我们把梯形矩阵定义为满足该条件的矩阵: 第 $i$ 行的第一个非零系数2 $a_{i,q(i)}$ 的列标 $q(i)$ 总是大于第 $i-1$ 行的第一个非零元 $a_{i-1, q(i-1)}$ 的列标 $q(i-1)$. 与例 1 不同的是, 当系数矩阵经过行变换化为梯形矩阵后, 最后若干行有可能都为零, 最后一个非零行也未必只有一个非零元.

   高斯消元法的一般步骤如下:

   完成后, 系数矩阵就会变为梯形矩阵.

例2 解线性方程组

  

\begin{equation} \leftgroup{ &x_1 &+ &x_2 &- &x_3 &+ &x_4&=\quad &3\\ &2x_1 &+ &2x_2 &- &2x_3 &+ &x_4&=\quad &7\\ &x_1 &+ &x_2 & & &+ &2x_4&=\quad &3\\ &2x_1 &+ &2x_2 &- &x_3 &+ &5x_4&=\quad &4} \end{equation}
解:

   将该方程组写成增广矩阵形式

\begin{equation} \mat B={ \qtyRound{ \begin{array}{cccc|c} 1 &1 &-1 &1 &3 \\ 2 &2 &-2 &1 &7 \\ 1 &1 &0 &2 &3 \\ 2 &2 &-1 &5 &4 \\ \end{array} }} \end{equation}
开始消元
\begin{equation} \begin{aligned} \bvec r_2 - 2 &\bvec r_1 \\ \bvec r_3 - 1 &\bvec r_1 \\ \bvec r_4 - 2 &\bvec r_1 \\ \end{aligned} \quad \Longrightarrow \quad \mat B={ \qtyRound{\begin{array}{cccc|c} 1 &1 &-1 &1 &3 \\ 0 &0 &0 &-1 &1 \\ 0 &0 &1 &1 &0 \\ 0 &0 &1 &3 &-2 \\ \end{array} }} \end{equation}

   发现此时,矩阵第二列自第二行以下全为零,所以需要依次向下一列寻找不为零的元素.继续消元

\begin{equation} \begin{aligned} \bvec r_2 \leftrightarrow &\bvec r_4 \\ \bvec r_3 - 1 &\bvec r_2 \\ \bvec r_4 - 0 &\bvec r_2 \\ \end{aligned} \quad \Longrightarrow \quad \mat B={ \qtyRound{\begin{array}{cccc|c} 1 &1 &-1 &1 &3 \\ 0 &0 &1 &3 &-2 \\ 0 &0 &0 &-2 &2 \\ 0 &0 &0 &-1 &1 \\ \end{array} }} \end{equation}
\begin{equation} \bvec r_4 - 0.5 \bvec r_3 \quad \Longrightarrow \quad \mat B={ \qtyRound{\begin{array}{cccc|c} 1 &1 &-1 &1 &3 \\ 0 &0 &1 &3 &-2 \\ 0 &0 &0 &-2 &2 \\ 0 &0 &0 &0 &0 \\ \end{array} }} \end{equation}
我们按照上面的方法用第 3 行求 $x_4$, 代入第 2 行求得 $x_3$. 然而当我们想用第 1 行求 $x_1$ 的时候却出发现我们还没求出 $x_2$. 解决办法是, 我们令 $x_2 = c$ 且假设 $c$ 可以取任意值, 则解可以表示为
\begin{equation} \leftgroup{ &x_1 &=\quad &5-c\\ &x_2 &=\quad &c \\ &x_3 &=\quad &1\\ &x_4 &=\quad &-1} \end{equation}
或者写成矢量的形式
\begin{equation} \bvec x = c \pmat{-1\\ 1\\ 0\\ 0} + \pmat{5\\ 0\\ 1\\ -1} \end{equation}
将该式代入方程组, 可以验证 $c$ 取任意值时方程组都成立.

   如果多个 $x_i$ 的值都未知, 我们就分别假设它们等于不同的任意常数即可.

解的分类

   当系数矩阵变为梯形矩阵后, 可以用以下步骤判断解的情况:

  1. 若存在系数都为零的行 $i$, 但是对应的常数 $y_i$ 却不为零, 则方程组无解, 否则有解.
  2. 若系数矩阵可以化为三角矩阵(且系数矩阵第一列不全为零), 则方程有唯一解, 否则有无穷多个解.

解的表示

   按照例 2 中的方法, 如果方程有解, 我们总可以将解表示为一些常矢量的线性组合加上一个常矢量.

\begin{equation} \bvec x = \sum_{i=1}^{N} c_i \bvec x_i + \bvec x_0 \end{equation}
其中 $c_i$ 是 $N$ 个任意常数(当方程有唯一解时 $N = 0$), 无论这些常数取什么值, $\bvec x$ 都是方程的解. 另一方面, 给出方程的任意一个解, 总能找到一些常数 $c_i$ 与之对应. 式 18 叫做方程的通解, 通解中的任意一个就做方程的特解(例如上式中所有的 $\bvec x_i$ 都是特解).

   特殊地, 如果 $\bvec y = \bvec 0$ (粗体的 $\bvec 0$ 表示零矢量, 即每个元都是 0),则方程组是齐次的. 齐次方程一个显然的特解是 $\bvec x = \bvec 0$, 根据高斯消元法, 我们可知, 若齐次方程组存在无穷个解, 它们可以表示为

\begin{equation} \bvec x = \sum_{i=1}^{N} c_i \bvec x_i \end{equation}
即 $\bvec x_0 = \bvec 0$.

   所以, 对于任意有解的非齐次方程组 $\mat A \bvec x = \bvec y$, 我们可以将通解(式 18 ) 从形式上理解为齐次方程组 ($\mat A \bvec x = \bvec 0$) 的通解与非齐次方程组的任意一个特解相加.


1. 这点我们留到以后证明
2. 为了书写简单, 我们将每次变换后的系数矩阵元仍然用 $a_{i,j}$ 来表示, 虽然它的值可能已经发生变化. 若需要区分, 可以将第 $n$ 次变换后的矩阵元用 $a_{i,j}^{(n)}$ 表示.
3. 如果 $a_{1,1} \ne 0$ 则不需要
4. 如果在处理 $i = m-1$ 之前就得到了梯形矩阵, 则可提前终止.

致读者: 小时物理百科一直以来坚持所有内容免费且不做广告,这导致我们处于日渐严重的亏损状态。长此以往很可能会最终导致我们不得不选择商业化,例如大量广告,内容付费,会员制,甚至被收购。因此,我们鼓起勇气在此请求广大读者热心捐款,使网站得以健康发展。如果看到这条信息的每位读者能慷慨捐助 10 元,我们几天内就能脱离亏损状态,并保证网站能在接下来的一整年里向所有读者继续免费提供优质内容。感谢您的支持。
—— 小时(项目创始人)

编辑词条 返回目录 返回主页 捐助项目 © 小时物理百科 保留一切权利