数值计算方法与算法.ppt

《数值计算方法与算法.ppt》由会员分享，可在线阅读，更多相关《数值计算方法与算法.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于数值计算方法与算法现在学习的是第1页，共47页 求解线性方程组 Ax=y，可用直接法。当 A 为稀疏矩阵时，直接法将破坏矩阵 A 的稀疏性。我们可以对线性方程组进行等价变换，构造出等价方程组 x=Mx+g,由此构造迭代关系式例如，分解A=N-P，则(1)(),0,1,2,kkxMxgk1111 (),(,),NP xyNxPxyxNPxNyMxg MNP gNy(0)(0)(0)(0)T12(1)(2)Take any initial vector(,),we obtain iterative sequences,This is the iterative method to be dis

2、cussed.nxxxxxx现在学习的是第2页，共47页迭代法：构造一个向量序列 x(k)，使其收敛到某个极限向 量 x*，即 则x*就是线性方程组的解。常用迭代方法：雅可比迭代，高斯-赛德尔迭代，松弛迭代等。()*,kxx现在学习的是第3页，共47页6.1 6.1 雅可比迭代6.1.1 雅可比迭代格式迭代格式 线性方程组 Ax=y，即 11112211211222221122 (6.1)nnnnnnnnnna xa xa xya xa xa xya xa xa xy现在学习的是第4页，共47页若aii0,i=1,2,n,（6.1）可变为记 则1311211231111111123221221

3、322222222,112121 nnnnn nnnnnnnnnnnnnnaaayxxxxaaaaaaayxxxxaaaaaaayxxxxaaaa /,/,ijijiiiiiibaagya 1122133112211233221122,11 nnnnnnnn nnnxb xb xb xgxb xb xb xgxb xb xbxg现在学习的是第5页，共47页写成矩阵形式或简记为 对任意初始向量 构造迭代格式：(6.2)是称为简单迭代或雅可比迭代。1121311122123222331323331230000nnnnnnnnnxbbbxgxbbbxgxbbbxgxbbbxg(0)(0)(0)(0)

4、12 .(,),nxBxgxxxx(1)(),0,1,2,(6.2)kkxBxg k现在学习的是第6页，共47页 雅可比迭代矩阵 记所以 称为雅可比迭代矩阵，是常数项向量。11221122diag(,),nnnnaaDaaaa1111,From,we have ()()()().ADADAxyDAD xyDxDA xyxDDA xDyIDA xDy1(),BID A1gDy现在学习的是第7页，共47页如果通过(6.2)构造的迭代序列x(k)收敛，即则 x*为 Ax=y的解，即 Ax*=y。事实上，对(6.2)取极限得()lim*,kkxx11 *()*,*,i.e.*is a solution

5、 of.xBxgxID A xDyAxyxAxy现在学习的是第8页，共47页迭代格式的收敛性引理6.1(线性代数定理)设矩阵序列 则 （证明见关治和陈景良编数值计算方法P410412）定理6.1 设迭代格式为 由初始向量x(0)产生的向量序列x(k)收敛的充分必 要条件是证明 必要性（）设 则由（6.3）得(1)(),0,1,2,(6.3)kkxMxg k()1.M2,kI M MM()lim0 ()1.kkxM()lim*,kkxx*.(6.4)xMxg现在学习的是第9页，共47页(6.3)-(6.4)得设第k次迭代的误差记为充分性（）设(M)1,证x(k)收敛。如果(M)1，则I-M为非奇

6、异矩阵。事实上，因为(M)1，i1，因此=1不是M的特征值，即(1)()()*()(*)(*)kkkxxMxgMxgM xx()*,thuskkxx21110,kkkkMMM11(1)001 limlimlim(*)0,.i.e.lim0.From we have()1.kkkkkkkkMxxMM|1|0.IMIMLemma 6.1,现在学习的是第10页，共47页所以方程组(I-M)x=f 有惟一解x*,满足(I-M)x*=f，即x*=Mx*+f。于是由引理6.1知，()(1)2(2)(0)0*(*)(*)(*).kkkkkxxM xxMxxMxxM()()If ()1,then lim0,l

7、im(*)0,i.e.lim*.kkkkkkMMxxxxThis completes the proof.现在学习的是第11页，共47页例6.1 设系数矩阵为 判定雅可比迭代格式的收敛性。解 雅可比迭代矩阵为特征方程为 1 221 11,2 21A022101,(/).220ijijiiMBbaa 322|110,0,thus()0.From(1),we havekjj nxknxx 111.Contradiction.nnnkjjkjjkkkjkjjjkj kj kj kaxa xaaxx By the definition of strictly diagonally dominant,0

8、.iia 现在学习的是第17页，共47页 当方程组的系数矩阵为严格对角占优时，关于雅可比迭代我们有下面的定理。定理定理 6.3 6.3 当系数矩阵为严格对角占优时，雅可比迭代收敛。证明 方法一：根据严格对角占优矩阵的定义。雅可比迭代矩阵：(),where /,;0.ijn nijijiiiiBbbaaji b 111111|()maxmax|=max|/|1,Jacobi converges.nnijiji ni niijjj inijiii njj iaBBbaaa 现在学习的是第18页，共47页方法二：反证法。因为A为严格对角占优矩阵，由引理6.2知，aii0.11122,diag(,).

9、nnBID A Daaa111 Assume()1,then matrix exists some eigenvalue ,such that|1,and det()0.However,on the one hand,()(),det()=det()det()=0.BBIBIBIID ADDADIBDDAD1det()0,det()=0.(1)DDADBut on the other hand,现在学习的是第19页，共47页111212122212 (2)nnnnnnaaaaaaDADaaa 1Because|1,|,1,2,.is strictly diagonally dominant.n

10、iiiiijjj iaaainDADBy Lemma 6.2,we have det()0 (3)(3)contradicts with(1).Thus()1.DADB现在学习的是第20页，共47页 雅可比迭代算法(1)(),0,1,2,(6.2)kkxBxg k(1)()()()112213311(1)()()()221123322(1)()()()331132233(1)()()(1122,11i.e.kkkknnkkkknnkkkknnkkkknnnn nnxb xb xb xgxb xb xb xgxb xb xb xgxb xb xbx)(6.5)ng算法描述：1.输入系数矩阵A和常

11、数项向量y；2.形成雅可比迭代矩阵B和向量g现在学习的是第21页，共47页3.赋初始值 FOR =1,2,.,/FOR =1,2,.,/0iiiiijijiiiiingyajnbaab T()T(1)10,0,.,0(stands for)21,1,.,1(stands for)kkxxxx现在学习的是第22页，共47页4.实现迭代5.输出方程组的解 x2i，i=1,2,n.6WHILE 12 10 1:2FOR 1,2,.,0 21 FOR 1,2,.,*1 2 ENxxxxunsxBxgvnssb u vx vxusg uDWHILE现在学习的是第23页，共47页6.2 高斯-塞德尔(Ga

12、uss-Seidel)迭代 高斯-塞德尔迭代的计算 在雅可比迭代(6.4)的迭代过程中，可用新求出的x(k+1)的分量来代替x(k)的分量参与计算，直到用x(k+1)的前n-1分量代替x(k)的前n-1个分量求出 为止，即可由（6.5）得到高斯-塞德尔迭代：(1)()()()112213311(1)(1)()()221123322(1)(1)(1)()331132233(1)(1)(1)1122,1 kkkknnkkkknnkkkknnkkknnnn nxb xb xb xgxb xb xb xgxb xb xb xgxb xb xb(1)1 (6.6)knnxg(1)knx现在学习的是第24

13、页，共47页令B=L+U，其中则高斯-赛德尔迭代可写成矩阵形式或写成其中，为高斯-塞德尔迭代矩阵，121312123231321,11200000,000nnnnn nnnbbbbbbbbLUbbbb(1)(1)(),0,1,2,.,(6.7)kkkxLxUxg kn(1)1()1()()(),0,1,2,.,(6.8)kkkxILUxILgSxfkn1()SILU1().fILg现在学习的是第25页，共47页 高斯-塞德尔迭代的收敛性 由定理6.1知，高斯-塞德尔迭代收敛的充分必要条件为 也可以利用条件 来判断高斯-塞德尔迭代收敛。定理定理 6.4 6.4 当系数矩阵为严格对角占优时，高斯-

14、塞德尔迭代收敛。证明证明 类似于定理6.3的证明。反证法。()1.S1S 1Gauss-Seidel iterative matrix is ().SILU Assume()1,then matrix exists some eigenvalue ,such that|1,and det()0.SSIS现在学习的是第26页，共47页1111111 However,on the one hand,()()()()()()(),det()=det()det)det()=0.det(ISIILUILILUILILUILDDDLDUISILDDDLDUI11)0,det()0,det()=0.(1)L

15、DDDLDU111212122212But,on the other hand,.nnnnnnaaaaaaDDLDUaaa现在学习的是第27页，共47页1111Because is strictly diagonally dominant,and|1,|,1,2,is also strictly diagonally dominant.By Lemma 6.2,det(niniiijijijjjj ij iAaaaainDDLDU)0,this contradicts with(1).Therefore()1.This completes the proof.DDLDUS现在学习的是第28页，

16、共47页定理定理 6.5 6.5 当系数矩阵A为正定矩阵，高斯-塞德尔迭代收敛。证明证明 11 ().Assume is any eigenvalue of,and is a correspondingeigenvector of,then (),(),or ().SILUSxILUxxUxIL xDUxDDL xDo inner product with at two sides,(,)(),),(,).(1)(),)xDUx xDDL x xDUx xDDL x x现在学习的是第29页，共47页The decomposition of is as follows:.Because is p

17、ositive definite,so (,)(),)0i.e.(),)(,)From(1),we have 1.Thus G-S does not converge.ISM 111 0 0100 1 1 0,()110.2 2 102 1022()023.002ILILSILU 现在学习的是第32页，共47页 高斯-塞德尔迭代算法 根据(6.6)，可以写出高斯-塞德尔迭代的核心部分：记()()()T(1)(1)()()T11111 1(,),2(,).kkkkkkkiinxxxxxxxxx6WHILE 1210 FOR (1;)1 2 FOR (1;)FOR (1;)xxuun ux uxu

18、iin isg ijjn j *2 ENDWHILEssb ijxjin detail asnext page 2 xis现在学习的是第33页，共47页FOR (1;)*2 FOR (1;)*1 2 jji jssb ijxjjijn jssb ijxjxis 现在学习的是第34页，共47页6.3 松弛迭代 高斯-塞德尔迭代为松弛迭代法是高斯-塞德尔迭代法的一种变化形式。令(1)(1)(),0,1,2,.,(6.7)kkkxLxUxg kn(1)()(1)()(1)()(1)()(),then +.From(6.7),=.DefinekkkkkkkkkxxxxxxxxxLxUxgxRelaxa

19、tion iterative mehtod,(1)()()(1)()()()(1)()()(1)()(6.9)kkkkkkkkkxxxxLxUxgxxLxUxg 现在学习的是第35页，共47页其中，参数0称为松弛因子。将(6.9)变形为(6.9)或(6.10)称为松弛迭代法。迭代矩阵为 当01时，称为低松弛迭代；当12时，称为超松弛迭代；当=1时，即为高斯-塞德尔迭代。(1)()(1)1()1()1 (1)(1),(1)(1)(1)(1)(6.10)kkkkkL xIU xgxLIU xLgS xLg1(1)(1).SLIU1(1),SLUS现在学习的是第36页，共47页 实际用计算机计算时，

20、采用(6.9)的分量形式，即 雅可比迭代、高斯-塞德尔迭代和松弛迭代均为单步线性迭代。(1)()()()()1112213311(1)()(1)()()222112332(1)(1)()(1)()(kkkkknnkkkkknnnknxxb xb xb xgxxb xb xb xgx()(1)(1)(1)1122,111)()(6.11)kkkknnnn nnnxb xb xbxg现在学习的是第37页，共47页 松弛迭代的收敛性定理定理 6.6 6.6 松弛迭代收敛的必要条件是02。即若松弛迭 代收敛，则必有02。证明证明 松弛迭代矩阵 其中，1(1)(1).SLIU2112121211 ,11

21、1(1).1nnnnbILbbbbbIU 现在学习的是第38页，共47页 如果松弛迭代收敛，由定理6.1知，即S的所有特征值的绝对值均小于1。由特征方程的性质得 由（1）和（2）两式得11 det()=1,det()=1.Thusdet det(1)det(1)(1).(1)nILILSLIU()1,S12det.(2)nS 12|1|det|1,i.e.|1|1 0 2.nnS 现在学习的是第39页，共47页定理定理 6.7 6.7 如果系数矩阵A为严格对角占优，当松弛因子 时，则松弛迭代收敛。证明类似于定理6.4。定理定理6.86.8 若A为对称正定矩阵时，则当 时，松弛迭代收敛。0102

22、现在学习的是第40页，共47页 松弛迭代算法 基本上与高斯-塞德尔迭代算法相同。6WHILE 1210 FOR (1;)1 2 FOR (1;)FOR (1;)xxuun ux uxuiin isg ijjn j *2 ENDWHILEssb ijxj2(1)1*x ix is现在学习的是第41页，共47页6.4 逆矩阵的计算1.用初等变换2.用伴随矩阵3.用逆矩阵的定义：1 .A II A11*|AAA11,(),(),i.e.ijijA AI AaAx1112111121212222122212121 000 10.0 01nnnnnnnnnnnnaaaxxxaaaxxxaaaxxx 现在学习的是第42页，共47页化为n个线性方程组：用直接法或迭代法算出：也就完成了逆矩阵 的计算。111121221222120,1,2,.10jnjnnnnnnjxaaaxaaajnaaax T12(,),1,2,jjnjxxxjn1A现在学习的是第43页，共47页2005.12.9现在学习的是第44页，共47页现在学习的是第45页，共47页6.5 程序示例现在学习的是第46页，共47页感谢大家观看感谢大家观看现在学习的是第47页，共47页