线性方程组

<image>

线性方程组是数学方程组的一种，它符合以下的形式：

$$\begin{cases}a_{1,1}x_{1} + a_{1,2}x_{2} + \cdots + a_{1,n}x_{n}= b_{1} \\ <pre> a_{2,1}x_{1} + a_{2,2}x_{2} + \cdots + a_{2,n}x_{n}= b_{2} \\ \vdots \quad \quad \quad \vdots \\ a_{m,1}x_{1} + a_{m,2}x_{2} + \cdots + a_{m,n}x_{n}= b_{m} \end{cases}$$

其中的 $a_{1,1}, \, a_{1,2}$ 以及 $b_{1}, \, b_{2}$ 等等是已知的常数，而 $x_{1}, \, x_{2}$ 等等则是要求的未知数。

如果用线性代数中的概念来表达，则线性方程组可以写成：

$$\mathbf{A} \mathbf{x} = \mathbf{b}$$

这里的 $\mathbf A$ 是 $m\times n$ 矩阵，$\mathbf x$ 是含有 $n$ 个元素列向量，$\mathbf b$ 是含有 $m$ 个元素列向量。

$$\mathbf A= \begin{bmatrix} 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{bmatrix},\quad \mathbf{x}= \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix},\quad \mathbf{b}= \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{bmatrix}$$

这是线性方程组的另一种记录方法。在已知矩阵 $\mathbf A$ 和向量 $\mathbf{b}$ 的情况求得未知向量 $\mathbf{x}$ 是线性代数的基本问题之一。

## 例子

以下是一个由两个方程构成的线性方程组：

$$\begin{cases}3x_{1} + 5x_{2} = 4 \\ <pre> x_{1} + 2x_{2} = 1 \end{cases}$$

方程组中有两个未知数。以矩阵表示，这个方程组可以记录为：

$$\begin{bmatrix} 3 & 5\\ 1 & 2 \end{bmatrix} \cdot \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 4 \\ 1 \end{bmatrix}$$

这个线性方程组有一组解：$x_1 = 3, \, x_2 = -1$。可以直接验证：

$$\begin{cases}3 \times 3 + 5 \times (-1) = 9 - 5 = 4 \\ <pre> 3 + 2 \times (-1) = 3 -2 = 1 \end{cases}$$

可以证明，这组解也是方程组唯一的解。

不是所有的线性方程组都有解。以下是一个没有解的例子：

$$\begin{cases}x_{1} + x_{2} = 2\\ <pre> 2x_{1} + 2x_{2} = 1 \end{cases}$$

显然，如果有 $x_1$ 和 $x_2$ 满足了第一行的式子的话，它们的和等于 2。而第二行则要求它们的和等于 0.5，这不可能。

也有的线性方程组有不止一组解。例如：

$$\begin{cases}x_{1} + x_{2} = 2 <pre> \end{cases}$$

$x_1 = 1, \, x_2 = 1$ 是一组解，而 $x_1 = 3, \, x_2 = -1$ 也是一组解。事实上，解的个数有无限个。

## 线性方程组的解

<image>

如果有一组数 $x_1, x_2, \cdots, x_n$ 使得方程组的等号都成立，那么这组数就叫做方程组的解。一个线性方程组的所有的解的集合会被简称为解集。根据解的存在情况，线性方程组可以分为三类：

- 有唯一解的恰定方程组。
- 解不存在的超定方程组。
- 有无穷多解的欠定方程组（也被通俗地称为不定方程组）。

### 几何解释

当未知数只有两个（x和y）的时候，方程组里面的每一个方程可以看成 Oxy平面（正交直角坐标系）上的一条直线的方程。直线上的点的坐标就是满足这个方程的一组数。从这个角度看来，方程组的解就是所有这种直线的公共点。而若干条直线的公共部分要么是一条直线，要么是一个点，要么是空集，因此对应的，线性方程组的解要么有无穷个，要么恰好有一个，要么不存在。

如果未知数有三个，那么每一个方程则代表了三维空间里面的一个平面，而方程组的解集也就是一些平面的共同部分。所有解的集合可以对应一个平面，一条直线，一个点或空集。

这个问题的一般情况可以从线性空间的角度去分析，即我们可以将线性方程组的求解问题看成向量 $\mathbf{b}$ 在矩阵 $\mathbf A$ 所张成的线性空间里面的投影的问题。未知数的个数如果是一般的n个的话，可以想象每个方程代表了n维空间里面的一个超平面。而方程组的解就是所有超平面的公共点。

### 齐次线性方程组

齐次的线性方程组是指向量 $\mathbf{b}=\mathbf 0$ 的情况。这时候方程变成：

$\mathbf A \mathbf{x}=\mathbf 0$ 这个方程肯定会有一组解：$\mathbf{x}=\mathbf 0$。实际上，方程的解就是矩阵$\mathbf A$对应的线性变换的零空间。一般来说，当方程的个数小于未知数的个数时，方程组会有除 $\mathbf{x}=\mathbf 0$ 以外的解。当方程组个数变多时，则要看其中“有效”的方程的个数。有时候某一个方程可以表示成另外几个方程的线性组合。比如方程组：

$\begin{cases}3x_{1} + x_{2} + 2 x_{3} = 0 \\ <pre> x_{1} - x_{2} + 4 x_{3} = 0\\ 2x_{1} + 3x_{3} = 0 \end{cases}$

之中，第三个方程就可以表示为前两个方程的线性组合：

$2x_{1} + 3x_{3} = \frac{1}{2}(3x_{1} + x_{2} + 2 x_{3}) + \frac{1}{2}(x_{1} - x_{2} + 4 x_{3})$ 这时第三个方程组就可以不必考虑了。用线性代数的词汇表达，“有效”的方程的个数就是矩阵 $\mathbf A$ 中线性无关的行向量的个数，或者说行向量线性张成的空间的维数。这个数也被称为矩阵的秩。当矩阵 $\mathbf A$ 的秩 $r$ 小于未知数的个数$n$时，方程组的解会有无穷多个，构成一个 $n-r$ 维的线性空间。而当 $r$ 等于未知数的个数 $n$ 时，方程组有唯一零解，$r$ 不可能大于 $n$。

### 松弛求解

在实验数据处理和曲线拟合问题中，求解超定方程组非常普遍。这时常常需要退一步，将线性方程组的求解问题改变为求最小误差的问题。形象的说，就是在无法完全满足给定的这些条件的情况下，求一个最接近的解。比较常用的方法是最小二乘法。最小二乘法求解超定问题等价于一个优化问题，或者说最小值问题，即，在不存在$\mathbf{x}$使得$\mathbf{b} -\mathbf A \mathbf{x} = \mathbf 0$的情况下，我们试图找到这样的$\mathbf{x}$使得$\left| \mathbf{b} - \mathbf A \mathbf{x} \right|$最小，其中$\left| \cdot \right|$表示范数。

## 求解

### 克莱姆法则

基于线性方程组的解空间理论，线性方程组有唯一解当且仅当有效方程数等于未知数的个数。这时，可以运用各种方法具体求出唯一存在的解。克莱姆法则是一种求解线性方程组的方法，大多数线性代数教材都会提到。例如对于如下的线性方程组：

$\begin{cases}a_1 x + b_1 y = c_1 \\ a_2 x + b_2 y = c_2 \end{cases}$

运用克莱姆法则，这个方程组的解可以如下：

$x = \frac{D_x}{D}, \qquad y = \frac{D_y}{D}$

其中，$D_x, D_y, D$分别是如下三个行列式：

$D = \left| \begin{matrix} a_1 & b_1 \\ a_2 & b_2 \end{matrix} \right| ,$ $D_x = \left| \begin{matrix} c_1 & b_1 \\ c_2 & b_2 \end{matrix} \right| ,$ $D_y = \left| \begin{matrix} a_1 & c_1 \\ a_2 & c_2 \end{matrix} \right|$

对于更一般的情况：

$$\mathbf{A} \mathbf{x} = \mathbf{b}$$

解可以由同样的公式给出：

$\begin{cases}x_1 = \frac{D_1}{D} \\ <pre> x_2 = \frac{D_2}{D} \\ \vdots \qquad \vdots \\ x_n = \frac{D_n}{D}\end{cases}$

其中的

$$D = \det (\mathbf A)$$

$$\forall 1 \leqslant i \leqslant n, \, \, D_i = \det (\mathbf{A_i})$$

$\mathbf{A_i}$是将矩阵$\mathbf A$的第i纵列换成向量b之后得到的矩阵。

可以看出，这些表达式只有在$D = \det (\mathbf A)$存在并且不等于0的时候才是有意义的，这点只有在有效方程数等于未知数的个数的时候才能得到保证。

### 数值方法

在实际运算中，当矩阵的维数较高时，计算行列式是非常繁复的。也就是说，计算行列式的计算复杂度随维数的增长非常快，对于一个$n \times n$的矩阵，用初等的方法计算其行列式，需要的计算时间是$O(n!)$（n的阶乘）。因此，克莱姆法则在现实问题求解几乎不会被采用，而其重要性在于证明某些线性问题的解答会自然而然是整数解答，因而存在有效率的解法。换言之，克莱姆法则的重要性是在于理论证明的应用，而非问题的实际求解。

经典的求解线性方程组的方法一般分为两类：直接法和迭代法。前者例如高斯消去法, LU分解等，后者的例子包括共轭梯度法等。这些方法的计算复杂度在可以接受的范围内，因此被广泛采用。例如，高斯消去法的复杂度为$O(n^3)$ 一般来说，直接法对于阶数比较低的方程组（少于20000至30000个未知数）比较有效；而后者对于比较大的方程组更有效。在实际计算中，几十万甚至几百万个未知数的方程组并不少见。在这些情况下，迭代法有无可比拟的优势。另外，使用迭代法可以根据不同的精度要求选择终止时间，因此比较灵活。在问题特别大的时候，计算机内存可能无法容纳被操作的矩阵，这给直接法带来很大的挑战。而对于迭代法，则可以将矩阵的某一部分读入内存进行操作，然后再操作另外部分。

## 应用

现实中的问题大多数是连续的，例如工程中求解结构受力后的变形，空气动力学中计算机翼周围的流场，气象预报中计算大气的流动。这些现象大多是用若干个微分方程描述。用数值方法求解微分方程（组），不论是差分方法还是有限元方法，通常都是通过对微分方程（连续的问题，未知数的维数是无限的）进行离散，得到线性方程组（离散问题，因为未知数的维数是有限的）。因此线性方程组的求解在科学与工程中的应用非常广泛。

许多具体的应用会得到结构比较特别的线性方程组，比如用差分方法和有限元方法离散微分方程后通常会得到三对角或五对角的方程组，网络问题有时会得到对称的线性方程组（$\mathbf A = \mathbf A^T$），因此除了通用的线性方程组求解器，在一些专业领域，研究人员们也开发了适用于特定问题的求解器，比如适用于稀疏矩阵的求解器，适用于三对角矩阵的求解器，适用于对称矩阵的求解器等。

## 相关软件

由于线性方程组的求解是一个非常普遍的问题，在多年的科学与工程实践中，科学家和工程师们积累很多高效率的线性方程组求解器，例如：LAPACK、BLAS等。这些软件中，许多可以可以在 NetLib 免费获得。LAPACK和BLAS在大多数Linux的发行版本中都已经预装。目前LAPACK有Fortran（包括90和77版本）、C、C++等几个语言的版本。利用LAPACK和BLAS中的子程序， Matlab 对这些线性方程组求解器进行封装。用户不需要选择求解器的类型和问题的类型，Matlab可以根据对矩阵的分析自动选择合适的求解器。

## 其他方法与软件

上面讲的是线性方程组的数值解法。对于比较小的线性方程组，求得符号解是可能的。常用的软件有Mathematica, Maple等。在某些领域的研究中，这种需要并且可能求符号解（精确解）的情况偶尔会遇到。未知数的个数一般限制在几十个左右。显然，符号解在对于实际中遇到的有几百万个未知数的问题是无能为力的，比如，大型结构，天气预报，湍流模拟等问题中得到的线性方程组。

## 外部链接

- Mathway，使用电脑解决绝大部分的数学问题。
- Simultaneous Linear Equations Calculator，一个简单的线性方程组求解器