线性方程组

维基百科,自由的百科全书
跳转至: 导航搜索
线性代数
\mathbf{A} = \begin{bmatrix}
1 & 2 \\
3 & 4 \end{bmatrix}
向量 · 矩阵  · 行列式  · 线性空间
三變量的線性系統確定了一組平面。交點就是解。

在数学中,线性方程组方程组的一种,它符合以下的形式:

 \begin{cases}a_{1,1}x_{1} + a_{1,2}x_{2} + \cdots + a_{1,n}x_{n}=  b_{1} \\
                     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}

這里的Am×n 矩陣x是含有n个元素列向量b是含有m 个元素列向量。


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

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

例子[编辑]

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

 \begin{cases}3x_{1} + 5x_{2} =  4 \\
                      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 \\
                     3 + 2 \times  (-1) =  3 -2 = 1  \end{cases}

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

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

 \begin{cases}x_{1} + x_{2} =  2\\
                     2x_{1} + 2x_{2} =  1  \end{cases}

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

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

 \begin{cases}x_{1} + x_{2} =  2
                       \end{cases}

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

线性方程组的解[编辑]

方程组的解是所有直线的公共点

如果有一组数x1x2、……xn使得方程组两边的等号都成立,那么这组数就叫做方程组的解。一个线性方程组的所有的解的集合会被简称为解集。根据解的存在情况,线性方程组可以分为三类:

  • 有唯一解的恰定方程组,
  • 解不存在的超定方程组,
  • 有无穷多解的欠定方程组(也被通俗地称为不定方程组)。

几何解释[编辑]

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

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

一般情况[编辑]

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

齐次线性方程组[编辑]

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

A \mathbf{x}=0

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

 \begin{cases}3x_{1} + x_{2} + 2 x_{3} =  0 \\
                      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})

这时第三个方程组就可以不必考虑了。用线性代数的词汇表达,“有效”的方程的个数就是矩阵A中线性无关的行向量的个数,或者说行向量线性张成的空间的维数。这个数也被称为矩阵的秩。当矩阵A的秩r小于未知数的个数n时,方程组的解会有无穷多个,构成一个n-r维的线性空间。而当r等于未知数的个数n时,方程组有唯一解,而当r大于未知数的个数n时,方程组只会有零解。

松弛求解[编辑]

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

其中的

 D = \det (A) ,
 \forall 1 \leqslant i \leqslant n, \, \, D_i = \det (A_i) ,

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

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

数值方法[编辑]

在实际运算中,当矩阵的维数较高时,计算行列式是非常困难的。也就是说,计算行列式的计算复杂度随维数的增长非常快,对于一个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可以根据对矩阵的分析自动选择合适的求解器。

其他方法与软件[编辑]

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

参见[编辑]

参考文献[编辑]

外部連結[编辑]