线性方程组

高斯消元法

客观世界最简单的数量关系是均匀变化的关系。在均匀变化问题中，列出的方程组是一次方程组，我们称之为线性方程组(Linear system of equations)。$n$元线性方程组的一般形式为
$$\{\begin{array}{l}{a}_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n=b_1\\ a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n=b_2\\ \cdots \cdots \\ a_{m1}{x}_1+a_{m2}{x}_2+\cdots +a_{mn}{x}_n=b_m\end{array}$$
如果存在$n$个常数 $x_1=s_1,x_2=s_2,\cdots ,x_n=s_n$ 满足线性方程组的所有方程，则称为线性方程组的一个解(solution)。方程组的所有解组成的集合称为这个方程组的解集。

解线性方程组的一般方法，是把方程组用一个更容易解的等价方程组 (即有相同解集的方程组)代替。用来化简线性方程组的三种基本变换是：

(1) 互换两个方程的位置；
(2) 把某一个方程的所有项乘以一个非零常数；
(3) 把某一个方程加上另一个方程的常数倍；

以上三种变换称为高斯消元法(Gaussian Elimination)。

例如，解方程组
$$\{\begin{array}{l}\begin{array}{rlrl}& 2x_2& -x_3& =7\\ x_1& +x_2& +2x_3& =0\\ x_1& +x_2& -x_3& =-6\\ x_1& +3x_2& -2x_3& =1\end{array}\end{array}$$
经过基本变换把线性方程组化成阶梯形方程组
$$\{\begin{array}{l}\begin{array}{rlrl}{x}_1& +x_2& -x_3& =-6\\ & 2x_2& -x_3& =7\\ & & 3x_3& =6\\ & & 0& =0\end{array}\end{array}$$
还可以进一步变换为简化阶梯形方程组
$$\{\begin{array}{llcc}{x}_1& & & =-9\\ & x_2& & =5\\ & & x_3& =2\\ & & 0& =0\end{array}$$
上面的简单例子代表了用消元法解线性方程组的一般方法和计算格式。

初等行变换

根据矩阵与向量的乘法定义，线性方程组可写为矩阵形式
$$A\mathbf{x}=\mathbf{b}$$
其中
$$A=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}\end{array}\right],\mathbf{x}=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right],\mathbf{b}=\left[\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_n\end{array}\right]$$
矩阵 $A$ 称为系数矩阵， $\mathbf{x}$ 为未知数向量，$\mathbf{b}$ 为常数向量。

从上节求解线性方程组的过程中，不难发现，只是对线性方程组的系数和常数项进行了运算。因此，线性方程组可以用它的系数和常数项来求解。

为求解方便，把常数向量添加到系数矩阵最后一列，构成的矩阵
$$\bar{A}=[A\mid b]=\left[\begin{array}{c}\begin{array}{cccc}{a}_{11}& \cdots & a_{1n}& b_1\\ a_{21}& \cdots & a_{2n}& b_2\\ ⋮& ⋮& \ddots & ⋮\\ a_{m1}& \cdots & a_{mn}& b_m\end{array}\end{array}\right]$$
称为方程组的增广矩阵(augmented matrix)。

初等行变换：上节所讲的三种基本变换对应于矩阵的下列变换：

(1) 行互换变换：对调矩阵的第$i$行和第$j$行 ，记为 $r_i\leftrightarrow r_j$
(2) 行倍乘变换：矩阵的第$i$行乘以非零常数$k$，记为 $k{r}_i$
(3) 行倍加变换：将第$j$行的元素倍加到第$i$行，记作 $r_i+k{r}_j$

称为矩阵的初等行变换(elementary row transformation)。

矩阵消元法：在解线性方程组时，把它的增广矩阵经过初等行变换化成行阶梯形矩阵，写出相应的阶梯形方程组 ，进行求解；或者一直化成简化行阶梯形矩阵，写出它表示的简化阶梯形方程组，从而立即得出解。

上节例子中，增广矩阵经过初等行变换可简化为
$$\bar{A}=\left[\begin{array}{c}\begin{array}{cccc}0& 2& -1& 7\\ 1& 1& 2& 0\\ 1& 1& -1& -6\\ 1& 3& -2& 1\end{array}\end{array}\right]\to \left[\begin{array}{c}\begin{array}{cccc}1& 1& -1& -6\\ 0& 2& -1& 7\\ 0& 0& 3& 6\\ 0& 0& 0& 0\end{array}\end{array}\right]=B_1$$
称形如 $B_1$ 的矩阵为行阶梯形矩阵(Row Echelon Form，REF)。其特点是：

(1) 若有零行(元素全为零的行)，零行均在非零行的下方；
(2) 非零行第一个非零元素(称为主元，pivot)以下的元素全为零。

使用初等行变换对行阶梯形矩阵进一步化简
$$B_1=\left[\begin{array}{c}\begin{array}{cccc}1& 1& -1& -6\\ 0& 2& -1& 7\\ 0& 0& 3& 6\\ 0& 0& 0& 0\end{array}\end{array}\right]\to \left[\begin{array}{c}\begin{array}{cccc}1& 0& 0& -9\\ 0& 1& 0& 5\\ 0& 0& 1& 2\\ 0& 0& 0& 0\end{array}\end{array}\right]=B_2$$
称形如 $B_2$ 的矩阵为简化行阶梯形矩阵(Reduced Row Echelon Form，RREF)。其特点是：

(1) 每个非零行主元都是1；
(2) 主元所在列的其他元素都是零。

通过简化行阶梯形矩阵，我们可以直接写出解 $x_1=-9,x_2=5,x_3=2$。

使用矩阵消元法，我们可以知道任何矩阵都可以经过有限次初等行变换化成行阶梯形矩阵，任何矩阵也可进一步化成简化行阶梯形矩阵。

从最后的简化行阶梯形矩阵可以直接写出一般解，但注意把自由变量的系数变号移到等式右边。

线性方程组的解

假设某方程组的增广矩阵行已变换为阶梯形矩阵
$$\left[\begin{array}{c}\begin{array}{cccc}1& 0& -5& 1\\ 0& 1& 1& 4\\ 0& 0& 0& 0\end{array}\end{array}\right]$$
对应的线性方程组是
$$\{\begin{array}{l}\begin{array}{rlrl}{x}_1& & -5x_3& =1\\ & x_2& +x_3& =4\\ & & 0& =0\end{array}\end{array}$$
方程组的解可显示表示为 $x_1=1+5x_3,x_2=4-x_3$ ，显然有无穷多组解。

把 $n$ 元线性方程组的增广矩阵化成行阶梯形矩阵后，若有 $r$ 个非零行，则行阶梯形矩阵有 $r$ 个主元。以主元为系数的末知量称为主变量，剩下的 $n-r$ 个未知量称为自由变量，其值可任取。

假设某方程组的增广矩阵行已变换为阶梯形矩阵
$$\left[\begin{array}{c}\begin{array}{cccc}2& -3& 2& 1\\ 0& 1& -4& 8\\ 0& 0& 0& 15\end{array}\end{array}\right]$$
对应的线性方程组是
$$\{\begin{array}{l}\begin{array}{rlrl}2x_1& -3x_2& +2x_3& =1\\ & x_2& -4x_3& =8\\ & & 0& =15\end{array}\end{array}$$
这个阶梯形方程组显然是矛盾的，故原方程组无解。

解的情况：线性方程组有解的充要条件是增广矩阵的增广列不是主元列，即行阶梯形方程组不包含矛盾方程。若线性方程组有解，则解有两种情况：(1) 当没有自由变量时，有唯 一解；(2) 当有自由变量是，有无穷多解。

向量方程

应用向量加法和数乘运算，线性方程组 $A\mathbf{x}=\mathbf{b}$ 可以写成向量方程
$$x_1{\mathbf{a}}_1+x_2{\mathbf{a}}_2+\cdots +x_n{\mathbf{a}}_n=\mathbf{b}$$
其中 ${\mathbf{a}}_1,{\mathbf{a}}_2,\cdots ,{\mathbf{a}}_n$ 为系数矩阵 $A$ 的列向量组，$\mathbf{b}$ 为常数向量。它的一组解 $s=(x_1,x_2,\cdots ,x_n{)}^T$ 称为方程组的解向量。

例如，方程组
$$\{\begin{array}{l}\begin{array}{rlrl}2x_1& -x_2& +x_3& =4\\ 4x_1& +2x_2& -x_3& =-1\end{array}\end{array}$$
可以表述为
$$\left[\begin{array}{c}2\\ 4\end{array}\right]x_1+\left[\begin{array}{c}-1\\ 2\end{array}\right]x_2+\left[\begin{array}{c}1\\ -1\end{array}\right]x_3=\left[\begin{array}{c}4\\ -1\end{array}\right]$$
既然可表示为向量的形式，那么就可以从向量的角度分析。向量方程是否有解的问题等价于判断常数向量 $\mathbf{b}$ 能否由系数矩阵列向量组线性表示，即向量 $\mathbf{b}$ 是否属于系数矩阵的列空间 col  A = span { a 1 , a 2 , ⋯ , a n } \text{col }A=\text{span}\{\mathbf a_1,\mathbf a_2,\cdots,\mathbf a_n\} col A=span{a1​,a2​,⋯,an​}。

结论：方程 $A\mathbf{x}=\mathbf{b}$有解的充要条件是 $\mathbf{b}$ 是 $A$ 的各列的线性组合。

以线性变换的角度理解，希望找出未知向量 $\mathbf{x}$ ，使得该向量在线性变换 $A$ 的作用下变成已知向量 $\mathbf{b}$。因此，我们可以从逆变换的角度获得未知向量。显然，如果变换后维度压缩，方程不一定有解。即列空间的维度低于未知向量维度。

齐次线性方程组的解

常数项都为零的线性方程组 $A\mathbf{x}=0$ 称为齐次线性方程组。向量方程为
$$x_1{\mathbf{a}}_1+x_2{\mathbf{a}}_2+\cdots +x_n{\mathbf{a}}_n=0$$

齐次线性方程组显然有一组解
$$x_1=x_2=\cdots =x_n=0$$
这组解称为零解或平凡解。除此之外的其他解称为非零解或非平凡解。

方程 $A_{m\times n}\mathbf{x}=0$ 有非零解等价于 $A$ 的列向量组线性相关，即 $\text{rank}(A)<n$

齐次线性方程组的解有如下性质

1. 如果 $s_1,s_2$ 是齐次线性方程组的两个解向量，则 $s_1+s_2$ 也是方程组的解向量。
2. 如果 $s$ 是齐次线性方程组的解向量，则对任意常数$k$， $ks$ 也是方程组的解向量。

这两条性质只要直接代入向量方程进行验证就可以。

显然，系数矩阵为 $A$ 的齐次线性方程组的解集
ker ⁡ A = { x ∣ A x = 0 } \ker A=\{\mathbf x|A\mathbf{x}=0\} kerA={x∣Ax=0}
满足向量空间的条件， 称为零空间(nullspace)或核(kernel)。解空间的一组基 $s_1,s_2,\cdots ,s_{n-r}$ 称为该方程组的基础解系。零空间的维数即为自由变量的个数。

如果能找到基础解系，就能描述整个解空间。

定理：

1. 方程 $A_{m\times n}\mathbf{x}=0$ 有非零解的充要条件是 $\text{rank}(A)<n$。
2. 方程 $A_{m\times n}\mathbf{x}=0$ 基础解系中自由变量的个数等于 $n-\text{rank}(A)$。
3. 设 $A$ 是向量空间 $V$ 内的线性变换

$$\dim V=\dim (\text{range }A)+\dim (\ker A)$$

可以用系数矩阵的初等行变换来求基础解系。

示例：求下列齐次线性方程组的解集。
$$\{\begin{array}{l}{x}_2-x_3+x_4-x_5=0\\ x_1+x_3+2x_4-x_5=0\\ x_1+x_2+3x_4-2x_5=0\\ 2x_1+2x_2+6x_4-3x_5=0\end{array}$$
解：先做矩阵消元法获得阶梯形矩阵和简化阶梯形矩阵
$$A=\left[\begin{array}{ccccc}0& 1& -1& 1& -1\\ 1& 0& 1& 2& -1\\ 1& 1& 0& 3& -2\\ 2& 2& 0& 6& -3\end{array}\right]\to \left[\begin{array}{ccccc}1& 0& 1& 2& -1\\ 0& 1& -1& 1& -1\\ 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 0\end{array}\right]\to \left[\begin{array}{ccccc}1& 0& 1& 2& 0\\ 0& 1& -1& 1& 0\\ 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 0\end{array}\right]$$
因此
$$\{\begin{array}{l}{x}_1=-x_3-2x_4\\ x_2=x_3-x_4\\ x_5=0\end{array}$$
可写为解向量的形式
$$\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\\ x_5\end{array}\right]=x_3\left[\begin{array}{c}-1\\ 1\\ 1\\ 0\\ 0\end{array}\right]+x_4\left[\begin{array}{c}-2\\ -1\\ 0\\ 1\\ 0\end{array}\right]$$

非齐次线性方程组的解

对于非齐次线性方程组 $A\mathbf{x}=0$ 。判断向量方程 $x_1{\mathbf{a}}_1+x_2{\mathbf{a}}_2+\cdots +x_n{\mathbf{a}}_n=\mathbf{b}$ 是否有解，等价于判断常数向量 $\mathbf{b}$ 是否属于 span { a 1 , a 2 , ⋯ , a n } \text{span}\{\mathbf a_1,\mathbf a_2,\cdots,\mathbf a_n\} span{a1​,a2​,⋯,an​}。

判别定理：线性方程组有解的充要条件是其系数矩阵$A$与增广矩阵$\bar{A}$的秩相等 $\text{rank}(A)=\text{rank}(\bar{A})$。

通俗理解就是，变换后的阶梯形方程组不存在 $0=b$ 的矛盾方程。

解的结构：设 $n$ 元非齐次线性方程组 $\text{rank}(A)=\text{rank}(\bar{A})$

(1) 若 $\text{rank}(A)=n$，方程组有唯一解；
(2) 若 $\text{rank}(A)<n$，方程组有无穷多解。

非齐次线性方程组 $A\mathbf{x}=\mathbf{b}$ 对应的齐次线性方程组 $A\mathbf{x}=0$ 称为导出方程组。解的关系：

1. $A\mathbf{x}=\mathbf{b}$ 的任意两个解向量之差是 $A\mathbf{x}=0$ 的一个解向量；
2. $A\mathbf{x}=\mathbf{b}$ 的通解是其任一解向量与 $A\mathbf{x}=\mathbf{b}$ 通解之和。

如下图

示例：求下列线性方程组的全部解

$$\{\begin{array}{l}\begin{array}{rlrl}{x}_1& +4x_2& -5x_3& =0\\ 2x_1& -x_2& +8x_3& =9\end{array}\end{array}$$
解：对方程组的增广矩阵做初等行变换获得阶梯形矩阵和简化阶梯形矩阵
$$\bar{A}=\left[\begin{array}{c}\begin{array}{cccc}1& 4& -5& 0\\ 2& -1& 8& 9\end{array}\end{array}\right]\to \left[\begin{array}{c}\begin{array}{cccc}1& 4& -5& 0\\ 0& -9& 18& 9\end{array}\end{array}\right]\to \left[\begin{array}{c}\begin{array}{cccc}1& 0& 3& 4\\ 0& 1& -2& 1\end{array}\end{array}\right]$$
因此
$$\{\begin{array}{l}{x}_1=4-3x_3\\ x_2=1+2x_3\end{array}$$
解向量的形式为
$$\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]=\left[\begin{array}{c}4\\ 1\\ 0\end{array}\right]+x_3\left[\begin{array}{c}-3\\ 2\\ 1\end{array}\right]$$