(3.1)--数值分析第三章线性方程组解法.pdf

数值分析课件数值分析课件同学们好！现在开始讲授第三章线性方程组解法线性方程组解法首先讲授数值分析课件数值分析课件第三章第三章 线性方程组解法线性方程组解法讲授：线性方程组计算机求解常用方法的构造技术重点论述:Jacobi迭代法、Seidel迭代法、Guass消元法及LU分解法的构造、收敛性等。数值分析课件数值分析课件本章讲授内容本章讲授内容3.1 3.1 引例引例3.2 3.2 基本概念基本概念3.3 3.3 线性方程组的迭代解法线性方程组的迭代解法3.4 3.4 线性方程组的直接解法线性方程组的直接解法3.5 3.5 线性方程组解对系数的敏感性线性方程组解对系数的敏感性数值分析课件数值分析课件3.1 3.1 引例引例线性方程组是怎么产生的？它的解有什么用处？数值分析课件数值分析课件某大型输电网络可用如下线性方程组表示：式中R1,R2,Rn表示负载电阻；r1,r2,rn表示线路内阻。()()()1111 211 122221100nnnnnnnRr IrIrIVR IRrIr IRIRrI+=+=+=为设计目的，需要知道其电源电压V=18，R1=R2=Rn=6，r1=r2=rn=1及n=20时各负载上的电流I1，I2，I20的值。数值分析课件数值分析课件122012201920718670670IIIIIIII+=+=+=即求满足如下线性方程的 I1，I2，I20的值实际中，人们经常遇到自变量个数很大的线性方程组求解问题，如地区天气预报、集成电路设计等，它们通常因为阶数很大使人工求解无效，必须要借助计算机的才能求出解！如何用计算机快速有效地求解线性方程组就变得很重要。线性方程组数值分析课件数值分析课件3.2 3.2 基本概念基本概念解线性方程组问题要知道哪些概念？数值分析课件数值分析课件1、线性方程组的表示2、线性方程组的解3、线性方程组的解法数值分析课件数值分析课件1 1、n n元线性方程组的表示元线性方程组的表示1112111212222212,nnnnnnnnaaaxbaaaxbAxbaaaxb=，11 11221121 1222221 122nnnnnnnnnna xa xa xba xa xa xba xa xa xb+=+=+=一般表示：矩阵表示：Ax=b数值分析课件数值分析课件2 2、线性方程组的解、线性方程组的解11 11221121 1222221 122nnnnnnnnnna xa xa xba xa xa xba xa xa xb+=+=+=*12,nxxx若有n个数成立：*11 112211*21 122222*1 122nnnnnnnnnna xa xa xba xa xa xba xa xa xb+=+=+=方程组的解数值分析课件数值分析课件1）直接法直接法用计算公式直接计算求出线性方程组解的方法。3、线性方程组解法2 2）迭代法）迭代法用迭代公式通过迭代计算求出满足精度要求的线性方程组近似解的方法。迭代法是一种逐次逼近线性方程组解的方法。迭代法是一种逐次逼近线性方程组解的方法。线性方程组计算机解法有直接法和迭代法两大类。#数值分析课件数值分析课件数值分析课件数值分析课件同学们好！下面讲授线性方程组的迭代解法。该内容分8集讲授。第1集：数值分析课件数值分析课件3.3 3.3 线性方程组的迭代解法线性方程组的迭代解法线性方程组的迭代解法与简单迭代法有关系吗？怎样构造线性方程组的迭代解法？数值分析课件数值分析课件1 1、基本思想、基本思想将线性方程组 Ax=b 等价变形为 x=Bx+g,然后构造向量迭代公式()()1,0,1,2kkxBxg k+=+=线性方程组迭代解法公式类似非线性方程求根类似非线性方程求根的简单迭代法公式，有Jacobi迭代法、Seidel迭代法及Sor法等。()()()10kkf xxxxx+=给定一个初始向量 x(0)，代入迭代公式计算出迭代向量序列：x(1),x(2),x(k),数值分析课件数值分析课件()()()()()()()()()()()()()()1111 11221111221 12222211 122kkkknnkkkkkknnkkkknnnnnnnxb xb xb xgxb xb xb xgxBxgxb xb xb xg+=+=+=+=+11112111111 11221122122222221 122222121 122nnnnnnnnnnnnnnnnnnnnxbbbxgxb xb xb xgxbbbxgxb xb xb xgAxbxBxgxbbbxgxb xb xb xg=+=+=+=+=+不动点方程组线性方程组的等价变形：数值分析课件数值分析课件1、迭代公式构造2、向量迭代格式3、范数4、数值分析中的范数5、谱半径6、迭代收敛定理7、收敛误差估计8、迭代法例题数值分析课件数值分析课件数值分析课件数值分析课件11 11221121 1222221 122nnnnnnnnnna xa xa xba xa xa xba xa xa xb+=+=+=1、Jacobi 迭代公式构造迭代公式构造等价变形等价变形1112213 31112221 123 32221 122111()1()1()nnnnnnnnnnnnnxba xa xa xaxba xa xa xaxba xa xaxa=Jacobi迭代的不动点方程组数值分析课件数值分析课件把不动点方程写成迭代格式111221331112221 12332221 122111()1()1()nnnnnnnnnnnnnxba xa xa xaxba xa xa xaxba xa xaxa=-(1)()()()11122133111(1)()()()2221 1233222(1)()()()1 122111()1()1()kkkknnkkkknnkkkknnnnnnnnnxba xa xa xaxba xa xa xaxba xa xaxa+=Jacobi迭代格式取定初始向量()()()()()000012,Tnxxxx=可逐次算出向量序列x(1),x(2),x(k),数值分析课件数值分析课件-(1)()()()11122133111(1)()()()2221 1233222(1)()()()1 122111()1()1()kkkknnkkkknnkkkknnnnnnnnnxba xa xa xaxba xa xa xaxba xa xaxa+=-(1)()()()11122133111(1)(1)()()22211233222(1)(1)(1)(1)1122111()1()1()kkkknnkkkknnkkkknnnnnnnnnxba xa xa xaxba xa xa xaxba xa xaxa+=Seidel 迭代格式Seidel迭代不能取代Jacobi迭代!Seidel迭代又称为Gauss-Seidel迭代。2、Seidel迭代公式构造是Jacobi 迭代公式的改进！数值分析课件数值分析课件3、Sor 迭代公式构造()1kx+用Seidel迭代格式算出的记为得到增量：做增量加速处理()1kx+()()1kkxxx+=()()()()()111kkkkxxxxx+=+=+()()()()()1111111,2,inkkkkiiiijjijjjj iiixxba xa xina+=+=+=Sor迭代格式Sor法又称为超松弛迭代法。是Seidel 迭代公式的改进！数值分析课件数值分析课件1232321313312121(72)0.70.10.2101(8)0.80.10.1101(4)0.80.20.25xxxxxxxxxxxxxxx=+=+=+=+=+=+例例1 1、写出如下线性方程组的、写出如下线性方程组的3 3种迭代格式种迭代格式123123123102710854xxxxxxxxx=+=+=解：求不动点方程组：数值分析课件数值分析课件1232133120.70.10.20.80.10.10.80.20.2xxxxxxxxx=+=+=+所以不动点方程组为：Jacobi迭代格式()()()()()()()()()k+1kk1231kk213k+1kk3120.70.10.20.80.10.10.80.20.2kxxxxxxxxx+=+=+=+Seidel迭代格式：()()()()()()()()()k+1kk1231k+1k213k+1k+1k+13120.70.10.20.80.10.10.80.20.2kxxxxxxxxx+=+=+=+Sor迭代格式：()()()()()()()()()()()()kk(1)1123k+1k(1)2213k+1k+1(1)33121(0.70.10.2)1(0.80.10.1)1(0.80.20.2)kkkkkkxxxxxxxxxxxx+=+=+=+()()()()111kkkxxx+=+#数值分析课件数值分析课件数值分析课件数值分析课件同学们好！下面继续讲授线性方程组的迭代解法。第2集：数值分析课件数值分析课件数值分析课件数值分析课件把Jacobi迭代格式(1)()()()11122133111(1)()()()2221 1233222(1)()()()1 122111()1()1()kkkknnkkkknnkkkknnnnnnnnnxba xa xa xaxba xa xa xaxba xa xaxa+=写成向量型式(1)1()1213111111(1)1()21232222221(1)1()121000kknkknnnkknnnnnnnnnaaabxaxaaabxaxaaaabxax+=+1 1、JacobiJacobi向量迭代格式向量迭代格式数值分析课件数值分析课件1212121200000000,0000nnnnaaaaLUaa=1122,nnaaDa=记()()()()1122,kkkknnxbbxxbbx=有111212122212nnnnnnaaaaaaADL Uaaa=111212122212121200,0nnnnnnnnaaaaaaaDLL Uaaaaa=+=数值分析课件数值分析课件由Jacobi向量型式()()()111kkxDL U xD b+=+()()1kkJJxB xg+=+记：()11,JJBDL UgD b=+=得Jacobi向量迭代格式(1)1()1213111111(1)1()21232222221(1)1()121000kknkknnnkknnnnnnnnnaaabxaxaaabxaxaaaabxax+=+()1JBDL U=+称为Jacobi迭代矩阵。数值分析课件数值分析课件2 2、Seidel Seidel 迭代的向量迭代格式迭代的向量迭代格式(1)1(1)121311111(1)1(1)212322222(1)1(1)12100000000000kknkknkknnnnnnnnaaaxaxaaaxaxaaaxax+=+()11()221()0000kknnknnbxbxabx +写成向量型式有(1)()()()11122133111(1)(1)()()2221 1233222(1)(1)(1)(1)1 122111()1()1()kkkknnkkkknnkkkknnnnnnnnnxba xa xa xaxba xa xa xaxba xa xaxa+=SeidelSeidel迭代格式数值分析课件数值分析课件()()1kkSsxB xg+=+得(1)1(1)121311111(1)1(1)212322222(1)1(1)12100000000000kknkknkknnnnnnnnaaaxaxaaaxaxaaaxax+=+()11()221()0000kknnknnbxbxabx +()()()()111kkkxDLxUxb+=+()()()()()()()()()()111111kkkkkkkDxLxUxbDL xUxbxDLUxDLb+=+=+=+记：()()11,SSBDLUgDLb=得Seidel向量迭代格式()1sBDLU=称为Seidel迭代矩阵。数值分析课件数值分析课件3、Sor法向量迭代格式把Sor迭代格式用矩阵表示，有()()()()()()1111kkkkxxDbLxUx+=+()()()()()()111kkkkDxDxbLxUx+=+()()()()()11kkDL xDU xb+=+()()()()()()1111kkxDLDU xDLb+=+得Sor法向量迭代格式()()1kkxB xg+=+()()()111,BDLDUgDLb=+=数值分析课件数值分析课件上面三种向量迭代格式可以统一写成上面三种向量迭代格式可以统一写成()()1kkxBxg+=+B为迭代矩阵这里三种迭代对应的迭代矩阵为这里三种迭代对应的迭代矩阵为()()111JBDLUDDAID A=+=()1SBDLU=()()11BDLDU=+#数值分析课件数值分析课件数值分析课件数值分析课件同学们好！下面继续讲授线性方程组的迭代解法。第3集：数值分析课件数值分析课件数值分析课件数值分析课件limlim0kkkkxaxa=数列收敛：向量收敛()*limkkxx=()*lim,1,2,kiikxx in=()()()()*11*22*,kkkknnxxxxxxxx=收敛的本质是距离趋于0，两个实数的距离是绝对值，那么向量的距离怎样描述呢？用范数！数值分析课件数值分析课件1 1、范数定义、范数定义1000;2);3)xxxxxxyxy=+）且设L是数域K上的一个线性空间，如果定义在L上的实值函数 P(x)满足:1)()0()00 xLP xP xx=、；()2),();xLKPxP x=()()3),()x yLP xyP xP y+则称P是L的范数，P(x)为x的一个范数。()pP xxx=记则1000;2);3)xxxxxxyxy=+）且比较数值分析课件数值分析课件2 2、数值分析中常用的线性空间、数值分析中常用的线性空间()12|,nnkRa aa aaaR=1 1）n n维向量空间维向量空间3 3）连续函数空间）连续函数空间,C a b=f(x)f(x)在a，b上连续2 2）矩阵空间）矩阵空间()|,m nm nm nijijm nRAAaaR=线性运算定义：()()()()()()():,fgfgxf xg xffxf x+=+=为数数值分析课件数值分析课件n nR1)0,00;n nARAAA=2),(;n nARKAA=数域）3),n nA BRABAB+4),(n nA BRABAB相容性）矩阵范数要满足如上四条！对比一下向量范数！1000;2);3)xxxxxxyxy=+）且3、中的矩阵范数定义数值分析课件数值分析课件例2、证明 若B1,则有I+B可逆，且()11IIBB+4、范数证明例题这里.是矩阵范数。证明:(反证法)假设I+B不可逆，则对应齐次方程组()0IB x+=()0IB xBxx+=有非零解，设为，有x两边取范数两边取范数，并利用范数定义BxBxxx=01xB矛盾！故I+B可逆。0;AAAABABABA B=+数值分析课件数值分析课件()()()()111IBIBIIBIB IB+=+=+两边取范数，并利用矩阵范数定义()()()111IBIB IBIBIB+()11IIBB+0;AAAABABABA B=+#数值分析课件数值分析课件数值分析课件数值分析课件同学们好！下面继续讲授线性方程组的迭代解法。第4集：数值分析课件数值分析课件数值分析课件数值分析课件1.nR中的向量范数111)nkkxx=2212)nkkxx=13)maxkk nxx=式中向量()12,Tnxx xx=例如()122221,2,3,123612314max 1,233Txxxx=+=+=则有；数值分析课件数值分析课件AxA x由范数相容性0AxxAx若矩阵A的算子范数定义：0maxnPPx RpxAxAx=2、矩阵算子范数,n npAR这里为n维向量的某种范数。12,AAA常用的有p=1,2,对应有，算子范数矩阵范数，反之不可！pppAxAx显然有数值分析课件数值分析课件1111)maxnijj niAa=列范数：112)maxniji njAa=行范数：2,13)nijFi jFAa=范数：Tmaxmax24)2A=范数：，是A A的最大特征值F范数不是算子范数，其他3个是算子范数。3.n nR中的矩阵范数例如00.40.60.2500.50.20.30A=11,1.1,0.981071FAAA=数值分析课件数值分析课件1),pqpm xxM xxL 范数等价：nR 上所有范数都是等价的。()()*2)limlim0,kkkkxxxx=n是R 上任何一个向量范数。4 4、范数等价与向量极限、范数等价与向量极限()()()*kkkpqpm xxxxM xx#数值分析课件数值分析课件数值分析课件数值分析课件同学们好！下面继续讲授线性方程组的迭代解法。第5集：数值分析课件数值分析课件谱半径数值分析课件数值分析课件1 1、谱半径定义、谱半径定义()1maxkk nA=22kkkabiab=+=+注：是复数时，,1,2,n nkARAkn=是 的特征值,称为矩阵A的谱半径。()2 222-3A=max 2,3=3AR例的 个特征值为，()()3 322222i-2A=Max 21,21,-25AR+=例的3个特征值为，数值分析课件数值分析课件定理1(),AA 是任意的矩阵范数。证明()()()kkkkkAxAxx=设是 的任意特征值，是对应的特征向量，则有2 2、谱半径与矩阵范数的关系、谱半径与矩阵范数的关系两边取范数两边取范数()()()()kkkkkkA xAxxx=()()0,kkkxxA同除，有()maxkkAA=由 的任意性，有数值分析课件数值分析课件1()()kkAA=)3 3、一些关于谱半径的结论、一些关于谱半径的结论0 2）存在一种矩阵范数使得()AA+3）当矩阵A对称时2()AA=lim0()1kkAA=4）当矩阵A为方阵时有#数值分析课件数值分析课件数值分析课件数值分析课件同学们好！下面继续讲授线性方程组的迭代解法。第6集：数值分析课件数值分析课件迭代收敛定理数值分析课件数值分析课件1、迭代收敛定理()()()10()1kkxB xgxB+=+定理2 对任意都收敛证明：()()()1*lim,kkkkxxxB xgk+=+设，在迭代式令有*xB xg=+()()()()()()()()()()1120*2*kkkkkxxBxgBxgB xxBxxBxx=+=()()0*limlim0kkkkxxxxB=由及和 的任意性，有4()1B再由谱半径的结论，得出；必要性()()1kkxB xg=+()()()()()10*,kkkkxBxg xBxgxxBxx=+=+=数值分析课件数值分析课件()()1()1kkxB xgB+=+充分性()*()1BIBIB xgx=非奇异线性方程组有唯一解()*IB xgxB xg=+于是有()()()0*kkxxBxx=()1lim0kkBB=由()*limkkxx=()()1kkxBxg+=+再由()()()()()0*limlim0kkkkxxBxx=证毕。数值分析课件数值分析课件定理定理3 3 SorSor法收敛法收敛00 22证明Sor法的迭代矩阵为,1,2,kkn=设是的n个特征值B()()11BDLDU=+()()()()11111nBDLDUDD=+=()121nnB=()1B收敛()()121102nnnB=由证毕。数值分析课件数值分析课件2、迭代收敛判别条件()()1()1kkxB xgB+=+判别条件I若存在迭代矩阵B的某种矩阵范数满足B1,则产生的迭代序列都收敛到其不动点*x()()()01,kknxRxB xg+=+()1,BB证明要点：由定理得。注意：1.判别条件I是充分条件，不是充要条件！2.矩阵范数有一个小于1即可。数值分析课件数值分析课件判别条件II()0 x若A为严格对角占优矩阵，则线性方程组Ax=b的Jacobi和Seidel迭代对任何初值都收敛。严格行对角占优阵()n n:ijAa=1,nkkkjjj kaak=严格列对角占优阵()n n:ijAa=1,nkkikii kaak=615351?237严格行和严格列对角占优矩阵统称严格对角占优矩阵！定理：严格对角占优矩阵是非奇异的。数值分析课件数值分析课件判别条件III6106160,0,15001500761 0150007 是正定矩阵！若A为正定矩阵，则线性方程组Ax=b的Seidel迭代对任何初值都收敛。()0 x#0,1,2,kkn=正定矩阵：A的k阶主子式数值分析课件数值分析课件数值分析课件数值分析课件同学们好！下面继续讲授线性方程组的迭代解法。第7集：数值分析课件数值分析课件数值分析课件数值分析课件定理4.设矩阵B的某种矩阵范数,则有()()()1*1kkkBxxxxB1、()()()10*1kkBxxxxB2、比较非线性方程求根误差定理*1101,211kkkkkLLxxxxxxxxLL、()()()1*0.5kkkBxxxx1B 数值分析课件数值分析课件()()1*1kkBxBxgxBxg+=+=+收敛()()()()()()()()()111kkkkkkxxBxgBxgB xx+=+=证明：()()()()11kkkkxxB xx+()()()()()()()()()()()11*1kkkkkkkkkxxxxxxxxB xxxxB xxBxx+=+=+=()()()()()()11*1kkkkkBxxxxB xx+()()()1*101kkkBBxxxxB1得证。()()()()1*kkkxxBxgBxgB xx+=+=数值分析课件数值分析课件()()()()()()()211210*111kkkkkkBBBxxxxxxxxBBB()()()()()()21112kkkkkkxxB xxBxx+()()()10*1kkBxxxxB2得证。证明方法：类似非线性方程求根定理的证明，将那里的绝对值换成范数、函数换成矩阵，数列换为向量并注意范数使用。#北京交通大学北京交通大学 数值分析课件数值分析课件北京交通大学北京交通大学 数值分析课件数值分析课件同学们好！下面继续讲授线性方程组的迭代解法。第8集：北京交通大学北京交通大学 数值分析课件数值分析课件北京交通大学北京交通大学 数值分析课件数值分析课件12312312352312422023103xxxxxxxxx+=+=+=例例3 3、用Jacobi 迭代法解线性方程组解：0.9810711JFB=Jacobi迭代收敛！Jacobi 迭代格式为(1)()()123(1)()()213(1)()()3122.40.40.650.250.50.30.20.3kkkkkkkkkxxxxxxxxx+=+=+00.40.60.2500.50.20.30JB=北京交通大学北京交通大学 数值分析课件数值分析课件()()00,0,0Tx=取计算()()()()11042.4,5,0.3,510,Txxx=()()()()()()()()2214181817444.58,4.25,2.28,2.06104.,2.99997,2.,0.411010TTxxxxxx=故所求近似解为1234,2.9997,2xxx=1234,3,2xxx=准确解：北京交通大学北京交通大学 数值分析课件数值分析课件例例4 4、已知方程组、已知方程组1、写出Jacobi和Seidel迭代格式；122111122213xyz =2、判别两种迭代格式的收敛性。解：1、Jacobi 迭代格式为(1)()()(1)()()(1)()()2212223kkkkkkkkkxyzyxzzxy+=+=+=+Seidel 迭代格式为(1)()()(1)(1)()(1)(1)(1)2212223kkkkkkkkkxyzyxzzxy+=+=+=+北京交通大学北京交通大学 数值分析课件数值分析课件1112111212222212nnnnnnnnaaaxbaaaxbaaaxb=对方程组11121212221200nnSnnnnaaaaaaIBaaa=11121212221200nnJnnnnaaaaaaIBaaa=可以证明：北京交通大学北京交通大学 数值分析课件数值分析课件32211022=得特征值1230=()22212022=得特征值1230,2=()01,JBJacobi=迭代收敛；()21SB=解:2、Jacobi迭代特征方程Seidel迭代特征方程Seidel迭代发散！#北京交通大学北京交通大学 数值分析课件数值分析课件北京交通大学北京交通大学 数值分析课件数值分析课件同学们好！下面讲授线性方程组的直接解法。该内容分6集讲授：第1集：北京交通大学北京交通大学 数值分析课件数值分析课件3.4 3.4 线性方程组的直接解法线性方程组的直接解法线性方程组的直接解法有哪些？它的计算公式怎么得出的？北京交通大学北京交通大学 数值分析课件数值分析课件直接方法描述直接方法描述解线性方程组的直接法有Gauss消元法，LU分解法及一些特殊线性方程组的解法等，其中Gauss消元法是直接法的基础。直接法的重点是直接法的重点是一般公式推导一般公式推导，要注意，要注意学习和体会。学习和体会。北京交通大学北京交通大学 数值分析课件数值分析课件1、Gauss消元法2、Gauss消元法分析3、主元消元法4、LU分解法5、追赶法6、特殊线性方程组解法北京交通大学北京交通大学 数值分析课件数值分析课件北京交通大学北京交通大学 数值分析课件数值分析课件11 11221122222nnnnnnnna xa xa xba xa xba xb+=+=(1)(1)121/,nnnnnnnnxbaxxx=先解出，逆序解出；11 11221121 1222221 122nnnnnnnnnna xa xa xba xa xa xba xa xa xb+=+=+=11 11221121 1222221 122nnnnnnnnnna xa xa xba xa xa xba xa xa xb+=+=+=回代求解三角方程组可以通过回代求解：一般方程组可用消元的方式化为三角方程组来求解：北京交通大学北京交通大学 数值分析课件数值分析课件基本思想先将线性方程组通过消元方法化为同解的上三角方程组，然后从该三角方程组中按第n个方程、第n-1个方程、第1个方程的顺序，逐步回代求出线性方程组的解。Gauss消元法分为消元和回代两个过程。消元:把原方程组化为上三角方程组；回代:求上三角方程组的解。北京交通大学北京交通大学 数值分析课件数值分析课件记原方程组为()()()()()()()()()()()()()000011112211000021122222000011221nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb+=+=+=()0110a设（1）消元：()()00121211121/,+2xmaam=为消去第2个方程的，取乘数做第1个方程 第 个方程第2个方程变为()()()11122222nna xa xb+=()()()()()()()()002121111002221 11002221 1/2,3,jjjmaabbm baam ajn=+=+=北京交通大学北京交通大学 数值分析课件数值分析课件()()00131311131/,+3xmaam=为消去第3个方程的，取乘数做第1个方程 第 个方程类似地，第3个方程变为()()()11132233nna xa xb+=()()()()()()()()003131111003331 11003331 1/2,3,jjjmaabbm baam ajn=+=+=一般的有()()00111111,/+iiiixmaamiin=为消去第 个方程的令乘数，做第1个方程 第 个方程=2,3,第i个方程变为()()()11122iinnia xa xb+=()()()()()()()()0011111001 11001 1/,2,3,iiiiiijijijmaabbm baam ai jn=+=+=()()()()()()()()002121111002221 11002221 1/2,3,jjjmaabbm baam ajn=+=+=北京交通大学北京交通大学 数值分析课件数值分析课件经过如上n-1次消元，方程组（1）变为()()()()()()()()()()()00001111221111122222111222nnnnnnnnnaxaxaxba xa xba xa xb+=+=+=()()111,iiijm ba计算公式：()()()()()()()()0011111001 110011/,2,3,iiiiiijijijmaabbm baam ai jn=+=+=n-1阶线性方程组!北京交通大学北京交通大学 数值分析课件数值分析课件对方程组(2)后n-1个方程做同样处理()()()111222212220,/+iiianxmaamiin=设，为消去3,4,个方程的令乘数，做第2个方程 第 个方程=3,4,方程组(2)变为()()()()()()()()()()()()()()()()000001111221331111112222332222233333222333nnnnnnnnnnna xa xa xa xba xa xa xba xa xba xa xb+=+=+=+=()()()()()()()()1122222112221122/,3,4,iiiiiijijijmaabbm baam ai jn=+=+=第二步消元n-2阶线性方程组!()()()()()()()()0011111001 11001 1/,2,3,iiiiiijijijmaabbm baam ai jn=+=+=北京交通大学北京交通大学 数值分析课件数值分析课件()()()()()()()()0011111001 11001 1/,2,3,iiiiiijijijmaabbm baam ai jn=+=+=()()()()()()()()1122222112221122/,3,4,iiiiiijijijmaabbm baam ai jn=+=+=()()()()()()()()111111/,1,2,kkikikkkkkkiiikkkkkijijikkjmaabbm baam ai jkkn=+=+=+系数计算公式顺序做了n-1次消元后，方程组(1)变为如下上三角方程组：()()()()()()()()()()00001111221111122222114nnnnnnnnnnaxaxaxba xa xbaxb+=+=再回代求解。北京交通大学北京交通大学 数值分析课件数值分析课件（2)Gauss消元公式1,2,1kn=1)计算()()()()()()()()()1111111/0,1,2,kkkikikkkkkkkkiiikkkkkijijikkjmaaabbm baam ai jkkn=+=+=+,1,1,kn n=2)计算(1)(1)(1)1()/nkkkkkkjjkkj kxbaxa=+=#北京交通大学北京交通大学 数值分析课件数值分析课件北京交通大学北京交通大学 数值分析课件数值分析课件同学们好！下面继续讲授线性方程组的直接解法。第2集：北京交通大学北京交通大学 数值分析课件数值分析课件北京交通大学北京交通大学 数值分析课件数值分析课件121(1)(2)(1)1 2121nnnnnnn消元步乘法次数除法次数1 1、GaussGauss消元法的计算量消元法的计算量112111(1)(1)(1)32nnkknNk kknn n=+=+消1(1)2Nn n=+回计算量计算量332333nnnNn=+()()()()()()()()()()0000111122111112222211122nnnnnnnnnaxaxaxba xa xba xa xb+=+=+=()()()()()()()()0010010011111 11 1/,iiiiiijijijmaabbm baam a=+=+北京交通大学北京交通大学 数值分析课件数值分析课件Gauss消元法消元过程是对（A,b）做第三种初等行变换,每次对一个方程做一次消元时，对应的初等矩阵为1111ikikMm=2 2、GaussGauss消元法矩阵解释消元法矩阵解释北京交通大学北京交通大学 数值分析课件数值分析课件第1步消元(1)(1)(1)(1)1112111112111(,)(,);,nnnnM MMA bAbMM MMM AAM bb=第n-1步消元后，有(1)121121(1)1(1),nnnnnnnMMM AAMMMMMAAAMALUALU=记111*1*1*11*1*1MML=L是下三角阵，U是上三角阵。北京交通大学北京交通大学 数值分析课件数值分析课件3、Gauss消元法可使用的条件()()()()()()()()()1111111/0,1,2,kkkikikkkkkkkkiiikkkkkijijikkjmaaabbm baam ai jkkn=+=+=+(1)(1)(1)1()/nkkkkkkjjkkj kxbaxa=+=定理2：矩阵A的所有顺序主子式0，则Gauss消元法可以使用。(1)0,kkkak 定理1：矩阵A的所有顺序主子式0。北京交通大学北京交通大学 数值分析课件数值分析课件4、Gauss消元法的缺点(1)10(1,2,)kkkakn=缺点：要求缺点2：在使用Gauss消元法进行计算机求解时，人们发现有时求出的解是错误的。例5、研究线性方程组12120.000112xxxx+=+=的Gauss消元法求解结果，假设计算在4位浮点十进制数的计算机上求解。北京交通大学北京交通大学 数值分析课件数值分析课件解：311121211112120.000110.1000 100.1000 100.1000 1020.1000 100.1000 100.2000 10 xxxxxxxx+=+=+=+=用Gauss消元法得31112215520.1000 100.1000 100.1000 101,00.1000 100.1000 10 xxxxx+=#北京交通大学北京交通大学 数值分析课件数值分析课件北京交通大学北京交通大学 数值分析课件数值分析课件同学们好！下面继续讲授线性方程组的直接解法。第3集：北京交通大学北京交通大学 数值分析课件数值分析课件北京交通大学北京交通大学 数值分析课件数值分析课件121212120.00011220.00011xxxxxxxx+=+=+=+=用Gauss消元法求解得121,1xx=其准确解为12100009998,99999999xx=可以接受。例5调换方程的顺序主元:消元法中用作分母的数;主方程:主元所在的方程。列主元消元法、全主元消元法北京交通大学北京交通大学 数值分析课件数值分析课件例6、用列主元与全主元方法解方程组1231231232315410030.12xxxxxxxxx+=+=+=解：12315410054100123130.1 1230.1 121）列主元法10.82010.8200 1.21102.5520520 1.2112.510.82010.82010.8200 120.80 120.80 120.80 1.2 11001.449/250011.41231.2,2,1.4xxx=得到解：北京交通大学北京交通大学 数值分析课件数值分析课件解：12312315410 030.112xxxb2）全主元法32110450321110.132xxxb3211045000.80.5 100.52.52xxxb312312105401054002.50.5202.50.5200.50.81000.71.4xxxbxxxb回代得到解1231.2,2,1.4xxx=北京交通大学北京交通大学 数值分析课件数值分析课件Gauss消元法，列主元法，全主元法比较Ga