第3求解线性代数方程组的数值方法

求解线性代数方程组的数值方法第三章111112211211222221122...............nnnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb阶线性方程组：其中,Axb矩阵表示记为系数矩阵未知向量常数项111212122212.........nnnnnnaaaaaaAaaanxxxx21nbbbb21235det()0,det()(1,2,...,)det()1(1)!30,2.3810iiAAxinAnnnnnnnn如果线性方程组的系数行列式不为零，即则该方程组有唯一解。由克莱姆(Cramer)法则，其解为这种方法需要计算个阶行列式并作次除法，而每个阶行列式计算需作次乘法，计算量十分惊人。如需次乘法。可见其在理论上是绝对正确，但在较大时，在实际计算中确实不可行的。解线性方程组的两类数值方法：直接法:经过有限次四则运算后可求得方程组精确解的方法(不计舍入误差!)迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。（一般有限步内得不到精确解）特点：准确，可靠，理论上得到的解是精确的。适合于中小规模的方程组。特点：速度快，但有误差。适合于大规模的方程组。Cramer法则是一种直接法，但无法实用3直接法概述直接法是将原方程组化为一个或若干个三角形方程组，而后再求解的方法．对于n阶线性方程组,bAx，若0)det(A.bAx有唯一解则方程组41.Gauss消元法.A)n(为上三角阵其中的解不难得到。三角形方程组)n()n(bxAbAx)()(nnbxA作一系列行变换对)()1()1(bA5bAx的乘积与上三角矩阵矩阵分解成下三角，若将对线性方程组ULAbAxLUA则bLUxbLyyUx都是三角形方程组上述方法称为直接三角形分解法不论是Gauss消元法还是直接三角形分解法,最终都归结为解三角形方程组2.三角分解法6对方程组，作如下的变换，解不变：①交换两个方程的次序②一个方程的两边同时乘以一个非0的数③一个方程的两边同时乘以一个非0数，加到另一个方程一、Gauss消元法这相当于对增广矩阵(A,b)作如下的变换：①交换矩阵的两行②某一行乘以一个非0的数③某一行乘以一个非0数，加到另一行消元法就是对增广矩阵作上述行的变换，变为三角形线性方程组，而后求根。§1.Gauss消元法7Gauss消元法的基本思想：11112211211222221122...............nnnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb先将阶线性方程组：1111221122222............nnnnnnnngbxbxbxgbxbxgbx转化为等价的（同解的）上三角形方程组：11,,...,nnxxx上述过程称为。然后逐次计算出，这一过程称消元过程回为代过程。8Gauss消元法的运算量步消元时作第k乘法次数：次)1)((knkn除法次数：次)(kn数为步消元乘除法运算总次作第k次)2)((knkn总次数为步消元需作乘除法运算完成全部1n11)2)((nkknkn652323nnn9全部回代过程需作乘除法的总次数为niin1)1(222nn于是Gauss消元法的乘除法运算总的次数为MD3323nnn)(323nOn数级类似地，可得Gauss消元法的加减法运算总的次数为121(1)[()()]2nknnPMnknk325326nnn10由于计算机完成一次乘除运算所耗时间要远远多于完成一次加减运算的时间，而且按统计规律，在一个算法中，加减运算和乘除运算次数大体相当，故在衡量一个算法的运算量时只需统计乘除的运算次数。很大时当n3323nnnMD33n20时如nGauss消元法乘除法约为2700次而如果用Cramer法则的乘除法运算次数约为20)120)(120(!2020910用行列式定义11123231236;45;221.xxxxxxxx用消元法解方.程.组例3121116|04152211Ab用增广矩阵表示求解解过程1116041504111111604150026312rr32rr回代求解3213,2,1.xxx12从Gauss消元法的过程自然想到：如果在消元过程中把对角线上方未知量的系数也化为零，使方程组化成每个方程只含一个未知量的方程组，则无须回代就可得到解。这种消元法称为Gauss－Jordan消元法。但经计算，它需要的乘除法次数为32.22nnn显然，其运算量超过Gauss消元法。所以用Gauss－Jordan消元法求解线性代数方程组是不可取的。不过，用它来求逆矩阵却有方便之处。13二、选主元Gauss消元法()()()00kkkkkkkkkGaussakaa消元法中，称为第步的主元。在消元过程中可能出现的情况，这时消元法将无法进行；即使主元素但很小，用其作除数，也会导致其他元素数量级的严重增长和舍入误差的扩散，对计算结果将造成很不利的影响。例3.1.3用Gauss消元法解线性方程组(用3位十进制浮点数计算）12120.00011.001.00,1.001.002.00.xxxx14解本方程组的精度较高的解为Tx)99989999.0,00010001.1(*用Gauss消元法求解(用3位十进制浮点数计算)),(bAA0.00011.001.001.001.002.002110000l00.1,00.021xx回代后得到主元440.00011.001.000.001.00101.0010－999912120.00011.001.00,1.001.002.00.xxxx与精确解相比,该结果相当糟糕！究其原因,在求行乘数时用了很小的数0.0001作除数!15(2)(2)2222(2)(2)22222122211(1)(1)1111(1)1(1)1111(((1.001.00(),()1().aababxxxxxxxxaaa，使得计算和时，分别产生了误差：)=1(万分之一),)=2(万分之二).由此导致解及的误差：)-0.0001(仍为由于小主元万分之一),百分之百由于小主元，的出现的误差被扩大了10000倍。上述例题表明：Gauss消元法是不稳定的算法，其中小主元是不稳定的根源。因而在Gauss消元法中要避免小主元的出现。这就需要采用“选主元”的技术。所谓选主元，简单地说就是选取绝对值最大的元素作主元。16全选主元Gauss消元法()(),||max||Gausskkpqijkijnaakpq：在第步消元过程中，首先全选主元，即求和，使得并互换矩阵的第k行与第p行，第k列与第q列，然后再按基本照通常的消元法进思想，行消元。(1)(1)(1)(1)111211(2)(2)(2)2222()()()()()()..................nnkkkkkknkkkknknnnaaabaabaabaab),()()(kkbA),()1()1(bA在此范围内选主元17kqxxx在全选主元消元法中，如果进行了列交换，则相应的解向量的排序也应作相应交换。例如，若作了第k列与第q列交换，相应的和的位注：置也应对换。全选主元消元法基本上可保证舍入误差不会扩散，因而它。但是，该方法的每一消元步都需要选增加了计算时间是一个稳定以及程序设的算计法主元，的难度。1231(1)(21)1()().63nknnnnkOn总的比较次数：需进行元素比较18列选主元Gauss消元法()()()()()||max(,)Gaus||skikkkpkinkkikkaaakpAb：在第步消元过程中，仅仅在中选主元，即求，使得并互换矩阵的第k行与第p行，然后再按照通常的基本思想,i=k,k+1,..消元法进.,n，行消元。(1)(1)(1)(1)111211(2)(2)(2)2222()()()()()()..................nnkkkkkknkkkknknnnaaabaabaabaab),()()(kkbA),()1()1(bA在此范围内选主元19()()||||/||1kkikikkklaa和全选主元相比较，列选主元消元法的比较次数降低了一个数量级，而且，程序设计也很简单。此外，列选主元消元法可保证，因此，在某种程度上能够保证舍入误差不会扩散，方法基本上讲。由于上述原因，人们一般乐于用列选主元消元法而不用全选主元消元法求解线性代数是稳定的方程组。121(1)1()().22nknnnkOn总的比较次数：不必选主元的情况：当系数矩阵A对称正定或严格对角占优或不可约对角占优时，可不必选主元。20),(bAA1.001.002.000.00011.001.00210.0001l现用列选主元消元法重解例3.1.3：将方程组的1,2行交换，即得00.1,00.121xx回代后得到这是一个相当不错的结果！1.001.002.000.001.001.000.999921),(bAA例3.1.4解线性方程组(用8位十进制尾数的浮点数计算)321643.5072.12623.4712.3132103218xxx解这个方程组和例3.1.3一样，若用Gauss消元法计算会有小数作除数的现象，若采用换行的技巧（即列选主元消元法），则可避免。321643.5072.12623.4712.3132108行交换因此的列元素为绝对值最大很小3,1,2,10138a2231rr1233210623.4712.31643.5072.128218310.50.510ll101.05.03103.0102.001018015.0103176.00643.5072.12绝对值最大不需换行320.62972292l54138685.05.031041555186.0001018015.0103176.00643.5072.12),()1()1(bA),()2()2(bA),()3()3(bA23)3()3(3333abx经过回代后可得)1(113)1(132)1(12)1(11axaxabx54138685.01041555186.039257367.0)2(223)2(23)2(22axabx103176.01018015.05.03x05088607.049105820.054138685.05.031041555186.0001018015.0103176.00643.5072.12事实上,方程组的准确解为Tx)367257384.0,050886075.0,491058227.0(*24小结•求解下三角（上三角）线性方程组的计算量：n(n+1)/2=O(n2/2)•用Guass消元法求解线性方程组的计算量1/3O(n3)•全选主元Guass消元法的总得比较次数1/3O(n3)•列选主元Guass消元法的总的比较次数1/2O(n2)•编写程序：用列选主元Gua