第二章 线性方程组的直接方法(1)

2.1 顺序高斯消去法

很多工程实际问题最终都可以归结为求解线性方程组。如：

• 用最小二乘法求实验数据的曲线拟合问题

• 工程中的三次样条函数的插值问题

• 经济运行中的投入产出问题

• 大地测量、机械与建筑结构的设计计算问题

这些问题都可以归结为求解线性方程组或者非线性方程组的数学问题。

本节讨论$n$元线性方程组的直接解法

$\begin{cases} a_{11}x_1 + a_{12}x_2+...+a_{1n}x_{n}=b_1 \\ a_{21}x_1 + a_{22}x_2+...+a_{2n}x_{n}=b_2 \\...............................\\ a_{n1}x_1 + a_{n2}x_2+...+a_{nn}x_{n}=b_n \end{cases}$

矩阵形式为$Ax=b$，为

$A = \left[\begin{matrix} a_{11} & a_{12} & a_{13} & a_{1n} \\ a_{21} & a_{22} & ... & a_{2n} \\ ... & ... & ... & ... \\ a_{n1} & a_{n2} & ... & a_{nn}\end{matrix}\right] , x=\left[\begin{matrix}x_1\\x_2\\...\\x_n \end{matrix}\right],b=\left[\begin{matrix}b_1\\b_2\\...\\b_n \end{matrix}\right]$

根据线性代数知识我们知道，这个矩阵有唯一解的条件是$det(A)\not =0$

求解线性方程组的直接方法：如果不考虑计算过程当中的舍入误差，经过有限次算数运算就可以得到方程组的精确解。

但是我们知道，我们的研究方法都要拿到计算机上实现，舍入误差是不可避免地。上讲提到的Cramer法则就是一种直接方法，但是它并不实用。如果用Cramer法则去计算线性方程组的话，计算量非常大。

接下来介绍几种实用的直接方法。

Gauss消去法

它是一种规则化的加减消元法，它的基本思想是通过逐次消元计算，把一个一般的线性方程组的求解问题转化为等效的上三角方程组的求解问题。

简单示例

$\begin{cases} 2x_1+4x_2-2x_3=2 \\ x_1-3x_2-3x_3=-1\\4x_1+2x_2+2x_3=3 \end{cases}$

消去后面两式$x_1$得

$\begin{cases} 2x_1+4x_2-2x_3=2 \\ -5x_2-2x_3=-2\\-6x_2+6x_3=-1 \end{cases}$

消去第三个方程中的$x_2$，得

$\begin{cases} 2x_1+4x_2-2x_3=2 \\ -5x_2-2x_3=-2\\\frac{42}{5}x_3=\frac{7}{5} \end{cases}$

这个时候方程已经变成一个上三角形式的方程组，所以我们通过回代求解出$x_1，x_2，x_3$，得

$x_3 = \frac{1}{6}, x_2 = \frac{1}{3},x_1 = \frac{1}{2}$

这就是顺序高斯消元法的基本思想，先逐次消元，然后回代求解。

下面用矩阵形式来将刚刚的消元过程表示，需要注意的是，上面的消元过程是对增广矩阵来进行的，而不是系数矩阵。

$(A,b) = \left[\begin{array}{ccc|c} 2 & 4 & -2 & 2 \\ 1 & -3 & -3 & -1 \\ 4 & 2 & 2 & 3\end{array}\right]$

消去后面两行中的第一列，$r_2 -\frac{1}{2}r_1, r_3 -2r_1$得

$\left[\begin{array}{ccc|c} 2 & 4 & -2 & 2 \\ 0 & -5 & -2 & -2 \\ 0 & -6 & 6 & -1 \end{array}\right]$

消去最后一行的第二列，$r_3-\frac{6}{5}r_2$得

$\left[\begin{array}{ccc|c} 2 & 4 & -2 & 2 \\ 0 & -5 & -2 & -2 \\ 0 & 0 & \frac{42}{5} & \frac{7}{5} \end{array}\right]$

消元过程实际上就是对增广矩阵不断地实施初等行变换。

一般方法

接下来来介绍求解线性方程组(1)的顺序Gauss消去法，为了清楚起见，我们记$A^{(1)} = A,b^{(1)} = b,a_{ij}^{1} = a_{ij}, b_{i}^{(1)} = b_{i}$

则，线性方程组(1)的增广矩阵为：

$(A^{(1)},b^{(1)}) = \left[\begin{matrix} a_{11}^{(1)} & a_{12}^{(1)} & a_{13}^{(1)}&... & a_{1n}^{(1)} & b_1^{(1)} \\ a_{21}^{(1)} & a_{22}^{(1)} & a_{23}^{(1)}& ... & a_{2n}^{(1)} & b_2^{(1)} \\a_{31}^{(1)} & a_{32}^{(1)} &a_{33}^{(1)} & ... & a_{3n}^{(1)} & b_3^{(1)} \\ ... & ... & ... & ... & ... & ...\\ a_{n1}^{(1)} & a_{n2}^{(1)} & a_{n3}^{(1)} & ... & a_{nn}^{(1)} & b_n^{(1)}\end{matrix}\right]$

第一步：设$a_{11}^{(1)} \not = 0$，依次用$-l_{i1} = -\frac{a_{i1}^{(1)}}{a_{11}^{(1)}}, (i=2,3,...,n)$乘矩阵的第1行加到第$i$行，得到矩阵：

$(A^{(2)},b^{(2)}) = \left[\begin{matrix} a_{11}^{(1)} & a_{12}^{(1)} & a_{13}^{(1)} &...& a_{1n}^{(1)} & b_1^{(1)} \\ 0 & a_{22}^{(2)} & a_{23}^{(2)} & ... & a_{2n}^{(2)} & b_2^{(2)} \\0 & a_{32}^{(2)}& a_{33}^{(2)} & ... & a_{3n}^{(2)} & b_3^{(2)} \\ ... & ... & ... & ... & ...\\ 0 & a_{n2}^{(2)} &a_{n3}^{(2)} & ... & a_{nn}^{(2)} & b_n^{(2)}\end{matrix}\right]$

其中：$a_{ij}^{(2)} = a_{ij}^{(1)} - l_{i1}a_{1j}^{(1)}, i,j=2,3,...,n \\ b_i^{(2)} = b_{i}^{(1)} - l_{i1}b_{1}^{(1)}, i=2,3,...,n$

第二步：设$a_{22}^{(2)} \not = 0$，依次用$-l_{i2} = -\frac{a_{i2}^{(2)}}{a_{22}^{(2)}}, (i=3,4,...,n)$乘矩阵的第2行加到第$i$行，得到矩阵：

$(A^{(3)},b^{(3)}) = \left[\begin{matrix} a_{11}^{(1)} & a_{12}^{(1)} & a_{13}^{(1)} &... & a_{1n}^{(1)} & b_1^{(1)} \\ 0 & a_{22}^{(2)} & a_{23}^{(2)} & ... & a_{2n}^{(2)} & b_2^{(2)} \\0 & 0 & a_{33}^{(3)} &... & a_{3n}^{(3)} & b_3^{(3)} \\ ... & ... & ... & ... & ... & ...\\ 0 & 0 & a_{n3}^{(3)}& ... & a_{nn}^{(3)} & b_n^{(3)}\end{matrix}\right]$

其中：$a_{ij}^{(3)} = a_{ij}^{(2)} - l_{i2}a_{2j}^{(2)}, i,j=3,4,...,n \\ b_i^{(3)} = b_{i}^{(2)} - l_{i2}b_{2}^{(2)}, i=3,4,...,n$

如此继续消元下去，第$n-1$步结束后得到矩阵：

$(A^{(n)},b^{(n)}) = \left[\begin{matrix} a_{11}^{(1)} & a_{12}^{(1)} & a_{13}^{(1)} &... & a_{1n}^{(1)} & b_1^{(1)} \\ 0 & a_{22}^{(2)} & a_{23}^{(2)} & ... & a_{2n}^{(2)} & b_2^{(2)} \\0 & 0 & a_{33}^{(3)} &... & a_{3n}^{(3)} & b_3^{(3)} \\ ... & ... & ... & ... & ... & ...\\ 0 & 0 & 0 & ... & a_{nn}^{(n)} & b_n^{(n)}\end{matrix}\right]$

观察这个矩阵，第一行矩阵从头到尾均没有发生变化，第二行元素只发生一次变化，第三行发生了两次变化，这里我们发现，系数矩阵$A$已经变成了上三角矩阵$U$，说明消元过程已经结束了。

对应的方程变成：

$\begin{cases} a_{11}^{(1)}x_1 + a_{12}^{(1)}x_2+...+a_{1n}^{(1)}x_{n}=b_1^{(1)} \\ a_{22}^{(2)}x_2+...+a_{2n}^{(2)}x_{n}=b_2^{(2)} \\...............................\\ a_{nn}^{(n)}x_{n}=b_n^{(n)} \end{cases}$

对方程组进行回代，就可求出方程组的解。

整个消元和回代的过程加在一起就是我们所说的顺序Gauss消去法，那么大家看到了，在整个过程中，方法是精确的，也就是没有截断误差，也就是说顺序Gauss消去法确实是一种直接方法。那么它对比于Cramer法则，它的计算量是如何呢？

算法效率

顺序Gauss消去法求解$n$元线性方程组的乘除运算量是：

$n^2-1+(n-1)^2-1+...+2^2-1+1+2+...+n \\ = \sum^n_{k=1}(k^2-1) + \sum^n_{k=1}k \\ = \frac{n(n+1)(2n+1)}{6}-n+\frac{n(n+1)}{2}\\ = \frac{1}{3}(n^3+3n^2-n)$

例如，假设$n=20$，则乘除次数为$3060$次，Cramer法则为$9.7×10^{20}$

因此，顺序Gauss消去法确实大大减少了运算量，因此它是一种比较实用的直接方法，简称为Gauss消去法。

局限性

（1）主元为0造成的局限性

需要注意的是，在消元之前，我们假设了$a_{kk}^{k}$不能为0，如果为0则无法进行消元，我们将$a_{kk}^{k}(k=1,2,...,n)$称为主元素。这里的$k$需要真正算到这一步的时候才能判断出$k$是否为0，如果我们在某一步的时候才判断出$k=0$了，那么前面的步骤就全部白算了。因此我们希望有一种判断方法，能在开始消元之前就判断出整个Gauss消去法中，主元素能否为0。结论为：

主元素都不为0的充要条件是：矩阵$A$的各阶顺序主子式都不为0

矩阵$A$为系数矩阵，因此我们可以根据判断矩阵$A$的各阶顺序主子式来判断，因此这也是Gauss消去法的局限所在。

（2）消去过程中产生“大数吃小数”问题

顺序高斯消去法除了当主元素为0时可能造成的无法消元以外还有其他局限性吗？我们来看一个例子

例1：解线性方程组（用十进制四位浮点计算）

$\begin{cases} 0.000100x_1+1.00x_2=1.00 \\ 1.00x_1+1.00x_2=2.00 \end{cases}$

（用Cramer法则可得精确解$x_1^* = 1.00010, x_2^* = 0.99990$）

解：用顺序Gauss消去法，消元得

$\begin{cases} 0.000100x_1+1.00x_2=1.00 \\ -10000x_2=-10000 \end{cases}$

这就产生了“大数吃小数”的问题，这样求解得$x_2 = 1.00, x_1 = 0.00$。我们发现这个误差非常非常大。由于顺序Gauss消去法没有截断误差，因此这是由舍入误差造成的。那么这个“大数”是从哪来的呢？我们发现在第一次进行消元的时候，求两行比例系数的过程中，我们用了绝对值很小的数做了除数，以至于误差被放大了。

我们将方程组交换两行，改写成

$\begin{cases} 1.00x_1+1.00x_2=2.00 \\ 0.000100x_1+1.00x_2=1.00\end{cases}$

用顺序Gauss消去法，消元得：

$\begin{cases} 1.00x_1+1.00x_2=2.00 \\ 1.00x_2=1.00\end{cases}$

回代得解$x_2 = 1.00, x_1 = 1.00$，这个近似解是可以接受的，误差也在可接受的范围。

通过这个例子大家看到了，在顺序Gauss消去法当中，尽管主元素不为0，可以保证Gauss消去法从头进行到尾，但是如果在消元的过程中，主元素很小的话，同样会产生最终解的舍入误差非常大以至于不能用的情况。这就是顺序高斯消去法第二个局限性，同时我们也找到了改变这个局限性的方法，就是互换两个方程。