太理水利工程计算及设计第二章 线性代数方程组的数值方法

1、第二章第二章 线性代数方程组的线性代数方程组的数值方法数值方法第一节第一节 线性代数方程组的直接解法线性代数方程组的直接解法第二节第二节 线性代数方程组的迭代解法线性代数方程组的迭代解法本章内容本章内容 各种直接解法的基本原理及构造迭代格式的各种直接解法的基本原理及构造迭代格式的基本原理。基本原理。重点重点第一节第一节 线性代数方程组的线性代数方程组的直接解法直接解法 直接解法是用有限次代数运算得到方程组解的方法。直接解法是用有限次代数运算得到方程组解的方法。如无舍入误差，则由直接解法得到的解就是精确解。但舍如无舍入误差，则由直接解法得到的解就是精确解。但舍入误差以及误差的积累是无法避免的，因

2、此直接解法给出入误差以及误差的积累是无法避免的，因此直接解法给出的仍是近似解。的仍是近似解。本节给出的各种直接解法都是适用于计算本节给出的各种直接解法都是适用于计算机的有效方法。机的有效方法。它们对稠密系数阵的较低阶方程组（几百它们对稠密系数阵的较低阶方程组（几百个方程）以及带状系数阵的高阶方程组（几千个方程）都个方程）以及带状系数阵的高阶方程组（几千个方程）都很有效。很有效。高斯消去法高斯消去法主元消去法主元消去法高斯高斯-约当消去法约当消去法三角分解法三角分解法对称矩阵的三角分解对称矩阵的三角分解-乔列斯基法乔列斯基法三对角阵的三角分解三对角阵的三角分解-追赶法追赶法方程组的逆矩阵解法与矩

3、阵求逆方程组的逆矩阵解法与矩阵求逆直接解法直接解法列主元法列主元法全主元法全主元法,22112222212111212111nnnnnnnnnnbxaxaxabxaxaxabxaxaxa,2121212222111211nnnnnnnnbbbxxxaaaaaaaaa设有设有n阶线性代数方程组阶线性代数方程组 方程组的矩阵形式为方程组的矩阵形式为可简记为可简记为BAX 本节假定本节假定A A非奇异或其行列式不为零，方程组有解且非奇异或其行列式不为零，方程组有解且唯一。唯一。一、高斯消去法一、高斯消去法 高斯消去法是高斯消去法是解线性方程组的经典方法解线性方程组的经典方法，由它改进得，由它改进得到

4、的选主元的消去法到的选主元的消去法, ,是目前计算机上常用于求低阶稠密是目前计算机上常用于求低阶稠密矩阵方程组的有效方法矩阵方程组的有效方法, ,其特点就是通过消元将一般线性其特点就是通过消元将一般线性方程组的求解问题转化为三角方程组的求解问题。方程组的求解问题转化为三角方程组的求解问题。高高 斯斯 消消 去去 法法举例举例11221733230636321321321xxxxxxxxx112217332521321321321xxxxxxxxx第一步第一步 消元过程消元过程(1)(2)(3)消消x1式式(1)/6(4)(5)(6)式式(5)-式式(4) 2式式(6)-式式(4) 623725

5、213232321xxxxxxx(7)(8)(9)高高 斯斯 消消 去去 法法623725213232321xxxxxxx62327215213232321xxxxxxx消消x2式式(8)/2式式(12)-式式(11) (3/2)(7)(8)(9)(10)(11)(12)43412721521332321xxxxxx(13)(14)(15)高高 斯斯 消消 去去 法法43412721521332321xxxxxx第二步第二步 回代过程回代过程321321xxx(13)(14)(15) 由式（由式（15）得到）得到x3，代入式（，代入式（14）得到）得到x2，再代入式，再代入式（13） 得到得到

6、x1。结果如下。结果如下高高 斯斯 消消 去去 法法高斯消去法的步骤高斯消去法的步骤)0()0(2)0(21)0(1)0(2)0(22)0(221)0(21)0(1)0(12)0(121)0(11nnnnnnnnnnbxaxaxabxaxaxabxaxaxa第一步消元第一步消元)1()1(3)1(32)1(2)1(2)1(23)1(232)1(22)1(1)1(13)1(132)1(121nnnnnnnnnnbxaxaxabxaxaxabxaxaxax原方程原方程（一）消元过程（一）消元过程高高 斯斯 消消 去去 法法niababbabbnjiaaaaaaaaabbnjaaaaiiiiijii

7、jjiijijjj2 ,/,2 ,/2 ,/0)0(11)0(1)0(1)0()1(1)0(1)0()1()0(11)0(1)0(1)0()1(1)0(1)0()1()0(11)0(1)1(1)0(11)0(1)1(1)0(11若niababbabbnjiaaaaaaaababbaaaababbaaaaiiiiijiijjiijijjjjjjj2 ,/,2 ,/)0(11)0(1)0(1)0()1(1)0(1)0()1()0(11)0(1)0(1)0()1(1)0(1)0()1()1(1)0(31)0(3)1(3)1(1)0(31)0(3)1(3)1(1)0(21)0(2)1(2)1(1)0(

8、21)0(2)1(2niababbabbnjiaaaaaaaaabbnjaaaaiiiiijiijjiijijjj2 ,/,2 ,/2 ,/0)0(11)0(1)0(1)0()1(1)0(1)0()1()0(11)0(1)0(1)0()1(1)0(1)0()1()0(11)0(1)1(1)0(11)0(1)1(1)0(11若第第k-1步消元的结果步消元的结果)1()1(1)1(1)1()1()1(1)1(1)1()1(1)1(1)1(11)2(2)2(23)2(232)1(1)1(13)1(132)1(121knnknnkknkkknkkknkknkkkkkkkkkknknkkkkkknnnn

9、bxaxaxabxaxaxabxaxaxbxaxaxbxaxaxax)()(1)(1)()(1)(1)1(1)1(1)1(11)2(2)2(23)2(232)1(1)1(13)1(132)1(121knnknnkknkkknkknkkkkkkknknkkkkkknnnnbxaxabxaxaxbxaxaxbxaxaxbxaxaxax第第k部消元部消元高高 斯斯 消消 去去 法法)( ,0)( ,),( ,/)( ,/0)()()1()1()()()1()1()()1()1()()1()1()()1(nikanikbabbnjikaaaaabbnjkaaaakikkkkikkikikkjkikki

10、jkijkkkkkkkkkkkkjkkjkkk?以上为高斯消去法的以上为高斯消去法的消元过程消元过程的算法。的算法。高高 斯斯 消消 去去 法法第第k个方个方程程第第k+1到第到第n个方程个方程第第n-1步消元结果步消元结果)1()1(1)()2(2)1(1)1()1(1)()(1)2(2)2(23)1(1)1(13)1(1210111nnnnkknnnnnnkknkkknnbbbbbaaaaaaaaa?O（二）回代过程（二）回代过程高高 斯斯 消消 去去 法法)1()1()1()1(/nnnnnnnnnnnnabxbxankjjkkjkkknkknkkkkkkkkknkknkkkkkxabx

11、xaxabxbxaxax1)()()(1)(1)()()(1)(1)() 1 , 2 , 1(/1)()()1()1(nkxabxabxnkjjkkjkkknnnnnn以上为高斯消去法的以上为高斯消去法的回代过程回代过程的算法。的算法。高高 斯斯 消消 去去 法法102212423321321321xxxxxxxxx题题1 试用高斯消去法解下列方程（小数点后取试用高斯消去法解下列方程（小数点后取4位数位数字计算）。字计算）。解解: 第一步消元第一步消元6667. 83333.116667. 06667. 23333. 003333. 16667. 303333. 03333. 01BA高高 斯

12、斯 消消 去去 法法第二步消元第二步消元6365. 70909. 36667. 05455. 2003636. 0103333. 03333. 01BA回代结果回代结果0000. 30001. 20000. 1X高高 斯斯 消消 去去 法法题题2 试用高斯消去法解下列方程。试用高斯消去法解下列方程。52213614282321321321xxxxxxxxx高高 斯斯 消消 去去 法法 二、主元消去法（二、主元消去法（ 称为主元）称为主元）11221732521321321321xxxxxxxxx6237521323321xxxxxx)1( kkka主主 元元 消消 去去 法法（1）Gauss消

13、去法消去法消消x1得得消消x2无法进行，因为无法进行，因为 。0)1(22a12102221xyzxyzxyz 121212121212121212102101010210101021010zyzyzyx（2）考虑如下线性方程组的）考虑如下线性方程组的Gauss消去法消去法 假定计算能保证假定计算能保证10位有效数字，则在此精度内位有效数字，则在此精度内x=y=z=1 是真解。是真解。消消x无法求解。原因无法求解。原因:第一个主元第一个主元 过小。过小。解（一）解（一）:主主 元元 消消 去去 法法12)0(1110a12102221xyzxyzxyz 12102212zyxzyxzyx332

14、22yzyzyx选较大主元选较大主元消消x结果结果 x=y=z=1 选择选择绝对值尽可能大的系数绝对值尽可能大的系数作为主元，会减少舍入误差作为主元，会减少舍入误差的影响，提高解的精度，并保证算法的稳定性。的影响，提高解的精度，并保证算法的稳定性。解（二）解（二）:主主 元元 消消 去去 法法 主元消去法主元消去法 在每一步消元中选取在每一步消元中选取绝对值绝对值尽可尽可能大的主元的高斯消去法称为主元消去法。能大的主元的高斯消去法称为主元消去法。列主元法列主元法全主元法全主元法有两种主元消去法：有两种主元消去法：主主 元元 消消 去去 法法 在消去在消去 的系数前，先从的系数前，先从 中选取中

15、选取绝对值最大者作为主元，交换第绝对值最大者作为主元，交换第k行与此主元所在的行，再行与此主元所在的行，再按高斯消去法消去第按高斯消去法消去第k行之后的方程中行之后的方程中 的系数，只要方的系数，只要方程是可解的，这一过程定能执行到底。程是可解的，这一过程定能执行到底。（一）列主元法（一）列主元法kxkx)1()1(1)1(,knkkkkkkkaaa主主 元元 消消 去去 法法)1()1(1)1(1)1()1()1(1)1(1)1()1(1)1(1)1(11)2(2)2(23)2(232)1(1)1(13)1(132)1(121knnknnkknkkknkkknkknkkkkkkkkkknkn

16、kkkkkknnnnbxaxaxabxaxaxabxaxaxbxaxaxbxaxaxax.40371. 00020. 20028. 2047471. 00010. 161077. 008563. 10010. 13920. 11)() 1 () 1 (bA4178. 745625. 5996. 33816. 1078125. 014 . 022002. 0)0()0(bA解：解： 4178. 745625. 5996. 33814. 178125. 04 . 022002. 032121321xxxxxxxx举例：列主元法举例：列主元法 第一步选列主元为第一步选列主元为 ，交换第，交换第1行与

17、第行与第3行，再消行，再消元计算得元计算得996. 331a 第二步选列主元为第二步选列主元为 ,交换第交换第2行与第行与第3行，再消行，再消元计算得元计算得0028. 232a.35159.039047.00020157.09996.0108563.10010.13920.11)()2()2(bA回代计算得到解为回代计算得到解为这个例题的精确解是这个例题的精确解是 9273. 1,69850. 0,90043. 0123xxx,)900423. 0 ,698496. 0,92730. 1 (Tx,)88888. 0 ,68695. 0,9300. 1 (Tx高斯消去法的结果是高斯消去法的结果

18、是主主 元元 消消 去去 法法（二）全主元法（二）全主元法,22112222212111212111nnnnnnnnnnbxaxaxabxaxaxabxaxaxan阶线性代数方程组阶线性代数方程组 nnnnnnnnbbbxxxaaaaaaaaa2121212222111211矩阵形式矩阵形式行交换变行交换变量顺序？量顺序？列交换变列交换变量顺序？量顺序？ （2）从方程组系数）从方程组系数 中选出绝对值最大者，中选出绝对值最大者，作为第一个主元。交换第一行与此元素所在的行，并交换第一作为第一个主元。交换第一行与此元素所在的行，并交换第一列与此元素所在的列，使选出的主元位于第一行第一列，一般列与此

19、元素所在的列，使选出的主元位于第一行第一列，一般地，在第地，在第k次消元之前，先从次消元之前，先从 中选出绝对值最中选出绝对值最大者作为主元，假定其位于第大者作为主元，假定其位于第p行第行第q列，然后交换系数阵列，然后交换系数阵A及及右端项阵右端项阵B的第的第k行与第行与第p行，并交换行，并交换A的第的第k列与第列与第q列，且交换列，且交换序列向量的第序列向量的第k个元素与第个元素与第q个元素的内容。个元素的内容。（1）设置一标识变量顺序的一维向量，其初始内容为）设置一标识变量顺序的一维向量，其初始内容为 基本思想基本思想Tn,3,2,1),1 (njiaij；),()1(njikakij主主

20、 元元 消消 去去 法法 （3）按高斯消去法完成第）按高斯消去法完成第k步消元，反复执行（步消元，反复执行（2），），直至消元过程结束；直至消元过程结束； （4）回代求解，解的顺序就是序列向量所示的顺序。）回代求解，解的顺序就是序列向量所示的顺序。主主 元元 消消 去去 法法167. 5944. 0167. 105333. 210833. 0056. 0167. 01消元第一次 1513181533126111 153181533126321321321xxxxxxxxx解解 6111153312151318行行互互换换第第一一、三三举例：全主元法举例：全主元法167. 5944. 0167.

21、 105333. 210833. 0056. 0167. 01消元第一次144. 3572. 100143. 2429. 010833. 0167. 0056. 01消元第二次解为解为000. 1,000. 3,000. 2132 xxx167. 5167. 1944. 0051333. 20833. 0167. 0056. 01列互换第二、三x2和和x3次序次序变化变化 全主元法的精度略优于列主元法，这是由于全主元法全主元法的精度略优于列主元法，这是由于全主元法是在全体系数中选主元，故它对控制舍入误差比较有效。是在全体系数中选主元，故它对控制舍入误差比较有效。但全主元法在计算过程中，需同时作

22、行与列的互换，因而但全主元法在计算过程中，需同时作行与列的互换，因而程序比较复杂，计算时间较长。列主元法的精度虽稍低于程序比较复杂，计算时间较长。列主元法的精度虽稍低于全主元法，但其计算简单，工作量大为减少，实践表明，全主元法，但其计算简单，工作量大为减少，实践表明，它与全主元法同样具有良好的数值稳定性，故列主元法是它与全主元法同样具有良好的数值稳定性，故列主元法是求解中小型稠密线性方程组的最好方法之一。求解中小型稠密线性方程组的最好方法之一。一般采用列一般采用列主元法。主元法。说明：说明：主主 元元 消消 去去 法法题题3 分别用列主元消去法和全主元消去法求解线性分别用列主元消去法和全主元消

23、去法求解线性方程组。方程组。000. 3643. 5072. 1000. 2000. 2623. 4712. 3000. 1000. 1000. 3000. 2001. 0321321321xxxxxxxxx精确解舍入到精确解舍入到4位有效数字为位有效数字为Tx)3675. 0 ,05104. 0,4904. 0(主主 元元 消消 去去 法法关于主元法的几点讨论关于主元法的几点讨论 （1 1）有两类系数阵可以避免选主元，直接使用高斯）有两类系数阵可以避免选主元，直接使用高斯消去法便可得到满意的结果。它们是：严格对角占优矩消去法便可得到满意的结果。它们是：严格对角占优矩阵和对称正定矩阵。阵和对称

24、正定矩阵。严格对角占优矩阵是指其元素满足严格对角占优矩阵是指其元素满足)1 ( ,niaanijijii或以列为准，其元素满足或以列为准，其元素满足)1( ,njaanjiijjj 严格对角占优矩阵严格对角占优矩阵必定是非奇异阵，且每步消元后，必定是非奇异阵，且每步消元后，仍保持对角占优的性质，因此，不必选主元。仍保持对角占优的性质，因此，不必选主元。 对称正定矩阵对称正定矩阵其行列式大于零，方程组可解，且在每其行列式大于零，方程组可解，且在每步消元中，剩下的子阵仍保持对角占优和对称性，因此不步消元中，剩下的子阵仍保持对角占优和对称性，因此不必选主元。必选主元。行行列列（2）关于病态方程）关于

25、病态方程002755853. 0006324242. 0068528. 2446949. 1446949. 1012671. 121xxTX9057. 5,4448. 80062807. 00063242. 000090000. 004469. 10127. 121xx其具有其具有5位有效数字的正确解为位有效数字的正确解为如把其系数阵也取成如把其系数阵也取成5位有效数字位有效数字0027559. 00063242. 00685. 24469. 14469. 10127. 121xx给出的错误解答为给出的错误解答为TX9786. 6,9773. 9第一步消元后第一步消元后该方程为一个病态方程。该

26、方程为一个病态方程。判断是否为病态方程判断是否为病态方程: :行列式很大或很小（如某些行列式近似相关）；行列式很大或很小（如某些行列式近似相关）；元素间相差大数量级，且无规则；元素间相差大数量级，且无规则；主元消去过程中出现小主元；主元消去过程中出现小主元；特征值相差大数量级。特征值相差大数量级。解决方法解决方法在已知方程组是病态的情况下（通过试算或理论分析），在已知方程组是病态的情况下（通过试算或理论分析），宜采用双倍或多倍字长进行高精度运算，以减弱有效位损宜采用双倍或多倍字长进行高精度运算，以减弱有效位损失的影响。失的影响。下面的误差校正算法下面的误差校正算法主主 元元 消消 去去 法法（

27、3）使解精确化的误差校正算法）使解精确化的误差校正算法)1()1()1()1()1()1()1()1()(RAYXXYRXXAAXBR设设X(1)是方程组是方程组AX=B的解。则得到误差向量的解。则得到误差向量（1）（2）（3）（4）（5）由（由（1），则），则令令则（则（2）即为）即为求解（求解（4），则校正后的近似解是），则校正后的近似解是 由于由于X（1），Y（1）是有误差的，故对解的校正可继续，是有误差的，故对解的校正可继续，直到满足误差要求为止。直到满足误差要求为止。)1()1()2(YXX主主 元元 消消 去去 法法检验相对误差。设检验相对误差。设为给定精度，如果为给定精度，如果

28、则执行则执行，继续修正近似解，直到，继续修正近似解，直到 为止。对为止。对某个某个K，若，若 ，说明算法失效，不能使解精确，说明算法失效，不能使解精确化，则终止计算。化，则终止计算。整个算法综述如下整个算法综述如下:取取用主元法解用主元法解修正近似解修正近似解计算误差向量计算误差向量计算相对误差计算相对误差BReAXBRYXXkRAYkkkkkkkkk/;, 2 , 1 , 0,)1()1()1()1()()()1()()()()1(kkee)(ne)()1(kkee; 1,)0()0()0(eBROX主主 元元 消消 去去 法法 三、高斯三、高斯约当消去法约当消去法12254632132321xxxxxxxx 前述消去法前述消去法包括消元回代两个过程包括消元回代两个过程。将消元过程略。将消元过程略加修改，把系数阵化为单位对角阵，则可免去回代。这加修改，把系数阵化为单位对角阵，则可免去回代。这种种将两个过程合二为一的消元算法就是高斯将两个过程合二为一的消元算法就是高斯约当消