计算方法-第六章线性方程组的数值解

第六章线性方程组的数值求解6.1高斯顺序消去法6.2高斯列主元消去法6.5追赶法6.6向量与矩阵的范数6.7误差分析6.8迭代法引言bAxbbbxxxaaaaaaaaabxaxaxabxaxaxabxaxaxamnmnmmnnmnmnmmnnnn简记为矩阵形式线性方方程组212121222211121122112222212111212111线性方程组的数值解法一般有两类：1、直接解法：经过有限次的算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差）。但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解。本章主要研究此类问题的解法。2、迭代法：用某种极限过程去逐步逼近线性方程组精确解的方法。迭代法具有需要计算机的存储单元较少、程序设计简单、原始系数矩阵在计算过程中始终不变等优点。123231236451221xxxxxxxx用消去法解方程组例11161116()0415041522110411111160415()0026*(1,23):,TAbx回代解、求解解得6.1高斯顺序消去法(1)(1)(1)(1)(1)(1)1111211(0)111(1)(1)(1)(1)(1)11(1)(1)212222(2,3,,)(1)(1)(1)(1)12(1)(1)(1)11121(2)(2)222(2)(2(1):00ainlaianinnnnnnnnnnnaaabaaabAbaaabaaaaaaa(1)(1)1(2)(2)(2)(1)2(1)2)(2),:,ijijnbAAbAbbbaab其中，(2)(1)(1)11(2)(1)(1)11(2,,;2,,)(2,,)ijijijiiiaalainjnbblbin(2)(1)(1)(1)(1)(2)2111211(0)222(2)(2)(2)(2)22(2)(2)2222(3,,)(2)(2)(2)2(1)(1)(1)(1)111112(2)((2)2222(3)0(2):0000ainlaianinnnnnnnnnaaabaabAbaababaaabaa2)(3)(3)(3):nAbb(3)(2)(2)22(3)(2)(2)22(3,,;3,,)(3,,)ijijijiiiaalainjnbblbin(1)(1)(1)(1)(1)1112111()(2)(2)(2)(2)()22222(0)()()()()()()(1,,)()()()(1)(1)(1)11121():knkakikknlaikkkkakkkkkkkiknkkknkkkknknnnkaaaabaaabkAbaabaabaaaa(1)(1)11(2)(2)(2)(2)22222(1)(1)()()()(1)(1):0nknkkkkkkkknkkknnnbaaabAbaabab(1)()()(1)()()(1,,;1,,)(1,,)kkkijijikkjkkkiiikkaalaiknjknbblbikn()()(1),1nnnnnAxbA（）继续上述过程直到完成第步消元计算。最后得到与原方程组等价的简单方程组其中为上三角（梯）形。()()()()()1()()1,,1nnnnnnkkkkkkjjkkjkxbaxbaxakn求解三角方程组后,得(1)(1)(1)(1)111211(2)(2)(2)()()2222()()()():()nnnnnnnnnnnaaabaabAbabAxb对应方程组为(),(1)0(1,2,,)()()(2)()nnkkkAxbARaknAxbAAxb设其中如果，则可通过高斯（顺序）消去法将约化为等价的三角方程组，且计算公式。如果为非奇异矩阵，则可通过高斯（顺序）消去法（及交换两行的初等变换）将约化为定理。高斯顺序消去法的条件()11111110(1,2,,)0(1,2,,).0,0(1,2,,)iiiiiiiiiaikADikDaaaDikaa约化的素的充要条件是矩阵的顺序主子式定主即理元213111(1)(2)(1)(2)111111,nllLlLAALbb矩阵三角分解法Ax=b是线性方程组,A是n×n方阵,并设A的各阶顺序主子式不为零。令A(1)=A,当高斯消元法进行第一步后,相当于用一个初等矩阵左乘A(1)。不难看出，这个初等矩阵为重复这个过程，最后得到1,()(1)()(1)1111,kkknkkkkkkkLllLAALbb一般地(1)()121(1)()111nnnnLLLAALLLbb()111121211113132121123,1111nnnnnnAUALLLULUlllLLLLlll将上三角矩阵记为得到其中为单位下三角矩阵这就是说，高斯顺序消去法实质上产生了一个将A分解为两个三角形矩阵相乘的因式分解，于是我们得到如下重要定理。11111(1)(2,3,,)/(2)(1,2,,1)()/iiiikkknnnnnikkiikiLybUxyybyblyinxyuinnxyuxu具体计算公式为iAA0(1,2,,(LU1)A)nDinLU设为阶矩阵，如果的顺序主子式，则可分解为一个单位下三角矩阵和一个上三角矩阵的乘积，且这种分解是定唯理矩阵的分一的。解当A进行LU分解后，Ax=b就容易解了.即Ax=b等价于:123123142521831520xxx用直接三法2角解例分解TTTTxUxyLLUA)3,2,1(,)72,10,14()72,10,14(,)20,18,14(2400410321153012001得得求解用分解公式计算得解y:1-1-11-1-A.102123269100102:ALUL=110,U=02123100210-110011L=-110U=0-241-3110023AULA求A的LU分解，并利用分解结果求解的分解为从而，故例103110-1100351110--110244441-311311002222()(),00kkkkkkaa由前面的高斯消去法知道在消元过程中可能出现的情况，这时消去法将无法进行；即使主元素但很小时，用其作除数，会导致其他元素数量级的严重增长和舍入误差的扩散，最后也使得计算解不可靠。1234020102232243017616564xxxx用高斯列主元法解线性方程组例6.2高斯列主元素消去法列主元消去法02010616562232222322:430174301761656020106165661656111351104110543333751861113009041111333324111020100061133Ab解1234616561111320411331756210091111342978200027525xxxx故在四位浮点十进制数的计算机上,结果为x1=0x2=1例5用高斯顺序消元法解线性方程组，并假设求解是在四位浮点十进制数的计算机上进行0.0001x1+x2=1x1+x2=29999x2=99980.0001x1+x2=1解：消元，得这与实际结果相差甚远。假设求解是在四位浮点十进制数的计算机上进行0.0001x1+x2=1x1+x2=2将两个方程对调，得x1+x2=20.0001x1+x2=1在四位浮点十进制数的计算机上,上式为x1+x2=2即x1+x2=2(0.1000×101-0.00001×101）x2=1x2=1（1-0.0001)x2=1x1+x2=2消元，得解得：x1=1，x2=1现在我们再用列主元法解例311112222211111nnnnnnnnnbcxfabcxfabcxfabxf6.5追赶法在一些实际问题中，例如解常微分方程边值问题，热传导方程以及船体数学放样中建立三次样条函数等问题，都会要求解系数矩阵为对角占优的三对角线方程组其中|i-j|1时,系数矩阵元素aij=0,且满足如下的对角占优条件:(1)|b1||c1|0,|bn||an|0(2)|bi|≥|ai|+|ci|,aici≠0,i=2,3,…,n-1.1122211111221iii111nnnnnnnnbcabcAabcabLU其中、、为待定系数。111111/()/()(2,3,,)(1,21,,2,)iiiiiiinniiiiLyfUyfbyfybinxyxnxyyxin解解111i11//()(2,3,,1)(2,3,,)iiiiiiiiiicbcbainbin计算公式121121121nnnyyyxxx追计算系数及的过程称为计算方程组的解的过程称的过程赶为。的过程。6.6向量和矩阵的范数定义(向量范数)x和y是Rn中的任意向量,向量范数‖•‖是定义在Rn上的实值函数,它满足:(1)‖x‖≥0,并且当且仅当x=0时,‖x‖=0;(2)‖kx‖=|k|‖x‖,k是一个实数;(3)‖x+y‖≤‖x‖+‖y‖常使用的向量范数有三种,设x=(x1,x2,…,xn)T11112221max-1-()2-iinniiniixxxxxx向量的范数向量的范数向量的范数常使用的矩阵范数有三种,设x=(x1,x2,…,xn)T1111i1maxmax2AmaxAmax()2-()nijinjnijinTTTaaAAAAAAA矩阵的行范数矩阵的列范数矩阵的范数,其中表示的最大特征值。()(1)A0(00)()(2)()(3)()(4)())(nnnnARNAAAAcAcAcABABABABNAR如果矩阵的某个非负的实值函数，满足条件正定条件为实数齐次条件三角不等式则称是的一个矩阵定义矩阵的范数范数（或模）46.522115A7A,6A