第二章 线性方程组的数值解法在科技、工程技术、社会经济等各个领域中很多问题常常归结到求解线性方程组。

例如电学中的网络问题，样条函数问题，构造求解微分方程的差分格式和工程力学中用有限元方法解连续介质力学问题，以及经济学中求解投入产出模型等都导致求解线性方程组。

n 阶线性方程组的一般形式为⎪⎪⎩⎪⎪⎨⎧=+++=+++=+++nn nn n n n n n n b x a x a x a b x a x a x a b x a x a x a L K K K K L L 22112222212********* （1.1） 其矩阵形式为b Ax = （1.2） 其中⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=n n nn n n n n b b b b x x x x a a a a a a a a a A M M L K K K K L L 2121212222111211),,2,1,(n j i a ij L =，),,2,1(n i b i L =均为实数，i b 不全为0，且A 为非奇异。

关于线性方程组的数值解法一般分为两类：1．直接法 就是不考虑计算机过程中的舍入误差时，经有限次的四则运算得到方程组准确解的方法。

而实际中由于计算机字长的限制，舍入误差的存在和影响，这种算法也只能求得线性方程组的近似解。

本章将阐述这类算法中最基本的消去法及其某些变形。

这些方法主要用于求解低阶稠密系数矩阵方程组。

2．迭代法 从某个解的近似值出发，通过构造一个无穷序列，用某种极限过程去逐步逼近线性方程组的精确解的方法。

本章主要介绍迭代法与迭代法。

迭代法是解大型稀疏矩阵（矩阵阶数高而且零元素较多）的线性方程组的重要方法。

§1 高斯)(Gauss 消去法1.1 Gauss 消去法Gauss 消去法是将线性方程组化成等价的三角形方程组求解。

首先举例说明Gauss消去法的基本思想和过程。

例1 解线性方程组⎪⎩⎪⎨⎧=−+=+−=−+224056242321321321x x x x x x x x x （1.3）解 用 21−乘第一个方程的两端并加至第二个方程，然后用2−乘第一个方程两端加至第三个方程，得同解方程组⎪⎩⎪⎨⎧−=+−−=+−=−+102736362423232321x x x x x x x （1.4） 再消去第三个方程中的变量2x ，又可得到与（1.4）等价的方程组⎪⎩⎪⎨⎧−=−−=+−=−+3123636242332321x x x x x x （1.5）这是一个三角形方程组。

这时，我们可从（1.5）的第三个方程解出3x ，然后回代第二个方程解出2x ，继续回代到第一个方程，则解为T x )41,23,41(=上述解方程组的方法就是Gauss 消去法。

一般地求解n 阶线性方程组（1.1）的步骤由如下1−n 步组成将（ 1.2）记为)0()0(b x A=，)(0)0(ij a A =，0)0(i b b =。

其中)0()0()0()|()|(A b A b A ==第一步 设0)0(11≠a，记),,3,2()0(11)0(11n i a a l i i L ==。

用1i l −乘)0(A 的第一行加到第i 行上，将第一列的元素13121,,,n a a a L 消为零，得⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡==)1()1()1(2)1(2)1(2)1(22)0(1)0(1)0(12)0(11)1()1(00)|(n nn n nn b a a b a a b a a a b AA L L LL L LL L （1.6） 式中)0(1)0()1(ij i ij ij a l a a −=，),,3,2,()0(1)0()1(n j i b l b b i i i iL =−=。

第二步 设0)1(22≠a，记),,4,3()1(22)1(22n i a a l i i L ==，将)1(A 的第二列元素)1(2)1(42)1(32,,,n a a a L 消为零，完成第二次消元。

仿此继续进行消元，假设进行了1−k 步，得到⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡==−−−−−−−)1()1()1()1()1()1(2)1(2)1(2)1(22)0(1)0(2)0(1)0(12)0(11)1()1()1(0000000)|(n k nn k nk k kn k kk n kn k k k k b a a a a b a a a b a a a a b AALLL L LLL L LL L L L L L L L L L L L （1.7）一般第k 步)11(−≤≤n k设0)1(≠−k kka ，计算乘数),,1()1()1(n k i a a l k kkk ik ik L +==−−，将)1(−k A 的第k 列的元素)1()1(1,,−−+k nkk k k a a L 消为零，完成1−n 次消元后，我们可得到上梯形矩阵⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡==−−−−−)1()1()1(2)1(2)1(22)0(1)0(1)0(12)0(11)1()1(1)|(n n n nnnn n n n b a b a a b a a a b AAL L LL L LL L (1.8) 其中，⎪⎩⎪⎨⎧−=−===−−−−−−)1()1()()1()1()()()1()1(,0,/k k ik k ik i k kj ik k ij k ij k ik k kk k ik ik b l b b a l a a a a a l n k j i ,,1,L += (1.9) 式中的元素)1(−k kka 称为（第k 步）的约化主元素，显然第k 步消元可以进行的条件是0)1(≠−k kk a ，可以证明0)1(≠−k kk a 的充要条件是A 的各阶顺序主子式)1,,2,1(0212222111211−=≠⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=n k a a a a a a a a a A kk k k k k k L L K K K K L L 。

若0)1(=−k kk a ，由于A 为n 阶非奇异矩阵，所以)1()1(1,,−−+k nk k k k a a L 中至少有一不为零。

例如)(0)1(k r a k rk>=−，于是可交换第r 行和第k 行，然后进行消元计算。

（1.8）式中)1(−n A对应的上三角形方程组与（1.1）同解⎪⎪⎩⎪⎪⎨⎧==++=+++−−)1()1()1(2122)1(22)0(1)0(12)0(121)0(11n n n n nn n n n n b x a b x a x a b x a x a x a L L L L L L （1.10） Gauss 消去法的回代过程是解三角形方程组（1.10），可以从下到上逐次把11,,,x x x n n L −的值计算出来，容易得到解的计算公式为⎪⎩⎪⎨⎧−==−+=−−−−∑)1(11)1(1)1(/][/k kk n k j j k kj k k kn nn n n n a x a b x a b x 1,,2,1L −−=n n k （1.11）1.2 Gauss 消去法的计算量由消去法步骤可知，消去第一列1−n 个系数所需要的乘法运算次数为n n )1(−，消去第二列2−n 个系数需要)1)(2(−−n n 次乘法运算。

最后，消去第1−n 列中的一个系数需要1*2次乘法运算。

所以，共需乘法运算总次数为n n n n n n n k k k k nk n k n k 3131]1)1(21[1)12)(1(61)1(32221−=−+−−++=−=−∑∑∑=== 其次，生成ij l 时还需要除法运算，总数为n nn n k n k 2121)1(21211−=−=∑−= 在回代求解时，需要作乘法运算，次数为n n k n k 2121211−=∑−= 同时，还需要进行n 次除法。

因此，求解过程共需乘除法运算的次数为n n n n n n n n 3131]2121[231312323−+=+−+− 对于较大的n ，所需运算的工作量可用331n 来估计，因为相对来讲低阶项微不足道，而加减法运算所需时间远少于乘除法，所以分析算法有效性时往往只统计乘除法次数。

由上面的公式容易求出，求解30阶线性方程组时，用Gauss 消去法只需要9890次乘除法运算，在第一章第 节中我们曾指出，若用Cramer 法则求解则需要 次乘除法运算。

§2 Gauss 主元素消去法2.1 主元的选取对求解的影响在Gauss 消去法的消元过程中，只要求保证0)1(≠−k kk a )1,,2,1(−=n k L ，但主元素的选取对结果会产生很大影响。

例如0)1(≠−k kka 而绝对值很小时，用其作除数，会导致其它元素的数量级急剧增加因而舍入误差也增大，最后会使计算结果不可靠。

例1 解方程组⎪⎩⎪⎨⎧=++=++=++96.05.696.00.5020.036.05.40.20.61.31.15.0321321321x x x x x x x x x （2.1）用3位浮点数进行计算。

解 若按自然顺序选取主元，则消元结果如下⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡−−−−→⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡−−−−−→⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=24601220000.240.12100.0000.610.310.1500.05905.240.1000.240.12100.0000.610.310.1500.0960.050.6960.000.5020.0360.050.400.200.610.310.1500.0)|()0()0(b A回代求解便得02.2,40.2,80.5*3*2*1==−=x x x但是满足方程组（2.1）的精确解为00.2,00.1,60.2321==−=x x x显然，近似解是一个很坏的结果。

为了改善计算结果，在消元时可选取绝对值较大的系数作为主元。

例如，在消元的第一步可选第三个方程中1x 的系数5.00作为主元，这时消元结果则为⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡−−→⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡−−→⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡↔99.599.200364.024.212.40960.050.6960.0500.090.545.200.10364.024.212.40960.050.6960.0500.000.610.310.1500.0020.0360.050.40.2960.050.6960.00.5)|(31)0()0(r r b A 最后回代求解得00.2,00.1,60.2*3*2*1==−=x x x该解与精确解一样。