数值分析(研究生)第四章线性方程组的直接解法一剖析

第四章线性方程组的直接解法（一）第一节实际问题的导入第三节矩阵的三角分解法第二节高斯消去法第四节解三对角方程组的追赶法上页下页返回求解bxA§1实际问题的导入Cramer法则：计算量太大.线性方程组的系数矩阵可分为：低阶稠密矩阵——阶数不超过500，零元素很少；大型稀疏矩阵——阶数高且零元素多.解线性方程组的方法：直接法——系数矩阵是低阶稠密矩阵的线性方程组及某些大型稀疏矩阵的线性方程组；迭代法——系数矩阵是大型稀疏矩阵的线性方程组.上页下页返回§2高斯消去法一、高斯消去法思路首先将A化为上三角阵，再回代求解.=上页下页返回消元记,)()1()1(nnijaAA)1()1(1)1(...nbbbbStep1：设，计算因子0)1(11a)...,,2(/)1(11)1(11niaamii将增广矩阵第i行mi1第1行，得到)1(1)1(1)1(12)1(11...baaan)2(A)2(b)...,,2,()1(11)1()2()1(11)1()2(njibmbbamaaiiijiijij其中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定理若A的所有顺序主子式均不为0，则高斯消元无需换行即可进行到底，得到唯一解.iiiiiaaaaA...............)det(1111注：事实上，只要A非奇异，即A1存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解.上页下页返回二、选主元消去法例1单精度解方程组211021219xxxx/*精确解为和*/...1000...00.1101191x8个...8999...99.0212xx8个用高斯消元法计算：911212110/aam999212210101010...0.011ma8个92121012mb9991010011100,112xx小主元可能导致计算失败.上页下页返回全主元消去法每一步选绝对值最大的元素为主元素，保证.1||ikmStepk:①选取;0||max||,ijnjikjiaakk②Ifikkthen交换第k行与第ik行;Ifjkkthen交换第k列与第jk列;③消元.注：列交换改变了xi的顺序，须记录交换次序，解完后再换回来.列主元消去法省去换列的步骤，每次仅选一列中最大的元.0||max||,iknikkiaak上页下页返回例2211111091,112xx11021111102119注：列主元法没有全主元法稳定.0,112xx例3211101019999991010010101注意：这两个方程组在数学上严格等价.标度化列主元消去法对每一行计算。为省时间，si只在初始时计算一次.以后每一步考虑子列中最大的aik为主元.||max1ijnjiasnkkkaa...iiksa注：稳定性介于列主元法和全主元法之间.上页下页返回实际应用中直接调用高斯消元法解3阶线性方程组的结果：结合全主元消去后的结果：上页下页返回.723134523－－＋－＋线性方程组用高斯列主元消去法解例zyxzyxzyx上页下页返回高斯-若当消去法与高斯消元法的主要区别：每步不计算mik，而是先将当前主元akk(k)变为1;把akk(k)所在列的上、下元素全消为0;bAxIbxA1上页下页返回运算量由于计算机中乘除运算的时间远远超过加减运算的时间，故估计某种算法的运算量时，往往只估计乘除的次数，而且通常以乘除次数的最高次幂为运算量的数量级.高斯消元法: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回代乘除次数：高斯消元法的总乘除次数为，运算量为级.nnn3132333n上页下页返回全主元消去法:比高斯消元法多出，保证稳定，但费时.33nO列主元消去法:比高斯消元法只多出，略省时，但不保证稳定.32nO标度化列主元消去法:比高斯消元法多出除法和，比列主元法稳定.但若逐次计算si(k)，则比全主元法还慢.)(2nO32nO高斯-若当消去法:运算量约为.故通常只用于求逆矩阵，而不用于解方程组.求逆矩阵即.23nO1||AIIA上页下页返回§3矩阵的三角分解法高斯消元法的矩阵形式：Step1:)0(/111111aaamii记L1=1...11121nmm，则][)1()1(1bAL)1(1)1(1)1(11...baan)2(A)2(bStepn1:)()2(2)1(1)()2(2)2(22)1(1)1(12)1(11121..................nnnnnnnnnbbbaaaaaabALLL其中Lk=1...11,,1knkkmm一、矩阵的LU分解上页下页返回1kL1...11,,1knkkmm111211...nLLL111jim,记为L单位下三角阵记U=)()2(2)2(22)1(1)1(12)1(11............nnnnnaaaaaaLUA上页下页返回定理若A的所有顺序主子式均不为0，则A的LU分解唯一（其中L为单位下三角阵）.证明：由§1中定理可知，LU分解存在.下面证明唯一.若不唯一，则可设A=L1U1=L2U2，推出121UU211122211LLUULL一般上三角阵单位下三角阵I注：L为一般下三角阵而U为单位上三角阵的分解称为Crout分解.实际上只要考虑A*的LU分解，即，则即是A的Crout分解.ULA~~**~*~LUA上页下页返回道立特分解法：——LU分解的紧凑格式反复计算,很浪费哦……通过比较法直接导出L和U的计算公式.思路nnnnnnnnuuullaaaa............1.........11..................1111211111),min(1jikjkkiuljia上页下页返回),min(1jikjkkijiula固定i:对j=i,i+1,…,n有ijkjikikijuula11lii=1kjikikijijulau11a将i，j对换，对j=i,i+1,…,n有iijikiikjkjiulula11iiikkijkjijiuulal/)(11b算法:道立特分解法Step1:u1j=a1j;lj1=aj1/u11;(j=1,…,n)Step2:计算和，从i=2,…,n1;Step3:ab11nkknnknnnnulau一般采用列主元法增强稳定性.但注意也必须做相应的行交换.b上页下页返回.5423351244zyxzyxzyxLU分解法）解方程组法（用矩阵的直接三角分解例上页下页返回对称正定矩阵的分解法定义一个矩阵A=(aij)nn称为对称阵，如果aij=aji.定义一个矩阵A称为正定阵，如果对任意非零向量都成立.0xAxTx回顾：对称正定阵的几个重要性质A1亦对称正定，且aii0若不然，则0xA存在非零解，即0xAxT存在非零解。1111)()(,AAIAAIAATTT对任意,存在,使得,即.0x0yxyAxAy1011yAyyAAAyxAxTTT其中0xAxaTiiTx)0...1...0(第i位A的顺序主子阵Ak亦对称正定对称性显然。对任意有,其中.kkRx00xAxxAxTkkTknkRxx00A的特征值i0设对应特征值的非零特征向量为，则.20xxxxAxTTxA的全部顺序主子式det(Ak)0因为niiA1)det(二、平方根法上页下页返回将对称正定阵A做LU分解U=uij=u11uij/uii111u22unn记为UD~A对称TUL~即TLDLA记D1/2=11u22unnu2/1~LDL则仍是下三角阵TLLA~~nnRL定理设矩阵A对称正定，则存在非奇异下三角阵使得.若限定L对角元为正，则分解唯一.TLLA注：对于对称正定阵A，从可知对任意ki有.即L的元素不会增大，误差可控，不需选主元.P126ikikiila12iiikal||上页下页返回nnnnnnnfffxxxbacbacbacb212111122211Step1:对A作Crout分解111121nnnA直接比较等式两边的元素，可得到计算公式（p130）.Step2:追——即解：fyL,111fy),...,2()(1niyrfyiiiiiStep3:赶——即解：yxU)1,...,1(,1nixyxyxiiiinn与G.E.类似，一旦i=0则算法中断，故并非任何三对角阵都可以用此方法分解.§4解三对角方程组的追赶法上页下页返回定理若A为对角占优的三对角阵，且满足，则追赶法可解以A为系数矩阵的方程组.0,0,0||||,0||||11iinncaabcb注：如果A是严格对角占优阵，则不要求三对角线上的所有元素非零.根据不等式可知：分解过程中，矩阵元素不会过分增大，算法保证稳定.运算量为O(6n).||||||||||,1||1iiiiiiiiabbab