线性方程组求解

维库，知识与思想的自由文库

线性方程组的求解是线性代数的一个基本问题之一. 简单地说,求解线性方程组就是对如下方程组

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

在已知矩阵 $A$ 和矢量 $\mathbf{b}$ 的情况下，求得未知向量 $\mathbf{x}$ 的过程。

[编辑] 问题的分类

根据解的存在情况，线性方程可以分为恰定方程组（有唯一解），超定方程组（解不存在），和欠定方程组（有无穷多解）。这个问题当然可以从线性空间的角度去分析，即我们可以将线性方程组的求解问题看成矢量 $\mathbf{b}$ 在矩阵 $A$ 所张成的线性空间里面的投影的问题。但是，对于初学者，一个比较形象的解释是，如果我们已知不重合的两个点，要求经过这两点的一条直线，那么我们可以唯一的确定这条直线。如果给定三个点，并且这三个点正好在一个直线上，这条直线仍然可以唯一确定。上面两种情况对应恰定问题。如果给定的三点不在一条直线上，我们将无法得到这样一条直线，使得这条直线同时经过给定这三个点。这对应上面所说的超定问题。也就是说给定的条件（限制)过于严格，导致解不存在。最后，如果只给定一个点，显然这条直线有无穷多种可能，这对应于上面说的欠定问题。在实验数据处理和曲线拟合问题中，求解超定方程组非常普遍。比较常用的方法是最小二乘法。形象的说，就是在无法完全满足给定的这些条件的情况下，求一个最接近的解。最小二乘法求解超定问题等价于一个优化问题，或者说最小值问题, 即，再不存在 $\mathbf{x}$ 使得 $\mathbf{b} - A \mathbf{x} = 0$ 的情况下，我们试图找到这样的 $\mathbf{x}$ 使得 $\left| \mathbf{b} - A \mathbf{x} \right|$ 最小，其中 $\left| \cdot \right|$ 表示范数。

[编辑] 数值方法

克萊姆法則是一种求解线性方程组的方法, 在大多数线性代数教材里都会被提到。例如对于如下的线性方程组：

$a 1 x + b 1 y = c 1$

$a 2 x + b 2 y = c 2$

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

$x = \frac{D_x}{D}$

$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|$

然而，在矩阵的维数较高时，计算行列式是非常困难的。也就是说，计算行列式的计算复杂度随维数的增长非常快，对于一个 $n \times n$ 的矩阵，用初等的方法计算其行列式，需要的计算时间是 $O (n!)$ （n的阶乘）。因此，克莱姆法则在实际计算中并未被采用。其意义仅仅在于出现在教材上，用以说明好的数值方法的重要性。

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

[编辑] 应用

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

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

[编辑] 相关软件

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

[编辑] 其他方法与软件

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