《应用数值分析》课件数值分析5.3线性方程组的数值解法.pptx

1、第第5章章 线性方程组的数值解法线性方程组的数值解法5.2 方程组的性态与条件数-基本的高斯消元法5.3 高斯消元法高斯列主元消去法高斯 若当消去法矩阵的三角分解5.4 基于矩阵三角分解的方法 平方根法和改进的平方根法追赶法（三对角矩阵）-SOR雅可比迭代法5.5 雅可比迭代法和高斯 赛德尔迭代法高斯 赛德尔迭代法5.6 逐次超松弛迭代法（）直接法迭代法5.1 引言5.3 Gauss消消元元法法 用消元法解方程组用消元法解方程组 )4.2(.122(2.3),54(2.2),632132321xxxxxxxx)5.2(.11432 xx 第第2步步.解解)2()2.2()4.2(第第1步步.)

2、3.2()5.2(得等价的三角形方程组得等价的三角形方程组 .62)6.2(,54,6332321xxxxxx解为解为 .)3,2,1(Tx 上述过程相当于上述过程相当于 112251406111bA 1114051406111例例1 620051406111331)2(rrr332rrr 其中其中 表示矩阵的第表示矩阵的第 行行.iri1)消元过程消元过程23(1)(1)(1)(1)(1)11121311(2)(2)(2)(2)222322()()(3)(3)(3)3333(3)(3)(3)300000nnnnnnnaaaabaaabBBaabaabk(1)(1)(1)(1)(1)11121

3、11(2)(2)(2)(2)22222()()()()()(2)()00000knknkkkkkknkkknknnnaaaabaaabBaabaab2024-11-23线性方程组的直接解法11Gauss消去法算法消去法算法/ikikikkkalaankj,1 *.ijijikkjaala*iiikkbblb消元计算消元计算 nki,1 for 1,2,1 nkfor for 回代求解回代求解 nnnnabb/1,2,1 ni iinijjijiiababb/)*(1 for 2024-11-23线性方程组的直接解法12P计算量计算量 /*Amount of Computation*/由于计算机

4、中乘除由于计算机中乘除/*multiplications/divisions*/运算的时运算的时间远远超过加减间远远超过加减/*additions/subtractions*/运算的时间，故运算的时间，故估计某种算法的运算量时，往往只估计估计某种算法的运算量时，往往只估计乘除的次数乘除的次数，而且通，而且通常以乘除次数常以乘除次数的的最高次幂最高次幂为运算量的为运算量的数量级数量级。Gaussian Elimination:Step k：设设 ，计算因子，计算因子且计算且计算0)(kkka).,1(/)()(nkiaamkkkkikik ).,1,()()()1()()()1(nkjibmbb

5、amaakkikkikikkjikkijkij 共进行共进行n 1步步 )()2(2)1(121)()2(2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaa)()(/nnnnnnabx )1.,1()(1)()(niaxabxiiinijjiijiii(n k)次次(n k)2 次次(n k)次次(n k)(n k+2)次次nnnknknnk6523)2)(2311 消元乘除次数：消元乘除次数：1 次次(n i+1)次次22)1(1211nninni 回代乘除次数：回代乘除次数：2024-11-23线性方程组的直接解法13P计算量计算量 /*Amount of

6、Computation*/由于计算机中乘除由于计算机中乘除/*multiplications/divisions*/运算的时运算的时间远远超过加减间远远超过加减/*additions/subtractions*/运算的时间，故运算的时间，故估计某种算法的运算量时，往往只估计估计某种算法的运算量时，往往只估计乘除的次数乘除的次数，而且通，而且通常以乘除次数常以乘除次数的的最高次幂最高次幂为运算量的为运算量的数量级数量级。Gaussian Elimination:Step k：设设 ，计算因子，计算因子且计算且计算0)(kkka).,1(/)()(nkiaamkkkkikik ).,1,()()(

7、)1()()()1(nkjibmbbamaakkikkikikkjikkijkij 共进行共进行n 1步步 )()2(2)1(121)()2(2)2(22)1(1)1(12)1(11.nnnnnnnnbbbxxxaaaaaa)()(/nnnnnnabx )1.,1()(1)()(niaxabxiiinijjiijiii(n k)(n k+2)次次nnnknknnk6523)2)(2311 消元乘除次数：消元乘除次数：22)1(1211nninni 回代乘除次数：回代乘除次数：Gaussian Elimination 的总乘除次数为的总乘除次数为 ，运算量为，运算量为 级。级。nnn31323

8、33n n=20时时,顺序顺序Gauss消去法需消去法需3060次乘除法运算次乘除法运算.定理定理1 设设 其中其中 ,bAx.RnnA (1)如果如果),2,1(0)(nkakkk将将 约化为等价的三角形方程组约化为等价的三角形方程组bAx则可通过高斯消去法则可通过高斯消去法.)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11 nnnnnnnnbbbxxxaaaaaa (2)如果如果 为非奇异矩阵，则可通过高斯消去法为非奇异矩阵，则可通过高斯消去法(及交及交换两行的初等变换换两行的初等变换)将方程组将方程组 约化为约化为AbAx.)()2(2)1(121)()2(2)

9、2(22)1(1)1(12)1(11 nnnnnnnnbbbxxxaaaaaa？矩阵矩阵 在什么条件下才能保证在什么条件下才能保证 ).,2,1(0)(nkakkk A归纳法归纳法当当 时，成立时，成立.1k设设 时结论成立，时结论成立，即即1k证明证明:充分性充分性.,)()()()()2(2)2(2)2(22)1(1)1(1)1(12)1(11)()1(knnknkkknkkknknkkaaaaaaaaaaaAA且有且有 ),2,1(0kiDi),1,2,1(ki可用高斯消去法将可用高斯消去法将 约化到约化到 ，)1(A)(kA0)(iiia有有即即 ,0)2(22)1(11)2(22)1

10、(12)1(112aaaaaD (1)(1)111(1)(2)()1122()kkkkkkkkaaDaaaa定理定理2 约化的主元素约化的主元素 的的充要条件充要条件是矩阵是矩阵 的顺序主子式即的顺序主子式即),2,1(0)(kiaiiiA).,2,1(0kiDi11110(1,2,).iiiiiaaDikaa 由假设由假设),2,1(0)(kiaiii).,2,1(0kiDi推出推出 必要性必要性.,1)1(11Da).,3,2(/1)(nkDDakkkkk(k)0kka21221232xxx方如程组例 例例2 求解方程组求解方程组 .000.3000.2000.1643.5072.1000

11、.2623.4712.3000.1000.3000.2001.0321 xxx用用4 4位浮点数进行计算位浮点数进行计算.,)(*Tx0.3675 0.05104,0.4904,精确解舍入到精确解舍入到4 4位有效数字为位有效数字为 000.3643.5072.1000.2000.2623.4712.3000.1000.1000.3000.2001.0bA2000001.0/000.21000001.0/000.13121 mm 20036006400101002300520040000.1000.3000.2001.0997.12004/400123 m 解法解法1 1 用高斯消去法用高斯消

12、去法 .)(Tx0.4000 0.09980,0.400,000.2000.5001002300520040000.1000.3000.2001.0 计算解计算解显然计算解是一个很坏的结果，不能作为方程组的近似解显然计算解是一个很坏的结果，不能作为方程组的近似解.？原因：原因：在消元计算时用了小主元在消元计算时用了小主元 0.0010.001，使得约化，使得约化后的方程组元素数量级大大增长，经再舍入使得计算时后的方程组元素数量级大大增长，经再舍入使得计算时发生了严重的相消情况，因此经消元后得到的三角形方发生了严重的相消情况，因此经消元后得到的三角形方程组就不准确了程组就不准确了.解法解法2 0

13、00.1000.3000.2001.0000.2623.4712.3000.1000.3643.5072.1000.231rrbA0005.05000.03121 mm 002.1003.3001.205000.0801.1176.30000.3643.5072.1000.26300.032 m,6870.0868.1005000.0801.1176.30000.3643.5072.1000.2 计算解为计算解为 .*)(xxT 0.3678 0.05113,0.4900,交换行，避免绝对值小的主元作除数交换行，避免绝对值小的主元作除数.000.3000.2000.1643.5072.1000

14、.2623.4712.3000.1000.3000.2001.0321 xxx,)(*Tx0.3675 0.05104,0.4904,12120.00001223方程组例如xxxx122.000010009,00.99998999.9xx准确到小数点后第 位的解为,如果计算过程用四位十进制浮点数（仿机器实际计算）1,用第一个方程消去第二个方程中的x 得412662100.1000100.2000100.2000100.2000100.2000 xxx211,0,.由此解得显然它不是原方程的解xx选主元消去法：列主元和全主元12312312322558344xxxxxxxxx 求解线性方：程3组

15、例21255118134421,2511第 列的列主元行与 行交换a51182125134412/5,1/52,3第 行分别乘以并加到行511801.41.61.802.84.25.6322,2.832第 列的列主元行与 行交换a511802.84.25.601.41.61.821/23行乘以加到 行511802.84.25.6000.51回代求解321211，xxx每一步选取系数矩阵每一步选取系数矩阵(或消元后的低阶矩阵或消元后的低阶矩阵)中绝对值最大的中绝对值最大的元素作为主元素，以使高斯消去法具有较好的数值稳定性元素作为主元素，以使高斯消去法具有较好的数值稳定性.列主元法：优点：计算简单

16、，缺点：精度略低全主元法：优点：精度略优，缺点：计算时间较长计算经验与理论分析均表明：列主元法和全主元法同样具有良好的数值稳定性，故列主元法是求解中小型稠密线性方程组的良好方法之一。12312312322558244xxxxxxxxx 用高斯若当消去法求解线性方程组例5：212551181344511821251344511801.41.61.802.84.25.6511802.84.25.601.40.51.8502.51002.84.25.6000.51500502.802.8000.511001010100121231,1,2 xxx计算高斯若当法复杂度：3/2,n解方程组大约需要次乘除法 比高斯消去法大.因此一般并不用于解方程组，而是矩阵求逆求矩高斯若当法阵的逆：A I对分块矩阵作高斯若当消元(经过初等行变换)，1,AIIA当把化为单位阵时 单位矩阵即化为123=212134A例6用高斯若当列主元消去法求：矩阵的逆|123100212010134001A I21201012310013400121201001.5210.5002.5300.5121201002.5300.5101.5210.50200.801.20.402.5300.51000.210.50.620042202.50152.510000.210.20.61002110106140015131|I A