Cht4线性方程组的直接解法

第2章线性方程组的解法——直接法与迭代法在自然科学与社会科学的研究中，常常需要求解线性代数方程组，这些方程组的系数矩阵大致分为两种：一种是低阶稠密矩阵（例如：阶数大约为小于等于150），另一种是大型稀疏矩阵（即矩阵阶数高且零元素较多）。在计算机上求解线性代数方程组Ax=b的常用的数值解法：1、直接法：就是经过有限次算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差）。但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解。这类方法是解低阶稠密矩阵及大型带状方程组的有效方法。2、迭代法：就是用某种极限过程去逐步逼近线性方程组精确解的方法，迭代法具有需要计算机的存贮单元较少，程序设计简单，原始系数矩阵在计算机中始终不变等优点，但存在收敛性和收敛速度等问题。迭代法是解大型稀疏矩阵方程组的重要方法。注:直接法求解n元线性代数方程组所需乘法次数1、Cramer（克莱姆）法则：(n+1)！，当n=10时，(n+1)!=39916800次2、Gauss消去法：当n=10时，约为430次3/)3(23nnn§2.1Gauss消去法§2.2直接三角分解法§2.3矩阵的条件数与病态方程组求解线性方程组的直接方法§2.4迭代法求解线性方程组的迭代方法n元线性方程组11112211211222221122nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb(2.1)方程组的矩阵形式(2.2)1111121212222212nnnnnnnnxbaaaaaaxbaaaxb简记为.Axb设A非奇异，则方程组有唯一解。§2.1Gauss消去法高斯消去法步骤：(1)首先将增广阵[A,b]化为上三角阵；(2)用三角方程组，回代求解。Gauss消去法是一个古老的求解线性代数方程组的方法（早在公元前250年我国就掌握了解三元一次联立方程组的方法）。但由于它改进、变形得到的主元素消去法，三角分解法仍然是目前计算机上常用的有效方法。例1用消去法解方程组12323123645221xxxxxxxx(1)(2)(3)解(1)化上三角方程组12323123645221xxxxxxxx①②③1232323645411xxxxxxx①②④③+(-2)×①④+②12323364526xxxxxx①②⑤12323364526xxxxxx①②⑤(2)回代过程.得到下同解方程组后,如下处理3(6)/(2)3x从下向上逐步求解把x3的值代入②求x2用x3,x2的值求x1235/42xx1236()1xxx对应的增广矩阵的变化1116(|)04152211Ab1116041504111111604150026(-2)×r1+r3→r3r2+r3→r3高斯消去法的基本思想将原方程组逐次消去未知元，变为与之同解的上三角方程组，再回代求解。用矩阵语言叙述，上述过程是使用初等行变换把增广阵约化为上三角阵，使用上三角方程组，回代求解。高斯消去法的一般性叙述11121121222212nnnnnnnaaabaaabaaab用行变换根据下面的上三角方程组,逐次回代求解xk(1)(1)(1)(1)11111221(2)(2)(2)22122(1)(1)(1)1,11,1()()nnnnnnnnnnnnnnnnnnnnbaxaxaxbaxaxaxaxbaxb(2.5)11nnxxx)()()2(2)2(2)2(22)1(1)1(1)1(12)1(11000nnnnnnnbabaabaaa22n-1,n-12.1.1顺序Gauss消去法在使用高斯消去法的过程中，仅对方程组做倍加变换，就形成了顺序高斯消去法。1.消元过程对于k=1,2,…,n-1执行(1)如果,则算法失效,停止计算;否则转(2)(2)对于i=k+1,k+2,…,n计算()0kkka(1)(1)(,1,2,...,);(1,2,...,).ijijiiaaijnbbin算法如下：记()()(1)()()(1)()()/(1,2,...,)kkikikkkkkkijijikkjkkkiiikkmaaaamajkknbbmb2.回代过程()()()()()1//(1,2,...,1)nnnnnnnkkkkkkjjkkjkxbaxbaxaknn顺序高斯消去法求解n元线性方程组的乘除运算总次数为：32(3)/3nnn顺序高斯消去法计算过程中出现的称为主元素.出现，消元过程就进行不下去了。()kkka()0kkka即使detA≠0，也可能对某个kn，出现.下面的定理给出了避免出现这种情况的条件。()0kkka定理2.1顺序高斯消去法的前n-1个主元素均不为零的充要条件是方程组(2.1)的系数矩阵A的前n-1个顺序主子式()kkka(1)(1)(1)11121(1)(1)(1)21222(1)(1)(1)120(1,2,...,1).kkkkkkkaaaaaaDknaaa证第k个顺序主子式Dk等于k前个主元之积!(1)(2)()1122.kkkkDaaa注解：即使，方程组(2.1)的系数矩阵A的n个顺序主子式Dk均不为零，保证了主元素均不为零，使顺序消去法得以进行。但是，当遇到某个主元素的绝对值很小时，将使行乘数-mik的绝对值很大，则舍入误差的积累会很大，计算出的近似解会有很大的误差。顺序高斯消去法的数值稳定性是没有保证的!顺序主元素消去法可能计算失败之例例：单精度解方程组211021219xxxx/*精确解为和*/...1000...00.1101191x8个...8999...99.0212xx8个用GaussianElimination计算：911212110/aam999212210101010...0.011ma8个92121012mb9991010011100,112xx小主元/*Smallpivotelement*/可能导致计算失败。运算量解释(AmountofComputation)由于计算机中乘除运算的时间远远超过加减运算的时间，故估计某种算法的运算量时，往往只估计乘除的次数，而且通常以乘除次数的最高次幂为运算量的数量级。GaussianElimination:Stepk：设，计算因子且计算0)(kkka)...,,1(/)()(nkiaamkkkkikik)...,,1,()()()1()()()1(nkjibmbbamaakkikkikikkjikkijkij共进行n1步)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11..................nnnnnnnnbbbxxxaaaaaa)()(/nnnnnnabx)1...,,1()(1)()(niaxabxiiinijjiijiii(nk)次(nk)2次(nk)次(nk)(nk+2)次nnnknknnk6523)2)((2311消元乘除次数：1次(ni+1)次22)1(1211nninni回代乘除次数：GaussianElimination的总乘除次数为，运算量为级。nnn3132333n2.1.2列主元素Gauss消去法定义使用高斯消去法的过程中，在第k次消元前，先对第k个增广阵[A(k),b(k)]做交换二行的变换，把中绝对值最大的元素换到(k,k)位置，再消元。此方法叫列主元素高斯消去法。其算法如下：记(1)(1)(,1,2,...,);(1,2,...,).ijijiiaaijnbbin1.消元过程对于k=1,2,…,n-1执行(1)选行号ik，使(2)交换第k行与第ik行（中数值）。()()max.kkkikikkinaa()(,1,...,)kikaikkn(3)对于i=k+1,k+2,…,n计算()()(1)()()(1)()()/(1,2,...,)kkikikkkkkkijijikkjkkkiiikkmaaaamajkknbbmb2.回代过程()()()()()1//(1,2,...,1)nnnnnnnkkkkkkjjkkjkxbaxbaxaknn注解：此算法中的称为第k个列主元素，它的值总要被换到位置(k,k)。()(1,2,...,1)kkikakn定理2.2设方程组(2.1)的系数矩阵A非奇异，则用列主元素消去法求解方程组时,各个列主元素均不为零。()kkika证设有一个列主元素为零，当消元进行到第r次时，由行列式性质，容易知道，系数矩阵A的行列式有下面的形状:()rrira与A是非奇异矩阵矛盾。该子式的第1列全为0评论：列主元素消去法，所需条件较少，仅仅要求方程组的系数矩阵A非奇异。而且，对一般的方程组，它还具有良好的数值稳定性，其计算量与顺序消去法的计算量相当。例1在四位十进制的限制下，分别用顺序消去法与列主元素消去法求解下列方程组1231231230.0120.0100.1670.67810.83345.91012.1320012004.2981xxxxxxxxx解用顺序消去法的消元过程：0.01200.0100.16700.67811.0000.83345.91012.10320012004.200981.0320.01200.0100.16700.678100.1000108.01044.41014674454101798103550.01200.0100.16700.678100.1000108.01044.41001175106547103215.546,100.0,104.0xxx回代后，得主元素主元素完全失真!!1231231230.0120.0100.1670.67810.83345.91012.1320012004.2981xxxxxxxxx原方程组：3215.546,100.0,104.0xxx近似解：把上近似解代入第3个方程后，得3200×(-104)+1200×100+4.2×5.546=-2.1278e+005检验2320012004.200981.000.45845.90911.7900.5500100.16700.67440.01200.0100.16700.67811.0000.83345.91012.10320012004.200981.0列主元素法的消元过程：3215.546,45.76,17.46xxx回代后，得列主元素列主元素320012004.200981.000.45845.90911.79000.096090.5329√由此看出，列主元法的精度明显高于顺序消去法!!1231231230.0120.0100.1670.67810.83345.91012.1320012004.2981xxxxxxxxx原方程组：32