贡献者： addis
1线性方程组（有 $x_1\dots x_n$ 这 $n$ 个未知量，所以也叫 $\boldsymbol{n}$ 元一次方程组）
\begin{equation}
\left\{\begin{aligned}
&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{aligned}\right. \\
~\end{equation}
可以写成矩阵和列矢量相乘的形式
\begin{equation}
\boldsymbol{\mathbf{A}} \boldsymbol{\mathbf{x}} = \boldsymbol{\mathbf{y}} ~,
\end{equation}
其中 $ \boldsymbol{\mathbf{A}} $ 是维度 $m \times n$ 的矩阵，称为
系数矩阵。
\begin{equation}
\boldsymbol{\mathbf{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}
$ \boldsymbol{\mathbf{x}} $ 是 $n$ 维列矢量 $(x_1,x_2,\dots,x_m,\dots,x_n) ^{\mathrm{T}} $。
$ \boldsymbol{\mathbf{y}} $ 是 $m$ 维列矢量 $(y_1,y_2,\dots,y_m) ^{\mathrm{T}} $，称为
常数列。$ \boldsymbol{\mathbf{A}} $ 和 $ \boldsymbol{\mathbf{y}} $ 通常看做已知的，而 $ \boldsymbol{\mathbf{x}} $ 看做未知的，即方程组待求的
解。下面我们介绍一种解线性方程组的简单的方法，
高斯消元法（Gauss elimination）。 先来看一个简单的例子。
例 1
我们先回顾一下初中阶段如何解线性方程组，例如
\begin{equation}
\left\{\begin{aligned}
&2x + 3y = 21\\
&5x - 2y = 5
\end{aligned}\right. ~\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}
\left(\begin{array}{cc|c}
2 & 3 & 21 \\
5 & -2 & 5
\end{array}
\right) ~\end{equation}
同样把第一行乘以 $-5/2$，加到第二行上得
\begin{equation}
\left(\begin{array}{cc|c}
2 & 3 & 21 \\
0 & -19/2 & -95/2
\end{array}
\right) ~\end{equation}
如果这个方程有多个未知数，且方程的数量和未知数相同（系数矩阵为方阵），理想情况下我们可以用第一行消去所有 $i > 1$ 行的第一个系数，再用第二行消去所有 $i > 2$ 行的第 2 个系数，以此类推，最后得到一个三角形系数矩阵。三角形系数矩阵的最后一行只有最后一个变量的系数不为零，我们求出这个变量后，再代入倒数第二行（只有两个未知量）求出另一个未知量，最后就可以得到所有未知量的值。这个过程叫做反向迭代（backward substitution）。
注意这只是一种理想的情况，如果在处理第 $i$ 行的时候发现 $a_{i,i} = 0$，则该方法无法进行下去。为此我们需要稍微复杂一些的方法，也就是高斯消元法的一般步骤。
1. 一般步骤
我们将式 1 形式的方程组用增广矩阵表示为
\begin{equation}
\boldsymbol{\mathbf{B}} =( \boldsymbol{\mathbf{A}} , \boldsymbol{\mathbf{y}} )={
\left(\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}
\right) }~
\end{equation}
定义以下三种矩阵（或增广矩阵）变换为初等行变换。初等行变换不改变方程组的解2。
- 对调矩阵中的第 $i$ 行与第 $j$ 行，记作 $ \boldsymbol{\mathbf{r}} _i \leftrightarrow \boldsymbol{\mathbf{r}} _j$
- 将矩阵第 $i$ 行的所有元素乘以一个非零数 $k$，记作 $ \boldsymbol{\mathbf{r}} _i \times k$
- 把矩阵第 $i$ 行的所有元素乘以数 $k$ 后加到第 $j$ 行上，下文简记为 $ \boldsymbol{\mathbf{r}} _j + \boldsymbol{\mathbf{r}} _i \times k$
任何非零矩阵（或增广矩阵）经过有限次初等行变换后总可以使系数矩阵 $ \boldsymbol{\mathbf{A}} $ 转化为梯形矩阵（echelon form）。我们把梯形矩阵定义为满足该条件的矩阵：第 $i$ 行的第一个非零系数3 $a_{i,q(i)}$ 的列标 $q(i)$ 总是大于第 $i-1$ 行的第一个非零元 $a_{i-1, q(i-1)}$ 的列标 $q(i-1)$。与例 1 不同的是，当系数矩阵经过行变换化为梯形矩阵后，最后若干行有可能都为零，最后一个非零行也未必只有一个非零元。
高斯消元法的一般步骤如下：
- 先处理第 $i = 1$ 行，如果 $a_{1,1} = 0$ 但某 $i' > 1$ 的行有 $a_{i', 1} \ne 0$，就先进行行变换4 $ \boldsymbol{\mathbf{r}} _i \leftrightarrow \boldsymbol{\mathbf{r}} _{i'}$。如果第一列全为 0，我们就无视第 1 列，从第 2 列重新开始，以此类推。记此时第 1 行第一个非零元的列标为 $q(1)$。接下来做若干次行变换 $ \boldsymbol{\mathbf{r}} _{i'} + \boldsymbol{\mathbf{r}} _1 \times k$ 使所有第 $i' > 1$ 行的 $a_{i', q(1)}$ 都为 0。
- 依次处理第 $i = 2\dots m-1$ 行5。要处理第 $i$ 行，先令 $q(i) = q(i-1)+1$，如果此时矩阵元 $a_{i, q(i)} = 0$，但某 $i' > i$ 的行有 $a_{i', q(i)} \ne 0$，就先进行行变换 $ \boldsymbol{\mathbf{r}} _i \leftrightarrow \boldsymbol{\mathbf{r}} _{i'}$。若不存在这样的 $i'$，我们就改令 $q(i) = q(i-1) + 2$ 并重新开始该步骤，以此类推。接下来做若干次行变换 $ \boldsymbol{\mathbf{r}} _{i'} + \boldsymbol{\mathbf{r}} _i \times k$ 使所有第 $i' > i$ 行的 $a_{i', q(i)}$ 都为 0。
完成后，系数矩阵就会变为梯形矩阵。
例 2 解线性方程组
\begin{equation}
\left\{\begin{aligned}
&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{aligned}\right. ~
\end{equation}
解：
将该方程组写成增广矩阵形式
\begin{equation}
\boldsymbol{\mathbf{B}} ={
\left(\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}
\right) }~
\end{equation}
对第一列
\begin{equation}
\begin{aligned}
\boldsymbol{\mathbf{r}} _2 - 2 & \boldsymbol{\mathbf{r}} _1 \\
\boldsymbol{\mathbf{r}} _3 - 1 & \boldsymbol{\mathbf{r}} _1 \\
\boldsymbol{\mathbf{r}} _4 - 2 & \boldsymbol{\mathbf{r}} _1 \\
\end{aligned}
\quad \Longrightarrow \quad
\boldsymbol{\mathbf{B}} ={
\left(\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}
\right) }~
\end{equation}
发现此时，矩阵第二列自第二行以下全为零，所以需要依次向下一列寻找不为零的元素。继续消元
\begin{equation}
\begin{aligned}
& \boldsymbol{\mathbf{r}} _2 \leftrightarrow \boldsymbol{\mathbf{r}} _4 \\
& \boldsymbol{\mathbf{r}} _3 - 1 \boldsymbol{\mathbf{r}} _2 \\
& \boldsymbol{\mathbf{r}} _4 - 0 \boldsymbol{\mathbf{r}} _2 \\
\end{aligned}
\quad \Longrightarrow \quad
\boldsymbol{\mathbf{B}} ={
\left(\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}
\right) }~
\end{equation}
\begin{equation}
\boldsymbol{\mathbf{r}} _4 - 0.5 \boldsymbol{\mathbf{r}} _3
\quad \Longrightarrow \quad
\boldsymbol{\mathbf{B}} ={
\left(\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}
\right) }~
\end{equation}
我们按照上面的方法用第 3 行求 $x_4$，代入第 2 行求得 $x_3$。然而当我们想用第 1 行求 $x_1$ 的时候却出发现我们还没求出 $x_2$。解决办法是，我们令 $x_2 = c$ 且假设 $c$ 可以取任意值，再把 $x_1$ 用 $c$ 表示。方程的解可以表示为
\begin{equation}
\left\{\begin{aligned}
x_1 &= 5-c\\
x_2 &= c \\
x_3 &= 1\\
x_4 &= -1 \end{aligned}\right. ~
\end{equation}
或者写成列矢量的形式
\begin{equation}
\boldsymbol{\mathbf{x}} = c \begin{pmatrix}-1\\ 1\\ 0\\ 0\end{pmatrix} + \begin{pmatrix}5\\ 0\\ 1\\ -1\end{pmatrix} ~.
\end{equation}
将该式代入方程组，可以验证 $c$ 取任意值时方程组都成立。
如果多个 $x_i$ 的值都未知，我们就分别假设它们等于不同的任意常数 $c_i$ 即可。
2. 解的数量
根据以上步骤，当系数矩阵变为梯形矩阵后，可以用以下步骤判断解的数量：
- 若存在系数 $a_{i,j}$ 全为零的行 $i$，但是对应的常数 $y_i$ 却不为零，则方程组无解。
- 若存在 $d$ 个系数 $a_{i,j}$ 全为零的行 $i$，且对应的所有 $y_i$ 也都为零，则方程有无穷个解，且需要 $d$ 个任意常数来表示所有可能的解。
- 若不存在系数 $a_{i,j}$ 全为零的行，则系数矩阵可以化为三角矩阵，使对角线上的元素全不为零。此时方程有唯一解。
3. 解的结构
按照高斯消元法的一般步骤，如果方程有解，我们总可以将解表示为一些常矢量的线性组合加上一个常矢量。
\begin{equation}
\boldsymbol{\mathbf{x}} = \sum_{i=1}^{d} c_i \boldsymbol{\mathbf{x}} _i + \boldsymbol{\mathbf{x}} _0~.
\end{equation}
其中 $c_i$ 是 $d$ 个任意常数（当方程有唯一解时 $d = 0$），无论这些常数取什么值，$ \boldsymbol{\mathbf{x}} $ 都是方程的解。另一方面，给出方程的任意一个解，总能找到一些常数 $c_i$ 与之对应。
式 18 叫做方程的
通解（general solution），通解中的任意一个就做方程的
特解（special solution）。
将式 18 代入方程组，使用矩阵乘法分配律（式 17 ）得到
\begin{equation}
\boldsymbol{\mathbf{A}} \sum_{i=1}^{d} c_i \boldsymbol{\mathbf{x}} _i + \boldsymbol{\mathbf{A}} \boldsymbol{\mathbf{x}} _0 = \boldsymbol{\mathbf{y}} ~,
\end{equation}
由于 $ \boldsymbol{\mathbf{x}} _0$ 是方程的一个特解，有 $ \boldsymbol{\mathbf{A}} \boldsymbol{\mathbf{x}} _0 = \boldsymbol{\mathbf{y}} $。所以
\begin{equation}
\boldsymbol{\mathbf{A}} \sum_{i=1}^{d} c_i \boldsymbol{\mathbf{x}} _i = \boldsymbol{\mathbf{0}} ~.
\end{equation}
线性方程组 $ \boldsymbol{\mathbf{A}} \boldsymbol{\mathbf{x}} = \boldsymbol{\mathbf{y}} $ 中，如果 $ \boldsymbol{\mathbf{y}} = \boldsymbol{\mathbf{0}} $（粗体的 $ \boldsymbol{\mathbf{0}} $ 表示零矢量，即每个元都是 $0$），则方程组被称为是
齐次（homogeneous）的。上式说明 $\sum_{i} c_i \boldsymbol{\mathbf{x}} _i$ 就是齐次方程组 $ \boldsymbol{\mathbf{A}} \boldsymbol{\mathbf{x}} = \boldsymbol{\mathbf{0}} $ 的通解。
综上所述，对于任意有解的非齐次（inhomogeneous）方程组 $ \boldsymbol{\mathbf{A}} \boldsymbol{\mathbf{x}} = \boldsymbol{\mathbf{y}} $，我们可以将通解（式 18 ）从形式上理解为齐次方程组 $ \boldsymbol{\mathbf{A}} \boldsymbol{\mathbf{x}} = \boldsymbol{\mathbf{0}} $ 的通解与非齐次方程组的任一特解相加。
1. ^ 参考 Wikipedia 相关页面。
2. ^ 这点我们留到以后证明
3. ^ 为了书写简单，我们将每次变换后的系数矩阵元仍然用 $a_{i,j}$ 来表示，虽然它的值可能已经发生变化。若需要区分，可以将第 $n$ 次变换后的矩阵元用 $a_{i,j}^{(n)}$ 表示。
4. ^ 如果 $a_{1,1} \ne 0$ 则不需要
5. ^ 如果在处理 $i = m-1$ 之前就得到了梯形矩阵，则可提前终止。
致读者： 小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此，我们请求广大读者
热心打赏 ，使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损， 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款， 他们的付出帮助了 99% 的读者免费获取知识， 我们在此表示感谢。