线性方程组的数值解法

第2章线性方程组的数值解法天津大学理学院数学系刘东毅2020/2/17线性方程组的数值解法2第2章线性方程组的数值解法主要目的：掌握线性方程组的数值解法nnnnnnnnnnbxaxaxabxaxaxabxaxaxa221122222121112121112020/2/17线性方程组的数值解法3主要内容：直接法Gauss消去法直接三角分解法：追赶法，平方根法等方程组的性态与误差分析迭代法Jacobi，Gauss-Seidel，SOR迭代法迭代法的收敛性分析2020/2/17线性方程组的数值解法42.1Gauss消去法Gauss消去法是计算机上常用的解线性方程组的有效方法。此方法分为消元过程-把原方程组化为上三角形方程组的过程。回代过程-求解上三角形方程组的过程。其他的衍生方法Gauss-Jordan消去法Gauss主元素法•列主元素法•全主元素法2020/2/17线性方程组的数值解法52.1.1Gauss消去法设有线性方程组Ax=b,(2.1.1)其中A=(ai,j)n×n非奇异，x=(x1,x2,…,xn)T,b=(b1,b2,…,bn)T为方便起见，将(2.1.1)记为A(1)x=b(1),(1)(1)(1)(1)1111211(1)(1)(1)(1)2212222(1)(1)(1)(1)12nnnnnnnnxaaabxaaabxaaab(2.1.2)即2020/2/17线性方程组的数值解法6设记乘数以-li1乘(2.1.2)的第一个方程,加到第i(i=2,3,…,n)个方程上去,(1)110,a(1)(1)1111/,2,3,,.iilaain(1)(1)(1)(1)1121111(2)(2)(2)22222(2)(2)(2)2nnnnnnnxaabaxaabxaab(2.1.3)其中：),,3,2(),,3,2,()1(11)1()2()1(11)1()2(niblbbnjialaaiiijijiji第一次消元：(1)(1)(1)(1)1111211(1)(1)(1)(1)2212222(1)(1)(1)(1)12nnnnnnnnxaaabxaaabxaaab(2.1.2)得A(2)x=b(2),即2020/2/17线性方程组的数值解法7设记乘数以-li2乘(2.1.3)的第二个方程,然后加到第i个(i=3,4,…,n)方程上去,(2)220,a(2)(2)2222/,3,4,,.iilaain(1)(1)(1)(1)(1)111121311(2)(2)(2)(2)2222322(3)(3)(3)33333(3)(3)()3nnnnnnnnnxaaaabxaaabxaabxaab其中：),,4,3(),,4,3,()2(22)2()3()2(22)2()3(niblbbnjialaaiiijijiji第二次消元：(1)(1)(1)(1)1121111(2)(2)(2)22222(2)(2)(2)2nnnnnnnxaabaxaabxaab(2.1.3)得A(3)x=b(3),即2020/2/17线性方程组的数值解法8设第k-1次消元后的等价方程组A(k)x=b(k))5.1.2()()(1)()2(2)1(1121)(,)(1,)(,)(,1)(1,1)(,1)(,)(1,)()2(2)2(12)2(2)2(22)1(1)1(11)1(1)1(21)1(11knkkkknkkknnkknkknknkkkkkkkknkkkkkkknkknkkbbbbbxxxxxaaaaaaaaaaaaaaaaaaGoto列主元素法2020/2/17线性方程组的数值解法9第k次消元：设记乘数以-lik乘(2.1.5)的第k个方程,然后加到第i(i=k+1,…,n)个方程上,()0,kkka()()/,1,2,,.kkikikkklaaikkn得到与(2.1.1)等价方程组)()(1)()2(2)1(1121)(,)(1,)(,)(,1)(1,1)(,1)(,)(1,)()2(2)2(12)2(2)2(22)1(1)1(11)1(1)1(21)1(11knkkkknkkknnkknkknknkkkkkkkknkkkkkkknkknkkbbbbbxxxxxaaaaaaaaaaaaaaaaaaA(k+1)x=b(k+1),即2020/2/17线性方程组的数值解法10第k次消元后的等价方程组A(k+1)x=b(k+1)(1)(1)(1)(1)(1)(1)1111211,111(2)(2)(2)(2)22222,122()()(),1(1)(1)1,11,(1)(1),1kknkknkkkkkkkknkkkkknkknnknnxaaaaabxaaaabaaaaaxaa(2)()(1)1(1)kkkkknbbb其中A(k+1)与b(k+1)中的元素的计算公式为：(1)()()(1)()()(1)()()kkkijijikkjkkkiiikkkkkaalabblbAAbk(k+1)与的前k行元素相同b与的前行元素相同2020/2/17线性方程组的数值解法11第n-1次消元得到的等价上三角形方程组A(n)x=b(n)(1)(1)(1)(1)1111112(2)(2)(2)22222()()(2.1.7)nnnnnnnnxabaaxabaxab分别求得xn,xn-1,…,x2,x1,其计算公式如下：()()()()()1/,()/(1,2,,1).nnnnnnniiiiiikkiikixbaxbaxainn回代过程消元与回代过程合起来称为Gauss消去法的全过程,它大概需要n3/3次乘除法.2020/2/17线性方程组的数值解法12例1.用Guass消去法解线性方程组：解：为了书写方便，写出此方程组的增广矩阵，并用矩阵变换来描述消元过程。1231231233,230,25.xxxxxxxxx512103123111A2020/2/17线性方程组的数值解法13消元过程如下：512103123111Al21=2l31=-1201065303111l32=1/303/50065303111写成与原方程组等价的线性方程组为2020/2/17线性方程组的数值解法14等价的线性方程组为.035,653,3332321xxxxxx回代求得原方程组的解为.)0,2,1(Tx2020/2/17线性方程组的数值解法15若n阶矩阵A=A(1)的第一阶至第k阶顺序主子式均不为零，即定理2.1.1(1)(1)111(1)(1)(1)11121112(1)(1)(1)(1)212210,0,,0,kkkkkaaaaaaaaa则()0(1,2,,;1),iiiaikkn反之亦真。()0(1,2,,)iiiain否则将溢出停机.那么系数矩阵A满足什么条件才会使这些元素全不为零呢？通过前面的讨论可知，Gauss消去法要求主元素此定理利用归纳法很容易证明。P172020/2/17线性方程组的数值解法161231231233,230,25.xxxxxxxxx由于Guass-Jordan消去法在线性代数中已经讨论过，并且与前面讨论的Guass消去法相类似，故这里只用一个示例来简述一下。2.1.2Guass-Jordan消去法用Guass-Jordan法解方程组：2020/2/17线性方程组的数值解法171231231233,230,25.xxxxxxxxx111321301215A100101020010l13=2/3l23=-5/3111303560102l21=2l31=-1102/31015/32005/30l12=1l32=-11113015/320102102/31015/320010用Guass-Jordan法解方程组：得方程组的解为(1,2,0)T2020/2/17线性方程组的数值解法18Gauss消去法的缺点：(1)则消元不能进行。(2)若但与比较,其绝对值甚小（小主元）,此时消元乘数lik的绝对值很大，势必造成误差的严重扩散，使得计算结果失真。()0,kkka()0,kkka()(1,,)kikaikn在此我们举一个例子：()()/,1,2,,.kkikikkklaaikkn(1)()()(1)()()(1)()()kkkijijikkjkkkiiikkkkkaalabblbAAbk(k+1)与的前k行元素相同b与的前行元素相同2020/2/17线性方程组的数值解法19例2.1.3.用Guass消去法解下列方程组（采用三位十进制浮点运算）解：记增广矩阵为，采用三位十进制浮点运算，消元过程用矩阵变换表示如下：1230.501.13.16.02.04.50.360.0205.00.966.50.96xxx该方程组的精确解为：*T(2.60,1.00,2.00)x2020/2/17线性方程组的数值解法20回代后求得0.501.13.16.02.04.50.360.0205.00.966.50.96A2,13,1(1)4.0010.00.501.13.16.000.10012.024.0010.024.559.6ll3,2(2)1000.501.13.16.000.10012.024.00012202460lT(5.80,2.40,2.02).x与精确解相差较大，原因在于两次消元过程中均使用了小主元的结果。精确解*T(2.60,1.00,2.00)x下面详细分析第二次消元2020/2/17线性方程组的数值解法21详细分析第二次消元如果精确计算，消元后方程组变成6.595.241024121.03232xxxx)24006.59()12005.24(24121.0332xxx最后一个方程x3的系数为-1224.5，常数项为-2459.但由于计算精度的限制，