线性方程组的解-直接法和迭代法-数值分析课件

在自然科学与社会科学的研究中，常常需要求解线性代数方程组，这些方程组的系数矩阵大致分为两种：一种是低阶稠密矩阵（例如：阶数大约为小于等于150），另一种是大型稀疏矩阵（即矩阵阶数高且零元素较多）。在计算机上求解线性代数方程组Ax=b的常用的数值解法：•1、直接法：就是经过有限次算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差）。但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解。这类方法是解低阶稠密矩阵及大型带状方程组的有效方法。第2章线性方程组的解法•——直接法与迭代法•2、迭代法：就是用某种极限过程去逐步逼近线性方程组精确解的方法，迭代法具有需要计算机的存贮单元较少，程序设计简单，原始系数矩阵在计算机中始终不变等优点，但存在收敛性和收敛速度等问题。迭代法是解大型稀疏矩阵方程组的重要方法。注:直接法求解n元线性代数方程组所需乘法次数1、Cramer（克莱姆）法则：(n+1)！，当n=10时，(n+1)!=39916800次2、Gauss消去法：当n=10时，约为430次3/)3(23nnnn元线性方程组11112211211222221122nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb(2.1)矩阵形式(2.2)1111121212222212nnnnnnnnxbaaaaaaxbaaaxb简记为.Axb设A非奇异，则方程组有唯一解。§2.1Gauss消去法§2.2直接三角分解法§2.3矩阵的条件数与病态方程组求解线性方程组的直接方法§2.4迭代法求解线性方程组的迭代方法§2.1Gauss消去法高斯消去法步骤：(1)首先将增广阵[A,b]化为上三角阵；(2)用三角方程组,回代求解。Gauss消去法是一个古老的求解线性代数方程组的方法。但它改进、变形得到的选主元素消去法，三角分解法仍然是目前计算机上常用的有效方法。高斯消去法的基本思想•将原方程组逐次消去未知元,变为与之同解的上三角方程组,再回代求解。用矩阵语言叙述，上述过程是使用初等行变换把增广阵约化为上三角阵,使用上三角方程组,回代求解。高斯消去法的一般性叙述11121121222212nnnnnnnaaabaaabaaab用行变换根据下面的上三角方程组,逐次回代求解xk(1)(1)(1)(1)11111221(2)(2)(2)22122(1)(1)(1)1,11,1()()nnnnnnnnnnnnnnnnnnnnbaxaxaxbaxaxaxaxbaxb(3.3)11nnxxx)()()2(2)2(2)2(22)1(1)1(1)1(12)1(11000nnnnnnnbabaabaaa22n-1,n-1(1)(1)(1)(1)11112211(1)(1)(1)(1)21122222(1)(1)(1)(1)1122(a)nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb1.逐次Gauss消元法记n阶线性方程组为：(1)(1)(1)(1)(1)111122111(2)(2)(2)(2)222222()()()()()()111kknnkknnkkkkkkknnkkkkkkkknnkaxaxaxaxbaxaxaxbaxaxbaxaxb()()()(b)kkknkknnnnaxaxb设第k1步消元后方程组为：(c))1()1(1)1(1)1(1)1(11)1(1,1)()(1)(1)()2(2)2(21)2(12)2(22)2(22)1(1)1(11)1(11)1(12)1(121)1(11knnknnkknkkknknkkkkkkknkknkkkkkkkknnkkkknnkkkkbxaxabxaxabxaxaxabxaxaxaxabxaxaxaxaxa(1)()()(1)()()(,1,,)kkkijijikkjkkkiiikkaamabbmbijkn第k步消元后(c)中上标为k+1的元素由方程组(b)消元得到,计算公式为：第k步消元后(c)()(),1,....kikikkkkamikna完成n1次消元后，可将原方程组化成同解的上三角形方程组如下：(1)(1)(1)(1)(1)11112213311(2)(2)(2)(2)22223322()()()nnnnkkkkkkknnkaxaxaxaxbaxaxaxbaxaxb()()(d)nnnnnnaxb回代过程：逐步回代求原方程组的解(e)1,2,,2,1/)(/1)()()()()(nnkaxabxabxnklkkklkklkkknnnnnn.,,,,),()1,,2,1(0,)()2(22)1(11)()(bAxGaussaaaankannnkkkkkk：消去法求解线性方程组使用逐次才能均不为零而只有所有主元素为主元素称条件是：消元过程能进行到底的由以上讨论可知所以逐次Gauss消去法的乘除法总运算量为：33)1(2)1(2)1(3232nnnnnnnnnnN(1)()()(1)()()(,1,,)kkkijijikkjkkkiiikkaamabbmbijkn()(),1,....kikikkkkamikna()()()()()1/()/,1,2,,2,1nnnnnnnkkkkkkllkklkxbaxbaxaknn定理2.1逐次高斯消去法的前n-1个主元素均不为零的充要条件是方程组(a)的系数矩阵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：(1)(2)()1122.kkkkDaaa引入主元素的必要性对线性方程组AX=b,若其系数行列式det(A)0,则该方程组有唯一解,但是这一条件不能保证所有主元素都不等于零,只要某一主元素等于零,就不能用Gauss逐次消元法求解该方程组,即使所有主元素不等于零,但某一主元素的绝对值很小时,Gauss逐次消元法也是不适用的.通过交换方程次序,选取绝对值大的元素作主元,基于这种思想导出了主元素法.2.列主元消去法为简便起见,对方程组用其增广矩阵表示：),(21222221111211nnnnnnnbaaabaaabaaabAB并直接在增广矩阵上进行运算。列主元素法的具体步骤如下：得矩阵：然后进行第一次消元行交换行与第将第即：作为主元素元素列中选取绝对值最大的首先在增广矩阵的第第一步，,,,1max,1:11111iaainii),()1()1(bAB记。得矩阵再进行第二次消元行换行与第的第将矩阵使比如列中选主元的第在矩阵第二步),(,,2),(max,,2),(:)3()3(2)2()2()2(22)2(2)2(2)2()2(22bAibAaaabAiniii.,),(max,),(:)()()()()()()(次消元进行第行换行与第的第将矩阵使比如列中选主元的第在矩阵步第kiKbAaaakbAKkkkkiknikkkikkikkkk)2()2()2(2)2(2)2(2)2(22)1(1)1(1)1(12)1(11)2()2(),(nnnnnnbaabaabaaabA如此经过n1步,增广矩阵B被化成上三角形,然后由回代过程求解。在上述过程中,主元是按列选取的,故称为列主元法。使用高斯消去法的过程中，在第k次消元前，先对第k个增广阵[A(k),b(k)]做交换两行的变换，把中绝对值最大的元素换到(k,k)位置，使主元素在该列中绝对值最大，再消元。此方法叫列主元消去法。()(,1,...,)kikaikkn注解：此算法中的称为第k个列主元素，它总要被换到位置(k,k)。()(1,2,...,1)kkikakn3全主元消去法(k)ijka(i,jk,k1,,n),,如果不是按列选主元,而是在第个矩阵中全体待选系数：中选取主元则得到全主元消去法其计算过程如下：次消元。然后进行第的位置，的互换将它换到为主元，并通过行与列元作中，选取绝对值最大的阶子矩阵的所有元素的右下方在矩阵步第kankkjiaknAkkkkkijk)()()(),,1,,()1(:。第一消元，得到矩阵然后进行的位置列的互换到作为主元，并通过行与素中选取绝对值最大的元在全体系数第一步),(,),,2,1,(:)2()2()1(11bAanjiaij经过nk次消元后,得到与方程组(a)同解的上三角形方程组,再由回代过程求解。评论：顺序消去法要求方程组的系数矩阵A非奇异且主元素不为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