高斯消去法课件.ppt

1、计算机数学基础(下)第5编 数值分析第第1010章章 线性方程组的数值解法线性方程组的数值解法本章主要内容本章主要内容：1.高斯消去法高斯消去法2.列主元消去法列主元消去法3.雅可比迭代法雅可比迭代法4.高斯高斯赛德尔迭代法赛德尔迭代法5.迭代法的收敛性迭代法的收敛性重点：高斯消去法、雅可比迭代法重点：高斯消去法、雅可比迭代法难点：迭代法收敛的判定难点：迭代法收敛的判定n元线性方程组的有关概念 由n个未知量，n道所有的未知量都是一次的方程组成的方程组称为n元线性方程组。习惯上我们用xj表示这些未知量，用aij表示它们的系数，用bj表示方程等号右边的常数。因此，n元线性方程组的一般形式为：nnn

2、nnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111n元线性方程组可以写成矩阵的形式 AXB其中：A A称为系数矩阵，是nn矩阵,X X称为未知量矩阵，b b称为常数矩阵，它们都是n1的列矩阵或称为n维列向量。当|A A|0时，方程组的解唯一存在。mnnnnnnnbbbbxxxXaaaaaaaaaA2121212222111211线性方程组的增广矩阵 由系数矩阵和常数矩阵并列构成的矩阵称为线性方程组的增广矩阵，记作A A|b b A A|b b nnnnnnnbaaabaaabaaa2122222111121110.1 高斯消去法 10.1.1 高斯

3、顺序消去法的基本思想 高斯消去法的基本思想是对线性方程组的增广矩阵进行行初等变换，使增广矩阵中的系数矩阵变为上三角矩阵，从而解出最后一个未知数 xn的值，然后在依次回代，求出其余的未知数的值。如果消元是按方程组的自然顺序进行的就称为高斯顺序消去法。例1.解线性方程组解：将方程组写成矩阵的形式 AXAXb b其中：A A|b b0115472321321321xxxxxxxxx0117111154112bA5.35.05.10333071120111111547112)21()24(312rrrr它相当于方程组：解得x35，回代到第2式可解得x2 4，再已将求出的x3，x2的值回代到第1式可解得

4、x1 -1方程组的解为(-1,4,5)T 5100333071125.35.05.10333071122321rr533372332321xxxxxx10.1.2 高斯顺序消去法公式记初始方程组 AXAXb b为 A A(0)(0)X Xb b(0)(0)第一次消元后的方程组记为A A(1)(1)X Xb b(1)(1)消元公式是：消元后的增广矩阵是：)1()1()1(2)1(2)1(2)1(22)0(1)0(1)0(12)0(1100nnnnnnbaabaabaaa),3,2(0/)0(11)0()1()1(1)0(11)0()1()0(11)0(11niblbbaalaaaaliiiiji

5、ijijii第二次消元的公式是怎样的呢？第二次消元后的方程组记为A A(2)(2)X Xb b(2)(2)第二次消元公式是：由此可得，),4,3(0/)1(22)1()2()2(2)1(22)1()2()1(22)1(22niblbbaalaaaaliiiijiijijii第k k次消元后的方程组记为A A(k)(k)X Xb b(k)(k),公式是：消元进行到第n1次时结束，),2,1(),2,1(0),2,1(),2,1(/)1()1()()()1()1()()1()1(nkkiblbbnkkiankkialaankkiaalkkikkikikikkkjikkijkijkkkkikik可求

6、出xn，然后回代。得到公式：)1,1(/)(/)1(1)1()1()1()1(niaxabxabxiiinijjiijiiinnnnnn)1()1()1()1()1(1)1()1(2)1(2)1(12)1(2)1(22)0(1)0(1)0(11)0(1)0(12)0(110000000000000000nnnnniiiiniiiiiiniiniibabaaabaaaabaaaaa小结：高斯顺序消去法解线性方程组的步骤：消元对k1到n1，若 进行消元 第k次消元公式前面已经给出。若 回代，方程组的解为),2,1,()0(njiaaijij令),2,1,()0(njibbii0)1(kkka0)1

7、(nnna)1,1(/)(/)1(1)1()1()1()1(niaxabxabxiiinijjiijiiinnnnnn定理1 线性方程组AXAXb b能用高斯消去法求解的充分必要条件是A A的各阶顺序主子式不为0。例2.用高斯消去法求解线性方程组解：写出增广矩阵A A|b b A A(0)(0)|b b(0)(0)19451236321321321xxxxxxxxx1941512316111第1次消元：各元素分别加到第2、3行上，得到 A A()|b b()第2次消元：A A(2)(2)|b b(2)(2)行的乘第用15,1,5,1,13121312111llaaa1114053206111行

8、上得到行的各元素加到第乘第用32232l2170053206111此时，系数矩阵部分已化为上三角矩阵，因为于是可以回代，得到：所以，原方程组的解为0)2(33a37/213x22/)335(2x11/)21316(1x321321xxx2001年7月试卷计算题11用高斯消去法求解线性方程组解：A A|b b1052321015102321321321xxxxxxxxx5.25.5707864801511021052131210151102消元结束回代,875.13625.4007864801511021220315,2483678,3625.4875.13123xxxTX)3,2,1(原方程组

9、的解为10.1.3 列主元消去法在高斯消去法中 我们把 分别称为第1步、第2步、第k步的主元，如果这些主元中的某一个主元0，当它做除数时就会使舍入误差增大，导致解的严重失真。)1()1()1(2)1(2)1(2)1(22)0(1)0(1)0(12)0(1100nnnnnnbaabaabaaa)1()1(22)0(11,kkkaaa为了提高算法的稳定性，应选取绝对值尽可能大的元素作为主元，这种消去法称为列主元消去法。例3.用列主元消去法解线性方程组解：A A|b b615318153312321321321xxxxxxxxx6111151318153312在第1列中选取绝对值最大的元素-18作为

10、主元，把第1行与第2行互换后再作第1次消元 A A(0)(0)|b b(0)(0)消元后再选取第2列主元A A(1)(1)|b b(1)(1)61111533121513181667.59444.01667.1053333.210151318再选取第2列主元，把第2行与第3行互换 A A(1)(1)|b b(1)(1)再消元得 A A(2)(2)|b b(2)(2)回代得53333.2101667.59444.01667.101513184285.91428.3001667.59444.01667.101513180000.1,0001.2,0000.3123xxx2002年1月试卷填空题8

11、用列主元消去法解线性方程组在作第1次消元之前，应选择主元 。134092143321321321xxxxxxxxx42002年1月试卷填空题8用列主元消去法解线性方程组作第1次消元之后的第个方程是 。解：A A|b b2333220221321321xxxxxxxx2031012133222031332201215.35.1205.15.01033225.35.1232xx 如果矩阵满足即主对角线上每一元素的绝对值均大于同行(列)其它元素绝对值之和，这样的矩阵称为严格对角占优矩阵。如果矩阵满足 ，各阶顺序主子式的值均为正数，这样的矩阵称为正定矩阵。正定矩阵和严格对角占优矩阵在消元过程中主元必是

12、 ，因此不必选主元，可以用顺序消元法解，而且一定满足前面所说的定理1的条件，用顺序消元法解一定可以进行到底。作业：P.23 带的练习题njiiijjjnijjijiiaaaa11或),2,1,(njiaaijji)1(kkka10.3 解线性方程组的迭代法 10.3.1 引言 设线性方程组AXb其中：若将线性方程组变形为等价的方程组XBXf建立迭代公式 X(k+1)BX(k)f，就可以从给定的初始向量X(0)出发，按上面的迭代公式得到解向量X(k),这种解法称为线性方程组的迭代解法。mnnnnnnnbbbbxxxXaaaaaaaaaA2121212222111211 能否用迭代法求出线性方程组

13、的解，关键在于向量序列X(k)是否收敛。设：如果，当 时X(k)的每一个元素都收敛。即 ，则称向量序列X(k)收敛，向量序列X(k)的极限向量为)()(2)(1)()2()2(2)2(1)2()1()1(2)1(1)1(,knkkknnxxxXxxxXxxxXncccC21k),2,1(lim)(nicxikik若向量序列X(k)收敛，设其极限向量为对迭代公式两边取极限：得 ，即因此，为方程组的解，此时称迭代法收敛。用迭代法解线性方程组需要解决两个问题：如何建立迭代公式，迭代收敛的条件是什么？*2*1*nxxxXlimlim)()1(fBXXkkkkfBXX*X10.3.2 雅可比迭代法将线性

14、方程组 AXAXb b改写成：得相应的迭代公式(雅可比迭代公式)：nnnnnnnnnnnnnaxaxaxabxaxaxaxabxaxaxaxabx/)(/)(/)(1122112223231212211131321211nnknnnknknnknknnkkkknnkkkaxaxaxabxaxaxaxabxaxaxaxabx/)(/)(/)()(11)(22)(11)1(22)(2)(323)(1212)1(211)(1)(313)(2121)1(1例2 求解线性方程组解：把方程组变形为：其雅可比迭代公式为：2.453.82102.7210321321321xxxxxxxxx84.02.02.0

15、83.02.01.072.02.01.0213312321xxxxxxxxx84.02.02.083.02.01.072.02.01.0)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx 取迭代初始值利用雅可比迭代公式计算，迭代过程如表，可见，随着迭代次数k的增加，迭代值 越来越接近原方程的精确解：一般地说，我们可以在预先给定的精度下停止迭代，把最后一次的迭代值作为原方程组的近似解。例如在此例中，如果精确到小数点后面5位小数，第13次迭代值与第12次迭代值相同，我们就可以用第13次迭代值作为方程组的解。0,0,0)0(3)0(2)0(1xxx)(3

16、)(2)(1,kkkxxx3.1,2.1,1.1*3*2*1xxx2002年1月试卷计算题11用雅可比迭代法解线性方程组从初始向量(0,0,0)T 开始，计算出第3次迭代结果，并要求写出迭代公式，计算过程中保留4位小数。解：迭代公式为：计算过程如表，解为：1052151023210321321321xxxxxxxxx)(2)(1)1(3)(3)(1)1(2)(3)(2)1(14.02.021.02.05.11.02.03.0kkkkkkkkkxxxxxxxxxT)8640.2,9260.1,9180.0(雅可比迭代的矩阵表示：线性方程组可以用矩阵表示为：其中nnnnnnnnnnnnnaxaxa

17、xabxaxaxaxabxaxaxaxabx/)(/)(/)(1122112223231212211131321211fXBX0nnnnnnnnnnabababfaaaaaaaaaaaaB222111212222221111111200002001年7月试卷选择题2用雅可比迭代法求解线性方程组构造迭代公式，则雅可比迭代矩阵B B002012432132121xxxxxxxx12101125.005.0)21101005.025.0)BA02110105.00)0210111025.0)DC雅可比迭代公式的矩阵形式为：若记fXBXkk)(0)1(nnnnaaaDaaaD100010001,000

18、000221112211则000000,00000021122121nnnnaaaUaaaL矩阵的分解为：其中：了解矩阵的分解可以帮助我们记忆下面所要学的高斯赛德尔迭代矩阵。是严格上三角矩阵是严格下三角矩阵是对角矩阵和1,ULDDbDfULDBULDA110),(10.3.3 高斯赛德尔迭代法高斯赛德尔迭代公式为：高斯赛德尔迭代公式的矩阵形式为：其中：nnknnnknknnknknnkkkknnkkkaxaxaxabxaxaxaxabxaxaxaxabx/)(/)(/)()1(11)1(22)1(11)1(22)(2)(323)1(1212)1(211)(1)(313)(2121)1(1gGX

19、Xkk)()1(bLDgULDG11)(,)(例3 用高斯赛德尔迭代法解线性方程组解：高斯赛德尔迭代公式为：取迭代初始值利用高斯赛德尔迭代公式计算，迭代过程如表，一般说来，高斯赛德尔迭代法比雅可比迭代法收敛快。2.453.82102.7210321321321xxxxxxxxx84.02.02.083.02.01.072.02.01.0)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx0,0,0)0(3)0(2)0(1xxx2002年1月试卷填空题7 用高斯赛德尔迭代法解线性方程组的迭代格式中，。52232122321321321xxxxxx

20、xxx)1(2kx)(3)1(123kkxx10.3.5 迭代法的收敛性定理4(迭代基本定理)若线性方程组XBXf对于任意初始向量X(0)及任意f，对应此线性方程组的迭代公式X(k+1)BX(k)f(k=0,1,2,)，收敛的充分必要条件是其中 是迭代矩阵B的特征根，当 为复数时 表示 的模。1|max1iniiii|i例5 设线性方程组AXAXb b，矩阵证明雅可比迭代法发散，而高斯赛德尔迭代法收敛。证明：矩阵A的雅可比迭代矩阵为：143434314343431A0434343043434300B特征方程为：矩阵A的高斯赛德尔迭代矩阵为：032271627434343434343)det()

21、(30BIf)1,2(,032121)2(,03249)1(ff雅可比迭代发散根据定理,4,1|1)(ULDG而000430043430,143430143001ULD644564901631690434300004300434301431630143001G的特征方程为解得特征根为：由定理4可知，高斯赛德尔迭代收敛。0)64276481(6445649016316904343)det()(2GIgi146.0633.0,03,21165.0|,0|3,21定理5(迭代法收敛的充分条件)设线性方程组XBXf，若矩阵B中的元素则对于任意初始向量X(0)及任意f，解此线性方程组的迭代公式X(k+1

22、)BX(k)f(k=0,1,2,)，收敛。该定理是充分条件，因此满足此条件的迭代一定收敛，不满足此条件不一定不收敛。所以，如题目要求证明某迭代法必收敛时可以用此方法证明，但如果题目要求判别某迭代法是否收敛或证明某迭代法发散，一般应采用定理4证明。1max1max1111niijnjnjijniijbbb或满足例6 设线性方程组AXAXb b，矩阵证明雅可比迭代法和高斯赛德尔迭代法都收敛。证明：矩阵A的雅可比迭代矩阵为：由定理5，雅可比迭代收敛。51121012110A3131014.0|max,02.02.02.001.02.01.00jijibB矩阵A的高斯赛德尔迭代矩阵为：由定理5，高斯赛

23、德尔迭代收敛。084.0022.0022.001.002.01.000002002102.002.0022.001.001.0001.01)(ULDG13.0|max3131ijjig作业P.6 四、证明题设解线性方程组试证明用雅可比迭代法求解收敛，而用高斯赛德尔迭代法求解发散。证明：1221122321321321xxxxxxxxx0221012200B122111221AB0的特征方程为：矩阵A的高斯赛德尔迭代矩阵为：0,0221122)det()(3,2,130BIf雅可比迭代收敛根据定理,4,1|1)(ULDG,122011001)(LD120100011010001001102120

24、011010001001100122010011001001G的特征方程为：000100220,120011001)(1ULD200320220000100220120011001G2,0)2(20032022)det()(3,22GIg赛德尔迭代发散高斯根据定理,4,1|3,2证毕2002年1月试卷选择题2 设线性方程组XBXf，n阶矩阵B的特征根为 ，对任意初始向量X(0)及任意f，对应此线性方程组的迭代格式X(k+1)BX(k)f(k=0,1,2,)，都收敛的充要条件是 。1)1|)11niiniiBA1|min)1|max)11iniiniDCC),2,1(nii定理6 设线性方程组AXAXb b，若A A是严格对角占优矩阵，则雅可比迭代法和高斯赛德尔迭代法收敛；若A A是对称正定矩阵，则高斯赛德尔迭代法收敛。前面的例6是严格对角占优矩阵，所以两种迭代法都收敛；例5是对称正定矩阵，所以高斯赛德尔迭代法收敛。作业：P.47 带的练习题,完成第1次大作业