第二章解线性方程组的直接方法初次修改稿

1高斯消去法主元素法直接三角分解法平方根法与改进平方根法误差分析第二章线性方程组的直接方法2.....................................,...,...22112222212111212111nnnnnnnnnnbxaxaxabxaxaxabxaxaxa讨论n元线性方程组的直接解法.3其中,.........212222111211nnnnnnaaaaaaaaaA,21nxxxx.21nbbbb方程组的矩阵形式为,bAx若矩阵A非奇异,即det(A)≠0,则方程组有唯一解.4直接解法是指,若不考虑计算过程中的舍入误差，经过有限次算术运算就能求出线性方程组的精确解的方法.但由于实际计算中舍入误差的存在,用直接解法一般也只能求出方程组的近似解.Cramer法则是一种不实用的直接法，下面介绍几种实用的直接法.解线性方程组的方法:直接方法和迭代法.迭代法是从解的某个近似值出发,通过构造一个无穷序列去逼近精确解的方法.一般地,有限步内得不到精确解.5Gauss消元法是一种规则化的消元法，其基本思想是通过逐次消元计算，把一般线性方程组的求解转化为等价的上三角形方程组的求解。§1Gauss消去法6322413312321321321xxxxxxxxx消去后两个方程中的x1得166225123232321xxxxxxx再消去最后一个方程的x2得613121321xxx消元结束.5754222512332321xxxxxx经过回代得解:例考虑线性方程组顺序Gauss消去法7消元过程:先逐次消去变量x1,x2,将方程组化为同解的上三角形方程组.上过方法可推广到一般情况回代过程:按方程相反的顺序求解上三角形方程组.8)1()1()1(3)1(2)1(1)1(3)1(3)1(33)1(32)1(31)1(2)1(2)1(23)1(22)1(21)1(1)1(1)1(13)1(12)1(11)1()1(............),(nnnnnnnnnbaaaabaaaabaaaabaaaabA第一步.设依次用,0)1(11a),...,3,2(,)1(11)1(11niaalii乘矩阵的第1行加到第i行上,得到矩阵:iiijijbbaabb,AA)1()1((1)(1),,则线性方程组的增广矩阵为记9)2()2()2(3)2(2)2(3)2(3)2(33)2(32)2(2)2(2)2(23)2(22)1(1)1(1)1(13)1(12)1(11)2()2(...0...0...0...),(nnnnnnnnbaaabaaabaaabaaaabA其中njialaajiijij,...,3,2,,)1(11)1()2(niblbbiii,...,3,2,)1(11)1()2(第二步.设依次用0)2(22a),...,4,3(,)2(22)2(22niaalii乘矩阵的第2行加到第i行,得到矩阵:10)3()3()3(3)3(3)3(3)3(33)2(2)2(2)2(23)2(22)1(1)1(1)1(13)1(12)1(11...00...00...0...)(nnnnnnn(3)(3)baabaabaaabaaaab,A其中njialaajiijij,...,4,3,,)2(22)2()3(niblbbiii,...,4,3,)2(22)2()3(11)()()3(3)3(3)3(33)2(2)2(2)2(23)2(22)1(1)1(1)1(13)1(12)1(11)()(.........)(nnnnnnnnnnbabaabaaabaaaab,A这就完成了消元过程.如此继续消元下去,第n1步结束后得到矩阵:12...............,...,...)()()2(2)2(22)2(22)1(1)1(12)1(121)1(11nnnnnnnnnnbxabxaxabxaxaxa对此方程组进行回代，就可求出方程组的解.对应的方程组变成：.1,,2,1,)(,)(1)()()()(nniaxabxabxiiinijjiijiiinnnnnn13能用顺序Gauss消去法求解的条件是在消元过程中得到的主元必须全不为0，即),,2,1(,0)(nkakkk顺序Gauss消去法通常也简称为Gauss消去法.主元素都不为零矩阵A的各阶顺序主子式都不为零.顺序Gauss消去法中的称为主元素.),...,2,1()(nkakkk)()2(22)1(11)det(kkkkaaaA14顺序Gauss消去法求解n元线性方程组的乘除运算量第1次消元乘除运算量:消元过程乘除运算量求li1:(n－1)求aij(2):(n－1)2求bi(2):(n－1)共(n2－1)次111)1(1222nn15回代过程乘除运算量：求xn:1求xn－1:2求x1:n….n2116nknkkk112)1()3(3123nnnn=30时,顺序Gauss消去法只需9890次乘除法运算.nnn21111)1(1222顺序Gauss消去法求解n元线性方程组的乘除运算量17高斯消去法优缺点：简单易行要求主元均不为零,因而适用范围小数值稳定性差18例：单精度解方程组211021219xxxx精确解...,1000...00.1101191x8个...8999...99.0212xx8个用顺序Gauss消去法计算：911212110/aal99921)2(2210101010...0.011la8个921)2(21012lb9991010011100,112xx小主元可能导致计算失败.§2主元素法19若将方程组改写成:110221921xxxx用顺序Gauss消去法,消元得12221xxx回代得解:x2=1,x1=1与准确解非常接近.可见,第一种算法是不稳定的,第二种算法是稳定的.20此例说明,在消元过程中,应避免选取绝对值较小的数作主元.如例中的第二种解法,通过交换方程次序,选取绝对值较大的元素作为主元.基于这种想法导出了主元法.为了提高计算的数值稳定性,在消元过程中采用选择主元的方法.常采用的是列主元消去法和全主元消去法.21给定线性方程组Ax=b,记A(1)=A,b(1)=b,列主元Gauss消去法的具体过程如下:.1max)1(11)1(1行互换行与第为主元素，第kaainik首先在增广矩阵B(1)=(A(1),b(1))的第一列元素中,取然后进行第一步消元得增广矩阵B(2)=(A(2),b(2)).列主元消去法22.2max)2(22)2(2行互换行与第为主元素，第kaainik然后进行第二步消元得增广矩阵B(3)=(A(3),b(3)).按此方法继续进行下去,经过n1步选主元和消元运算,得到增广矩阵B(n)=(A(n),b(n)).则方程组A(n)x=b(n)是与原方程组等价的上三角形方程组,可进行回代求解.只要|A|0,列主元Gauss消去法就可顺利进行.再在矩阵B(2)=(A(2),b(2))的第二列元素中,取23全主元素法每一步选绝对值最大的元素为主元素，保证.1||iklStepk:①选取;0||max||)(,)(kijnjikkjiaakk②Ifikkthen交换第k行与第ik行;Ifjkkthen交换第k列与第jk列;③消元注：列交换改变了xi的顺序，须记录交换次序，解完后再换回来。24例用主元素法求解线性方程组计算过程保留三位小数,方程的精确解为x1*=1,x2*=2,x3*=3.1515613183312111321xxx251513181533126111解1.按列主元素法，求解过程如下6111153312151318167.5944.0167.105333.2101513185333.210167.5944.0167.10151318428.9142.300167.5944.0167.10151318.000.1,000.2,001.3123xxx消元回代得261513181533126111解2.按全主元素法，求解过程如下6111153312151318167.5944.0167.105333.210151318167.5167.1944.0051333.20153118144.3572.10051333.20151318.000.1,000.3,000.2132xxx回代得3x2x27全主元素法的精度优于列主元素法,这是由于全主元素是在全体系数中选主元,故它对控制舍入误差十分有效.但全主元素法在计算过程中,需同时作行与列的互换,因而程序比较复杂,计算时间较长.列主元素法的精度虽然稍低于全主元素法,但其计算简单,工作量大为减少,且计算经验与理论实践均表明,它与全主元素法同样具有良好的数值稳定性.列主元素法是求解中小型稠密线性方程组的最好方法之一.例3的计算结果表明28Gauss消元法的矩阵表示3332312322211312111001001aaaaaaaaaba133312321131132312221121131211baabaabaaaaaaaaaaaaaa333231232221131211aaaaaaaaa12arr13brr133312321131132312221121131211baabaabaaaaaaaaaaaaaa§3直接三角分解法两者等价29333231232221131211aaaaaaaaaA,112121aal113131aal)2()2(33)2(32)2(23)2(22131211:00Aaaaaaaajiijijalaa11)2(2,2ji其中)2(1AAL,100100131211llL两者等价n=3时Gauss消元法的矩阵表示30)2(33)2(32)2(23)2(22131211)2(00aaaaaaaA)2(22)2(3232aal)3()3(33)2(23)2(22131211:000Aaaaaaa)2(2332)2(33)3(33alaa其中)3()2(2AAL,10010001322lL两者等价31ALLALA12)2(2)3()3(1211ALLA1