线性方程组的直接解法

第四章方程组的直接解法4.1Gauss消去法4.1.4Gauss-Jordan消元法4.1.3主元素消去法4.1.2矩阵的三角分解4.1.1Gauss消去法的计算过程第四章方程组的直接解法第4章线性方程组的直接解法教学目的1.掌握解线性方程组的高斯消去法、高斯选主元素消去法；2.掌握用直接三角分解法解线性方程组的方法；3.了解解对称正定矩阵线性方程组的平方根法与解三对角线方程组的追赶法；4.掌握向量，矩阵范数，矩阵的条件数等概念及方程组的扰动分析。教学重点及难点重点是1.解线性方程组的高斯消去法、高斯选主元素消去法；2.直接三角分解法解线性方程组的方法；3.向量，矩阵范数，矩阵的条件数等概念及方程组的扰动分析；难点是方程组的扰动分析。第四章方程组的直接解法实际中，存在大量的解线性方程组的问题。很多数值方法到最后也会涉及到线性方程组的求解问题：如样条插值的M和m关系式，曲线拟合的法方程，方程组的Newton迭代等问题。第4章线性方程组的直接解法第四章方程组的直接解法nnnnnnnbxaxabxaxa11111110)det(A对线性方程组：或者：bAx我们有Gram法则：当且仅当时，有唯一的解，而且解为：nnninninniiiiiaabaaaabaaDADDDx11111111111det),det(,第四章方程组的直接解法但Gram法则不能用于计算方程组的解，如n＝100，1033次/秒的计算机要算10120年解线性方程组的方法可以分为2类：①直接法：准确，可靠，理论上得到的解是精确的②迭代法：速度快，但有误差本章讲解直接法对于中小型方程组，常用直接解法。从本质上来说，直接方法的原理是找一个可逆矩阵M，使得MA是一个上三角阵，这一过程一般称为“消元”过程，消元之后再进行“回代”，即求解MAx=Mb。本章讨论Gauss消去法及其变形，以及一些情况下的特殊方法，最后进行误差分析。第四章方程组的直接解法4.1Gauss消去法我们知道，下面有3种方程的解我们可以直接求出：niabxaaadiagAiiiinn,,1,),,,(2211①n次运算nilxlbxllllllAiiijjijiinnnn,,1,1121222111②（n＋1）n/2次运算第四章方程组的直接解法1,,,122211211niuxubxuuuuuuAiinijjijiinnnn③（n＋1）n/2次运算第四章方程组的直接解法对方程组，作如下的变换，解不变①交换两个方程的次序②一个方程的两边同时乘以一个非0的数③一个方程的两边同时乘以一个非0数，加到另一个方程因此，对应的对增广矩阵(A，b)，作如下的变换，解不变①交换矩阵的两行②某一行乘以一个非0的数③某一个乘以一个非0数，加到另一行消元法就是对增广矩阵作上述行的变换，变为我们已知的3种类型之一，而后求根.第四章方程组的直接解法思路首先将A化为上三角阵，再回代求解。=4.1.1Gauss消去法的计算过程我们把方程组Ax=b写成1,22111,2222221211,111212111nnnnnnnnnnnnnnabxaxaxaabxaxaxaabxaxaxa),,2,1nj),(),()1()1(bAbA;,,2,1(niijijaa)1(设方程组(4,.1.1)的系数矩阵A非奇异,记(4.1.1)第四章方程组的直接解法,这样,方程组(4.1.1)又可写成。消元过程就是要按确定的计算过程对方程组进行初等行变换,将方程组化为上三角方程组.)1()1(bxAnnnnnnnbaaabaaabaaa21222221111211(1)(1)(1)(1)(1)11121311(2)(2)(2)(2)222322(3)(3)(3)3333()()000000nnnnnnnnaaaabaaabaabab第四章方程组的直接解法第一步消元:假设,作初等行变换运算0)1(11a步骤如下：niiaai,,2,1111行第行第nnnnnnnbaaabaaabaaa21222221111211)2()2()2(2)2(2)2(2)2(2211121100nnnnnnbaabaabaaa运算量：(n-1)*(1+n)第四章方程组的直接解法)3()3()3(3)3(3)3(3)3(33)2(2)2(2)2(23)2(221113121100000nnnnnnnbaabaabaaabaaaa运算量：(n-2)*(1+n-1)=(n-2)n第二步：niiaai,,3,2)2(22)2(2行第行第)2()2()2(2)2(2)2(2)2(2211121100nnnnnnbaabaabaaa第四章方程组的直接解法第k步消元:设消去法已进行k-1步,得到方程组,此时对应的增广矩阵是)()(kkbxA第四章方程组的直接解法第k步：nkiiaakkkkik,,1,k)()(行第行第类似的做下去，我们有：运算量：(n－k)*(1＋n－k＋1)=(n－k)(n－k＋2))()()3(3)3(3)3(33)2(2)2(2)2(23)2(2211131211000000nnnnnnnnbabaabaaabaaaan－1步以后，我们可以得到变换后的矩阵为：这就完成了消元过程。(4.1.4)第四章方程组的直接解法因此，总的运算量为：11)2)((nkknkn加上解上述上三角阵的运算量(n+1)n/2，总共为：)(33323nOnnn第四章方程组的直接解法因为A非奇异，所以可求解上三角方程组（4.1.4），通过逐次代入计算可得方程组的解，其计算公式为.1,,2,1,/(,/)(1)(1,)(1,)()(1,nniaxaaxaaxiiinkjjnnniniinnnnnnn(4.1.5)求解上式的过程称为回代过程。以上由消去过程和回代过程合起来求解（4.1.1）的过程就称为Gauss消去法，或称为顺序Gauss消去法。第四章方程组的直接解法如果我们用Cramer法则计算（4.1.1）的解，要计算n+1个阶行列式，并作n次除法。如果用子式展开的方法计算行列式，则计算每个行列式有n！次乘法。所以用Cramer法则大约需要（n+1）！次乘除法运算。例如，当n=10时，约需乘除法运算，而用Gauss消去法只需430次乘除法运算。例4.1用Gauss消去法解方程组.23132,22011209,23132321321321xxxxxxxxx.32979101011521070231321解第一步消元，令得增广矩阵,3/2,20/93121ll第四章方程组的直接解法第二步消元，令得增广矩阵,63/1032l.63536353001011521070231321利用回代公式（4.1.5）依次得到在这个例子中我们写出的是分数运算的结果。如果在计算机上进行计算，系数矩阵和中间结果都用经过舍入的机器数表示，中间结果和方程组的解都会有误差。.1,1,1123xxx4.1.2矩阵的三角分解从上面的消元过程可以看出，消元过程能顺利进行的重要条件是主元素。若用表示矩阵A的k阶顺序主子阵，则有下面的定理。.1,,2,1,0nkakkkkA第四章方程组的直接解法定理4.1全不为零的充要条件是A的顺序主子式其中。).,,2,1(,0)(kiaiii,,2,1,0detkiADiink证先证必要性设，则可进行k-1步消元程。显然，对，由于每步进行的初等变换不改变顺序主子式的值，所以第i-1步消元后有).,,2,1(,0)(kiaiii01)1(11Da2i.0)()2(22)1(11)()2(2)2(22)1(1)1(12)1(11iiiiiiiiiaaaaaaaaaD,0)(22)(12)(11)(mmmmAAAA用归纳法证充分性。k=1时，命题显然成立。设命题对m-1成立。现设由归纳假设有Gauss消去法可进行第m-1步，矩阵A变换为,,2,1,0detmiADii.1,,2,1,0)(miaiii第四章方程组的直接解法其中是对角元素为的上三角阵。因是通过消元过程由A逐步经初等变换得到的，A的m阶顺序主子式等于的m阶顺序主子式，即由可推出，定理得证。)(11mA)()1(1,1)2(22)1(11,,,,mmmmmmaaaa)(mA)(11mA)()1(1,1)2(22)1(11,,,,mmmmmmaaaa0mD0)(mmma定理4.2在方程组Ax=b中，A非奇异，则当A的所有顺序主子式均不为零时，可用Gauss消去法求解出方程组的解。特别地，若A为对称正定矩阵，则由对称正定矩阵的性质可知，对原方程组不必作任何处理，可直接Gauss消去法求解方程组。下面将消元过程用矩阵运算表示。对第k步，利用（4.1.3）给出的乘数，记，又记为第k个分量为1的单位向量，令Tnkkkklll),,,0,,0(,1)(Tke)0,,0,1,0,,0(ikl,1111,1)()(nkkkTkkkllelIL(4.1.6)第四章方程组的直接解法不难验证即IelIelIelIelITkkTkkTkkTkk))(())(()()()()(TkkkelIL)(1利用矩阵（4.1.6），第k步消元过程相当于这样经过n-1步消元过程得到,,)()1(121)()1(121nnnnnnbbLLLAALLL).,(),()1()1()()(kkkkkbAbAL这里，是上三角阵。记，又记)(nA)(nAU,1111)(1,213231211121nnnnnnllllllLLLL第四章方程组的直接解法这种矩阵称为单位下三角阵。L的对角线以下各元素就是各步消元过程的乘数。最后我们得到A=LU（4.1.7）称该式为A的LU分解。定理4.3矩阵，若其顺序主子式皆非零，则存在唯一的单位下三角阵L和上三角阵U，使A=LU。nnRA),,2,1(niDi其中，都是单位下三角阵，都是上三角阵。因A非奇异，则都可逆。A左乘，右乘即得因仍为上三角阵，也是上三角阵，同理是单位下三角阵，所以只能有即。定理得证证以上的分析已证明了A可作LU分解，下面证明分解的唯一性。设A有两个分解式,~~ULLUA~~,,,UULL~,LL~,UU~1U~1UU,~1~1ILLUU.~1~1LLUU1L~1U~~.,LLUU第四章方程组的直接解法分解式（4.1.7）也称为Doolittle分解。由（4.1.7）式可求出A的行列式，即若将上三角U写成，其中D是对角阵，是单位上三角阵，则有称该式为A的LDU分解，显然，这种分解具有唯一性。.det)()2(22)1(11nnnaaaA~UDU~ULDA~U（4.1.8）4.1.3主元素消去法在以上的Gauss消去法中，消元过程能进行的条件是主元素。例如，若，消去过程的第1步就不能进行。有时虽然但是很小，这时计算过程的舍入误差会导致消去法