关于消元法介绍

[拼音]：xiaoyuanfa

[外文]：elimination method

又称消去法。解线性代数方程组的主要方法之一。早在东汉以前，中国古代著名的数学著作《九章算术》中就有了用消元法解方程组的方法。直到今日，消元法仍是解线性代数方程组的一个很重要的方法。在一些国家的数学著作中也常用高斯消去法这一名词。

消元法解线性代数方程组时，将某一方程乘以某些常数分别加到其他方程上，以消去这些方程中的某一未知量。重复施行这一步骤，就可逐步消去未知量，最后只剩下一个未知量。用矩阵的语言来说也就是对方程组的系数矩阵或增广矩阵(加上右端项所成的矩阵)进行初等变换，使它的一些元素(例如主对角线以下的元素)为零。具体地说，设方程组为

(1)

式中αij(i，j=1，2，…，n)和ƒ1，ƒ2，…，ƒn都是已知数，x1，x2，…，xn为待求的解。设α11不为零，将第一个方程分别乘以-α21/α11，-α31/α11，…，-αn1/α11加到第2至第n个方程上，就消去了这些方程中的x1，方程组化成

(2)

这里为了统一起见，已将α11，α12，…，αƒ1分别写为α刴，α剓，…，α剝和ƒ別。对(2)的后n-1个方程进行类似处理，消去后n-2个方程的x2，这样继续下去，若α都不为零，最后得到

(3)

上述过程可表示为：对k=1，2，…，n-1，

式中

有了(3)就可反推求出(1)的解：

这称为回代过程，而前面消去的步骤称为消去过程。

在消去过程中，有时可能遇到α=0的情况，但若方程组(1)有惟一解，则在中至少有一个不为零，例如 α嫻≠0，那么只要将这时的第k个方程和第j个方程互换，即可继续进进消去。有时虽α≠0，但｜α｜很小，此时往往带来较大误差，从而使最后得到的解不够精确，甚至面目全非。为避免这种情况，也要进行上述交换，将 中最大者所在的方程与第k个方程交换，这叫做列主元素消元法或部分主元素消元法，也可在后n-k+1个方程的所有的系数中找出绝对值最大的而后进行方程和未知量的交换，这叫做全主元素消元法，但这种方法工作量较大，一般用列主元素消去法较好。

方程组(1)可写成矩阵的形式

(4)

式中A 为(1)的系数αij所成的矩阵，尣和ƒ 分别为列向量(x1，x2，…，xn)T和(ƒ1，ƒ2，…，ƒn)T;则以上的消去过程可写为

式中

而

pk为使矩阵的第k行与其后的某行交换的排列阵，当不需进行交换时，则无此pk因子或pk=I（n阶单位阵）。

又称因子分解法，是由消元法演变而来的解线性代数方程组的一种方法，它将方程组(4)中的系数矩阵A分解成下三角形矩阵L和上三角形矩阵 U之积。它有几种形式，例如可取L的对角线元素为1，即L为单位下三角形矩阵。这种情形下将L和U相乘，并与A比较，可知L和U的元素lij和uij可由下列递推公式给出：对k=1，2，…，n，

计算顺序为先算U的第一行，再算L的第一列，然后U的第二行，L的第二列等等，其中规定和数为零（下同）。得到L和U后，(4)可写为两个方程组

设y的分量为y1，y2，…，yn，容易得出

(5)

和

(6)

在分解因子时，为了避免除数ukk为零或｜ukk｜甚小带来较大误差，也可在U的每行元素ukk，uk，k+1，uk，n算好后，在这些元素中选主元，然后进行列的交换。此时要注意，尣的分量也应相应地进行交换。以上的方法称为杜利特尔分解法。若取L为下三角形矩阵，U为单位上三角形矩阵，则为克劳特分解法，其算式为：对k＝1，2，…，n，

计算时，先算L的第一列，再算U的第一行等等，同样可在算完lkk，lk+1，k，…，lnk后选主元，进行行的交换，但同时要将ƒ 的分量进行相应的交换。其求解的过程也和(5)、(6)类似。

若A为对称正定矩阵，可设

此处L为下三角形矩阵，LT为其转置，计算公式为:对k=1，2，…，n。

计算时先算L的第一列，再顺次算其后各列，这叫做平方根法或乔勒斯基法。在A为对称正定时，lkk均不为零，故可以不选主元，但这个方法需要n次开方运算，而开方的工作量较多。若设

此处L为单位下三角形矩阵，D为对角矩阵，其对角线元素记为d1，d2，…，dn，则计算公式为：对k=1，2，…，n，

对每个k，先算dk，再算L的第k列。为了节省运算量，可保存乘积而对k=1，2，…，n，按

一行行地计算，即按d1，21，l21，d2，31，l31，32，l32，d3，…的顺序计算。求解过程为

这叫做改进的乔勒斯基方法。

解系数矩阵 A为三对角矩阵的线性代数方程组的常用方法。设方程组为

第一个方程可写为

一般地，有

(7)

把它代入第i+1个方程中，可得

(8)

由(8)可以逐次递推求出p1，q1，p2，q2，…，pn，qn，这称为“追”的过程，易知pn=0，然后由(7)可依次求得xn，xn-1，…，x1，这叫“赶”的过程。可以证明，在

即A为强对角优势矩阵情况下，计算是稳定的，即舍入误差的影响很小。因此追赶法是行之有效的。实际上追赶法就是克劳特分解法。对块三对角矩阵，也有类似的所谓“块追赶“的方法，然而它需要求一系列的逆矩阵，计算量可能较大。

解线性代数方程组的方法分直接法和迭代法两大类，上面的方法都属直接法的范畴。在用直接法求解时，要根据系数矩阵的性质和计算机的性能，从内存、计算量、稳定性等一些方面来考虑。就一些计算机而言，乘除法所需时间较加减法多得多，故应尽量减少乘除法。上面的高斯消去法、杜利特尔法、克劳特法中的乘除法和加减法的次数均数量级，而乔勒斯基法由于利用了对称的性质，就只有。在计算中，中间量应尽量存储在原矩阵A以后不再用的元素的位置，例如分解法的L和U的元素即可占用A的相应元素的位置。特别对稀疏矩阵，应根据矩阵的形状，选择特殊的计算方法以尽量节省计算量和避免产生较多的非零元素。对三对角矩阵情形的追赶法就是一个突出的例子。

当用某种方法求出方程组(1)或(4)的解时，由于舍入误差的影响，它一般不是方程?榈木方鈱玻皇且桓鼋平鈶O。将慜代入原方程，若剩余向量r=A慜-ƒ各分量的绝对值均甚小，一般就可认为 慜是比较精确的近似解，也可任取一已知向量z，较精确地（例如用双精度）算出向量b=Az，然后用解A尣=ƒ 同样的方法解Az=b，得近似解墫。一般就用作为 尣的近似解慜的误差。然而这种方法也不是绝对可靠的。特别对病态矩阵、矩阵的元素或方程组的右端的微小变动可以导致方程组的解很大变动。这种误差估计的方法是威尔金逊的一个重要结果，然而作出的上界往往偏高。如何更好地估计误差仍待研究。

为了提高解的精度，下述迭代改进法还是可取的:设尣0为(4)的近似解，计算

，

再逐步求出方程组

的近似解Δ尣1，Δ尣2，…，此处

这样得到的序列尣0，尣1=尣0+Δ尣1，尣2=尣1+Δ尣2，…往往能逐步更近似于方程组的精确解。此外也还有其他一些方法。

给定一个非奇异矩阵A，求A的逆矩阵A-1本质上是解一组线性代数方程组的问题。事实上由Ap=I(单位矩阵)，可知逆矩阵p的第i列所成的向量pi应为方程组Api=ei的解，此处ei为第i个分量为1、其余分量为零的列向量。实际求逆矩阵时，可用消元法来计算。在前面的高斯消元法中，每步可以不仅将对角线以下的元素消成零而且将对角线以上的元素也消成零，并使对角线元素为1。与高斯消元法相类似，可以得到

这里Nk为在第k步将矩阵A(k)=Nk-1…N2N1A的第k列变为ek的矩阵。具体求逆时，可按下列步骤进行，其中αij，αik，αkj，αkk均指当时在A的相应元素位置上的数：对k＝1，2，…，n的每个k，依次做①计算d=1/αkk，并放在αkk处；

（2）对i≠k计算－dαik，并放在αik处；

（3）当i和j均不等于k时计算αij＋αikαkj并放在αij处；

（4）对j≠k计算dαkj，并放在αkj处。可证，最后在矩阵A原来的位置上就得到A的逆阵A-1。为了提高精度，也可采取选主元的方法。

和解线性代数方程组的三角分解法一样，也可将A分解为下三角阵L和上三角阵U之积，即A=LU，从而A-1=U -1L-1，而三角形矩阵的逆矩阵是易于求出的。

此外还有分块法、加边法、迭代法等一些求逆矩阵的方法。

参考书目

1. 冯康等编：《数值计算方法》，国防工业出版社，北京，1978。