第三章线性方程组解法

消去法Gauss消去法列/全主元素消去法Gauss-Jordan消去法求矩阵的逆解三对角方程组的追赶法矩阵分解法矩阵的LU分解正定矩阵的三角分解方程组的性态和条件数迭代法Jacobi、Gauss-Seidel、SOR迭代收敛条件及误差估计第三章线性方程组解法引言设有n元线性方程组：11112211211222221122nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb若用A表示矩阵，x表示未知数，b表示右端项，该系统可以写为Axb.引言最简单的直接解法：Cramer法则，根据该方法，方程组的解为(1,2,...,)iixin其中det()A，而i是A中第i列换成向量b所得矩阵的行列式。假定用按某行展开的方法计算行列式，那么，Cramer法则求解一个n元线性方程组所需要的乘法运算次数超过(1)!n。求解线性方程组的方法求解线性方程组的方法可分为两大类：直接法和迭代法。直接解法：假设计算过程没有误差的情况下，经过有限步算术运算可以得到线性方程组的精确解。但是由于实际计算中舍入误差的影响，这类算法一般也只能得到精确解的近似，比如：高斯消去法、三角分解法。迭代解法：构造适当的向量序列，用某种极限过程来逼近精确解。例如：Jacobi方法、Gauss-Seidel方法、SOR方法等。§1Gauss消元法Gauss消元法是最基本的一种方法，下例说明其基本思想:例1.解线性方程组：123123123612331518315xxxxxxxxx解：消去x1，进行第一次消元：首先找乘数，以-12乘第一个方程加到第二个方程，以18乘第一个方程加到第三个方程上可得同解方程组：1232323615957211793xxxxxxx例1（续）123233615957226655xxxxxx再消一次元得：二次消元后将方程化为上三角形式，然后进行回代容易解出：x3=3,x2=2,x1=1。1.1Gauss消去法求解思想：（1）逐次消去变量，将原方程组转化为同解的上三角方程组，这个过程称为消元过程；（2）按照与方程相反的顺序求解该上三角方程组，这个过程称为回代过程。——称为高斯消元法。(GaussElimination)消元过程目标：对方程组对应的增广矩阵111121221[]nnnnnnaabaabAbaab做有限次的初等行变换，使得最后的系数矩阵部分变换为上三角矩阵。将初始输入改写为：(1)(1)(1)1111(1)(1)(1)212(1)(112)(1)[]nnnnnnaabaabAbaabGauss消元法的消元过程第一步：假设(1)110a。保持第１行不变，依次消去第1列中除(1)11a以外的所有元素。方法：从第2行起，每行(第i行)减去第1行乘以(1)11(1)11iiala(i=2,3,…n)，得(1)(1)(1)(1)(1)11121311(2)(2)(2)(2)22232(2)(2)(2)(2)3233(2)(2)(2)(2)1,21,(2)(2)2331,3(2)(132)20000nnnnnnnnnnnnnaaaabaaabaaabaaabaaab(2)(1)(1)11(2)(1)(1)11,2,3,,ijijijiiiaalaijnbblb第二步：假设)22(20a。保持前２行不变，依次消去第2列中除(1)(2)1222,aa以外的所有元素。方法：从第3行起，每行(第i行)减去第2行乘以(2)22(2)22iiala(i=3,…n)，得(1)(1)(1)(1)(1)11121311(2)(2)(2)(2)22232(3)(3)(3)33(3)(2333)(3)1,(3)(3)(13133),0000000nnnnnnnnnnnaaaabaaabaabaabaab(3)(2)(2)22(3)(2)(2)22,3,,ijijijiiiaalaijnbblb第k步：设第k1步消元后得原方程组的同解方程组为：(1)(1)(1)(1)(1)111122111(2)(2)(2)(2)222222()()()kknnkknnkkkkkkknnkaxaxaxaxbaxaxaxbaxaxb()()()kkknkknnnnaxaxb()()()0,/(1,,)(1,,),,kkkkkikikkkikalaaiknikliknk设记将上方程组中第个方程减去第个方程乘以完成第步消元得同解方程组：(1)(1)(1)(1)(1)(1)111122111111(2)(2)(2)(2)(2)222221122()()()11kkkknnkkkknnkkkkkkkkkknnkaxaxaxaxaxbaxaxaxaxbaxaxaxb()(1)(1)(1)1,1111(1)(1)11kkkkkkkknnkkknkknnnaxaxbaxax(1)knb(1)()()(1)()()(,1,,)kkkijijikkjkkkiiikkaalabblbijkn将上述过程进行下去，对n阶方程组，共需进行1n步消元过程，就能将原方程化为同解的上三角形的方程组(1)(1)(1)(1)(1)11121311(2)(2)(2)(2)22232(3)(3)(3)33(1)(1)1,()(2331)000000000nnnnnnnnnnnnnaaaabaaabaababab其等价于线性方程组(1)(1)(1)(1)(1)11112213311(2)(2)(2)(2)22223322(3)(3)(3)33333()().........nnnnnnnnnnnaxaxaxaxbaxaxabaxaxbaxbGauss消元法的回代过程回代过程：逐步回代求得原方程组的解()()()()()1/()/1,2,,2,1nnnnnnnkkkkkkllkklkxbaxbaxaknn定理：对方程组Axb，若A的所有顺序主子式均不为0，则可用高斯消去法将方程组化为三角形方程组，且求出唯一解。Gauss消元法可以进行的充分条件()()(1)(2)()1122,0(1,2,,1)(),,,,,.kkkkkknnnaknaaaaGaussAxb由以上讨论可知消元过程能进行到底的条件是：称为主元素而只有所有主元素均不为零才能使用消去法求解线性方程组：Gauss消元法的算法描述for1:1fori1: j1:1   forendendendikikkkijijikkjknknalaknaala1for:1:1()/endniiijjiijiinxbaxa消元过程回代过程ika,1inaGauss消元法的计算量由于在计算机中作乘除运算量所需时间远大于作加减运算所需时间，故只考虑作乘除运算量。由消元法步骤知，第k次消元需作nk次除法，作(nk)(nk+1)次乘法，故消元过程中乘除法运算量为：112)1(3)1)((:nknnknkn乘法次数11)1(2)(:nknnkn除法次数nkknnknnknx1)1(2)(1:乘法：次；除法：运算量为：次乘法，因此回代过程次除法和需求回代过程中所以Gauss消去法的乘除法总运算量为：33)1(2)1(2)1(3232nnnnnnnnnnN()()()()()1/()/1,,1nnnnnnnkkkkkkllkklkxbaxbaxakn(1)()(1)()()(,1,,)kkijijikkjkkkiiikkaalabblbijkn1.2主元消去法对一般的很好求解的系统，高斯消去法计算效果不一定好。例2.12011112xx该系统的解很容易得到，但是却无法用高斯消去法。1211112xx例3.，其中是一个小量。111211012xx解.若利用高斯消去法11211221110xxx对应的解为：121111211xx而该问题的真解为若在上述例子求解过程中交换两行，则问题将有所改善：1211211xx121120112xx高斯消去法可以推出212(12)/(1)121xxx其对应的解为()0kkka注：除了避免外，还应避免主元素绝对值过小。在该过程中，主元是按列选取的，故称为列主元法。列主元素法的具体步骤如下：1(1)(1)1(2)(,112)1:1,max1,,]iiinaaiAb第一步首先在第列中选取绝对值最大的元素作为主元素即：将第行与第行交换然后进行第一次消元，得矩阵[(1)(1)(1)1111(1)(1)(1)(1)(1)2122(1)(1)(1)1[]nnnnnnaabaabAbaab2(2)(2)(2)(2)222(2)(2)(3)(3)2:,2,max,2,,,iiinAbaaAbiAb第二步在矩阵[]的第列中选主元使将矩阵[]的第行与第行列换再进行第二次消元得矩阵[]。()()()()()():,,max,,.kkkkkikikkinkkkkAbkaaAbkik第步在矩阵[]的第列中选主元使将矩阵[]的第行与第行列换进行第次消元列主元消去法(1)11(2)(2):(,1,2,,),(,)ijaijnaAb第一步在全体系数中选取绝对值最大的元素作为主元，并通过行与列的互换到的位置然后进行第一次消元，得到矩阵。()()():(1)(,,1,,)kkijkkkkAnkaijkknak第步在矩阵的右下方阶子矩阵的所有元素中，选取绝对值最大的元作为主元，并通过行与列的互换将它换到的位置，然后进行第次消元。全主元消去法()(,,1,,),,kijaijkkn如果不是按列选主元，而是在全体待选系数：中选取主元则得到全主元法其计算过程如下：全主元消去法：精度高，但是要换列和记录次序，比较麻烦。123123123612331518315xxxxxxxxx例4.用主元素法求解线性方程组：计算过程保留三位小数。111161233151831151831151233151116183115012.333501.1670.9445.167183115,01.1670.9445.16解法（列主元法）：求解过程如下：因其增广矩阵为：第一与第三行互换第一次消元第二三行互换3217012.333518311501.1670.9445.167003.1429.4283.0012.001.00xxx第二次消元由回代过程求解得：，，21116123315183115183116,1233151116183115012.33