第5章线性方程组的数值解法5.1高斯消去法5.1.1三角形方程组的解法系数矩阵为上三角阵或下三角阵的线性方程组称为三角形方程组，即u11x1+u12x2+…+u1nxn=b1u22x2+…+u2nxn=b2unnxn=bn(5.3)其矩阵形式为Ux=b(当i>j时uij =0)或l11x1=b1l21x1+l22x2=b2ln1x1+ln2x2+…+lnnxn=bn(5.4)其矩阵形式为Lx=b(当i<j时lij=0)三角形方程组易于求解。以上三角形方程组(5.3)为例，其有且仅有一组解的充要条件是uii≠0(i=1，2，…，n)。从最后一个方程开始，逐次向上回代可得xn=bn/unnxn-1=(bn-1-un-1，nxn)/un-1，n-1x1=(b1-u12x2-u13x3-…-u1nxn)/u11(5.5)这个过程称为回代过程。规定当m>n时∑nmf(·)=0(f(·)代表任意表达式，没有具体式子)，则式(5.5)可归结为xi=(bi-∑nk=i+1uikxk)/uii (i=n，n-1，…，1)(5.6)对于式(5.4)，类似地有xi=bi-∑i-1k=1likxk/lii(i=1，2，…，n)高斯消去法手算5.1.2高斯消去法
高斯消去法的基本思想： 对于一般的线性方程组，将其消元为同解的上三角形方程组，然后回代，即可得到原方程组的解。先看一个简单的例子，用以说明高斯消去法的计算过程。【例5.1】解方程组
①
② 
③x1+x2+x3=62x1+4x2-x3=72x1-2x2+x3=1解消元：
第一步： 计算①×(-2)+②、①×(-2)+③，得
①
④
⑤x1+x2+x3=62x2-3x3=-5-4x2-x3=-11第二步： 计算④×2+⑤，得到与原方程组同解的三角形方程组
①
④
⑥x1+x2+x3=62x2-3x3=-5-7x3=-21
回代：
高斯消去法的算法由⑥得x3=3。
将x3的值代入④得x2=2。
将x2、x3的值代入①得x1=1。
即原方程组的解为x1=1x2=2x3=3对于一般的n阶线性方程组Ax=b，即a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2an1x1+an2x2+…+annxn=bn首先进行消元：
第一步（第一次消元）：
设a11≠0，令li1=ai1/a11(i=2，3，…，n)用(-li1)乘式(5.1)的第一个方程并加到第i个方程上(i=2，3，…，n)，得到同解方程组a11a12…a1n0a（1）22…a（1）2n0a（1）n2…a（1）nnx1x2xn=b1b（1）2b（1）n(5.7)记为A（1）x=b（1），其中a（1）ij=aij-li1a1j(i，j=2，3，…，n)b（1）i=bi-li1b1(i=2，3，…，n)第二步（第二次消元）：
设a（1）22≠0，令li2=a（1）i2/a（1）22 (i=3，4，…，n)用(-li2)乘式(5.7)的第二个方程加到第i个方程上(i=3，4，…，n)，得到同解方程组a11a12a13…a1n0a（1）22a（1）23…a（1）2n00a（2）33…a（2）3n00a（2）n3…a（2）nnx1x2x3xn=b1b（1）2b（2）3b（2）n记为A（2）x=b（2），其中a（2）ij=a（1）ij-li2a（1）2j(i，j=3，4，…，n)b（2）i=b（1）i-li2b（1）2(i=3，4，…，n)一般地，经过k-1次消元后，得到方程组(5.1)的同解方程组为a11a12…a1ka1，k+1…a1na（1）22…a（1）2ka（1）2，k+1…a（1）2na(k-1)kka(k-1)k，k+1…a(k-1)kna(k-1)k+1，ka(k-1)k+1，k+1…a(k-1)k+1，n0a(k-1)nka(k-1)n，k+1…a(k-1)nnx1x2xkxk+1xn=b1b（1）2b(k-1)kb(k-1)k+1b(k-1)n(5.8)第k步（第k次消元）：
设a(k-1)kk≠0(称a(k-1)kk为主元素)，令lik=a(k-1)ik/a(k-1)kk(i=k+1，k+2，…，n)(5.9)用(-lik)乘式(5.8)的第k个方程并加到第i个方程上(i=k+1，k+2，…，n)，得到同解方程组为a11a12…a1ka1，k+1…a1na（1）22…a（1）2ka（1）2，k+1…a（1）2na(k-1)kka(k-1)k，k+1…a(k-1)kna(k)k+1，k+1…a(k)k+1，n0a(k)n，k+1…a(k)nnx1x2xkxk+1xn=b1b（1）2b(k-1)kb(k)k+1b(k)n记为A(k)x=b(k)，其中a(k)ij=a(k-1)ij-lika(k-1)kj(i，j=k+1，k+2，…，n)(5.10)b(k)i=b(k-1)i-likb(k-1)k(i=k+1，k+2，…，n)(5.11)如此继续下去，完成n-1次消元后，方程组(5.1)即化成同解的上三角形方程组a11a12…a1na（1）22…a（1）2na(n-1)nnx1x2xn=b1b（1）2b(n-1)n于是就可以进行回代，求出原方程组(5.1)的解xi=b(i-1)i-∑nk=i+1a(i-1)ikxk/a(i-1)ii(i=n，n-1，…，1)(5.12)记a(0)ij=aij(i，j=1，2，…，n)。易见，在上述消元过程中，每次都是顺序地选取主对角线上的元素a(k-1)kk作为主元素，所以高斯消去法又称为顺序高斯消去法。
定理5.1线性方程组Ax=b能用高斯消去法求解的充要条件是系数矩阵A的各阶顺序主子式Dk≠0(k=1，2，…，n)，即D1=a11≠0Dk=a11…a1kak1…akk≠0(k=2，3，…，n)证明从略。
在计算机上实现时，常把方程组的系数矩阵及右端向量存放在一个n行、n+1列的二维数组中。考虑到在消元过程中，算出a(k)ij后，a(k-1)ij就没有保留的必要了，所以可让a(k)ij仍占用a(k-1)ij所在单元。另外，消元为0的元素就不必计算了。
高斯消去法算法：
（1） 消元过程：
当k=1，2，3,…，n-1时,对i=k+1，k+2，…，n,做
① l=aik/akk。
② 对j=k+1，k+2，…，n+1，做aij -lakjaij。
（2） 回代过程：
对k=n，n-1，…，1，做ak，n+1-∑nj=k+1akjxj/akkxk。
由于计算机完成一次乘(除)法花费的时间远远多于做一次加(减)法的时间，而且按照统计规律，在一个算法中，乘除法与加减法的运算次数大体相当，所以通常用所做乘除法的次数来衡量算法的运算量。
由式(5.9)～式(5.11)可知，在第k次消元中，做了(n-k)2+2(n-k)次乘除法运算，于是n-1次消元所做乘除法的次数为∑n-1k=1［(n-k)2+2(n-k)］=n33+n22-5n6而由式(5.12)可知，回代过程所做乘除法的次数为∑nk=1(n-k+1)=n22+n2故高斯消去法的运算量为n33+n22-5n6+n22+n2=n33+n2-n3≈n335.1.3主元素消去法
在高斯消去法消元过程中，若出现主元素a(k-1)kk等于0的情况，消去法将无法进行；若主元素a(k-1)kk不等于0，但其绝对值很小，则由第1章的讨论可知，用它作为除数将会导致计算结果有很大误差，甚至于完全失真。
【例5.2】解线性方程组。
①
②0.00001x1+x2=1.000012x1+x2=3
【解】准确解是 (1，1)T。现设所用计算机为四位浮点数计算机。
（1） 方程组输入计算机后成为0.1000×10-40.1000×1010.2000×1010.1000×101x1x2=0.1000×1010.3000×101用高斯消去法对其消元后得0.1000×10-40.1000×1010-0.2000×106 x1x2=0.1000×101-0.2000×106回代得x2=1，x1=0，即为(0，1)T，解严重失真。
 （2） 若先交换方程组的两个方程①、②的顺序，成为0.2000×1010.1000×1010.1000×10-40.1000×101x1x2=0.3000×1010.1000×101用高斯消去法对其消元后得0.2000×1010.1000×10100.1000×101x1x2=0.3000×1010.1000×101回代得x2=1，x1=1，即为(1，1)T，得到了准确解。
为何（1）、（2）两种解法计算结果相差如此之大？原因就在于解法（1）进行消元时用了绝对值较小的主元素a11=0.00001作为除数，因此带来了较大的误差；而解法（2）交换方程顺序后，用绝对值较大的主元素作为除数，便具有了较好的数值稳定性。
主元素消去法的基本思想是在逐次消元时总是选绝对值最大的元素作为主元素，常用的主元素消去法有列主元素消去法和全主元素消去法。列主元素消去法简称列主元法，就是在第k次消元之前在a(k-1)ik(i=k，k+1，…，n)中选出绝对值最大的元素，经行交换，将它置于a(k-1)kk处再进行消元。全主元素消去法简称全主元法，就是在第k次消元之前在a(k-1)ij(i，j=k，k+1，…，n)中选出绝对值最大的元素，经行交换、列交换，将它置于a(k-1)kk处，再进行消元。
列主元高斯消去法可以证明，只要系数矩阵非奇异，列主元法在计算过程中的舍入误差是基本能控制的，且其选主元的工作量相对较小，所以列主元法最常用。现举一例，用以说明列主元高斯消去法的计算过程。
【例5.3】用列主元高斯消去法解线性方程组。x1-x2+x3=-43x1-4x2+5x3=-12x1+x2+2x3=11【解】消元过程列表如表51所示。表51消元过程列表
序号x1x2x3右端项说明（1）
（2）
（3）1
3
1-1
-4
11
5
2-4
-12
11在第一列上选主元3（4）
（5）
(6)3
1
1-4
-1
15
1
2-12
-4
11（1）（2）
计算l21=1/3=0.33333
l31=1/3=0.33333(7)
(8)
(9)3
0
0-4
0.33332
2.333325
-0.66665
0.33335-12
0.000040
14.99996（4）×(-l21)+（5）
（4） ×(-l31)+(6)
在第二列的子列上选主元2.33332(10)
(11)
(12)3
0
0-4
2.33332
0.333325
0.33335
-0.66665-12
14.99996
0.00004(8)(9)
计算l32=0.33332/2.33332=0.14285(13)
(14)
(15)3
0
0-4
2.33332
05
0.33335
-0.71427-12
14.999960
-2.14270(11)×(-l32)+(12)回代得x1=-0.99972x2=6.00002x3=2.99985，精确解是x1=-1x2=6x3=3。
列主元高斯消去法算法：
（1） 消元过程：
对于k=1，2，…，n-1，做
① 选主元（即确定r，使得ark=maxk≤i≤naik）。
k r。对i=k+1，k+2，…，n，若ark<aik，则i r。
② 若ark=0(说明系数矩阵奇异)，则输出奇异信息，然后结束。
③ 若r≠k，则交换增广矩阵的第k行和第r行，即对j=k，k+1，…，n+1，做akj arj。
④ 对i=k+1，k+2，…，n，计算l=aik/akk。
对j=k+1，k+2，…，n+1，做aij-lakj aij。
（2） 回代过程：
对于k=n，n-1，…，1，做ak，n+1-∑nj=k+1akjxj/akkxk。
列主元高斯消去法在高斯消去法的基础上增加了选主元及行交换的操作，而运算次数并无改变，故其运算量仍约为n33。
直接法在计算过程中不可避免地存在舍入误差，所以应对所求解进行偏差校验，即将x1，x2，…，xn代回原方程组。
Ei=bi-∑nj=1aijxj(i=1，2，…，n) 称为第i个方程的偏差，E=max1≤i≤nEi称为方程的最大偏差，用以校验解的可靠性。
5.1.4用列主元高斯消去法求行列式值
列主元高斯消去法实际上就是对矩阵进行了两种初等变换： 一种是对换两行的位置；另一种是将某行元素乘以同一数后加到另一行对应元素上。前者使行列式值变号，后者不改变行列式值。系数矩阵经消元后成为一上三角阵，而三角阵的行列式的值等于其主对角线元素之积，故可用列主元高斯消去法求行列式的值。下面通过一个例子来说明其求解过程。
【例5.4】求|A|＝1-113-45112的值。
【解】1-113-45112选主元①②3-451-11112
②-①×0.33333③-①×0.333333-4500.33332-0.6666502.333320.33335
选主元②③3-4502.333320.3333500.33332-0.66665
③-②×0.142853-4502.333320.3333500-0.71427
于是A=(-1)2×（3）×(2.33332)×(-0.71427)≈-4.99986(进行了两次行交换，故乘以(-1)2)。
易见，在用列主元高斯消去法消元过程中就可把系数矩阵行列式的值同时求出来。程序中在进入消元之前，将系数矩阵行列式值的初值d赋为1；在消元过程中，每进行一次行交换，便将-d赋给d；消元结束后，将d与主对角线元素aii(i=1，2，…，n)累乘即可得到系数矩阵行列式的值。
5.2高斯若尔当消去法5.2.1高斯若尔当消去法简介高斯若尔当消去法是高斯消去法的一种变形。高斯消去法将对角线下方的元素消元为0，若同时将对角线上方的元素也高斯若尔当消去法消元为0，且将对角元皆化为1，即将方程组(5.1)化成如下对角形方程组：111x1x2xn=c1c2cn则无须回代就可得到方程组(5.1)的解：x1x2xn=c1c2cn这种消去法称为高斯若尔当消去法，也称为无回代的高斯消去法。
在实际计算中，常采用列主元高斯若尔当消去法。下面用一个例子来说明该方法的计算过程。
【例5.5】用列主元高斯若尔当消去法解线性方程组x1-x2+x3=-43x1-4x2+5x3=-12x1+x2+2x3=11【解】1-11-43-45-1211211选主元3①②3-45-121-11-411211
将主元3化为11-1.333331.66667-41-11-411211
②-①③-①1-1.333331.66667-400.33333-0.66667002.333330.3333315
选主元2.33333②③1-1.333331.66667-402.333330.333331500.33333-0.666670
将主元2.33333化为11-1.333331.66667-4010.142866.4285800.33333-0.666670
①+1.33333×②③-0.33333×②101.857154.57142010.142866.42858000.71429-2.14284
将主元0.71429化为1101.857154.57142010.142866.428580013.00000
①-1.85715×③②-0.14286×③100-1.000030106.000000013.00000
于是解为x1=-1.00003x2=6.00000x3=3.00000精确解是x1=-1x2=6x3=3。
列主元高斯若尔当消去法算法(存储情况与高斯消去法类似)：
对k=1，2，…，n：
（1） 按列选主元，即确定r使ark=maxk≤i≤naik。
（2） 若ark=0(说明系数矩阵奇异)，则输出奇异信息，然后结束。
（3） 若r≠k，则交换增广矩阵的第k行和第r行，即
对j=k，k+1，…，n+1，做akj arj。
（4） 将主元akk化为1。
对j=k+1，k+2，…，n+1，做akj/akk akj。
（5）  消元。
当i=1，2，…，n时，若i≠k，则对j=k+1，k+2，…，n+1，做aij-aik akjaij。
算法完成后，增广矩阵的第n+1列即为原方程组的解。
可以看出，高斯若尔当消去法的消元过程比高斯消去法略复杂，但省去了回代过程。它的运算量约为n32，大于高斯消去法。因此，用其求解线性方程组不见得最好，不过用它求逆矩阵却有方便之处。
5.2.2逆矩阵的计算
用列主元高斯若尔当消去法求矩阵的逆实际上就是线性代数中学过的初等变换方法求逆的一种规范化算法。下面通过一个例子来说明其计算过程。
【例5.6】求A=1-10223-121的逆矩阵。