Chapter3线性方程组的解法(下)-ZTY

下午6时30分25秒1下午6时30分25秒1线性方程组第三章第三章解线性方程组的迭代法基础—向量与矩阵的范数3.5.1向量的范数/*vectornorms*/为了研究线性方程组近似解的误差估计和迭代法的收敛性，需要对n维向量空间Rn中的向量的“大小”给出某种度量。衡量数的误差用到绝对值；现代数学中常用“范数”来度量向量的“大小”。定义3.1设为定义在Rn上的实函数，如果对任意它满足条件：（1）当且仅当x=0(正定性）（2）（对任意常数）（齐次性）（3）（三角不等式）33.5.1向量的范数()fxxnRx0(0xx)xxRxyxy（对任意）nRx则称为Rn上的向量范数()fxx（4）xyxy定义3.1向量范数常用向量范数：niixx11||||||向量的1-范数：niixx122||||||向量的2-范数：pnipipxx/11||||||向量的p-范数：||max||||1inixx向量的-范数：可以证明向量函数||x||p是Rn上的向量的范数，且前三种范数是“p”范数的特殊情况nniinniinxxxxxxxxxxxxxx,,,max21121121122222125.5124.712xxx5.4,5.5,0.2,,321xxxx2x1x3x0.25.55.4向量范数的几何意义7例设x=(-1,2,3)T计算||x||1,||x||∞,||x||2||x||1=1+2+3=6解||x||2=(12+22+32)1/2=14||x||∞=max{1,2,3}=3nxxx211x2/1222212)(nxxxxinix1maxx定义向量序列收敛于向量是指对每一个1in都有。(){}kx*x*)(limikikxx可以理解为()||*||0kxxklim*)(limikikxx()||*||0kxxklim定义3.2向量收敛的定义§1NormsofVectorsandMatrices–MatrixNorms定义3.3矩阵范数/*matrixnorms*/定义Rmn空间的矩阵范数||·||对任意满足：nmRBA,00||||;0||||)1(AAA（正定性/*positivedefinite*/)||||||||||)2(AAC对任意(齐次性/*homogeneous*/)||||||||||||)3(BABA（三角不等式/*triangleinequality*/)(4)*||AB||||A||·||B||（相容/*consistent*/当m=n时)(5)||Ax||||A||·||x||nRx特别有：njijaAni1||max||||1（行或无穷范数）niijaAnj11||max||||1（列或1范数）10例设计算||A||1、||A||∞5431Aniijnja111maxAnjijnia11maxA解||A||1=max{5,8}=8||A||∞=max{4,9}=93.5.2矩阵的范数（续）11在用直接法解线性方程组时要对系数矩阵不断变换如果方程组的阶数很高,则运算量将会很大因此对线性方程组bAx要求找寻更经济、适用的数值解法nnnnRxRbRA,,设3.6线性方程组的迭代解法12迭代法是对任意给定的初始近似解向量，按照某种方法逐步生成近似解序列，使解序列的极限为方程组的解。因此迭代法是用某种极限过程去逐步逼近线性方程组精确解的方法。可以用有限步运算算出具有指定精确度的近似解。主要方法：1.雅可比(Jacobi)迭代法2.高斯-塞德尔（Gauss-Seidel)迭代法3.逐次超松弛法3.6线性方程组的迭代解法13例1设有方程组15831110225311621043243214321321xxxxxxxxxxxxxx或简记Ax=b解精确解x*=(1,2,-1,1)T。首先将Ax=b转化为等价方程组)315(81)211(101)325(111)26(10132442134312321xxxxxxxxxxxxxx或写为x=Bx+f3.6线性方程组的迭代解法（续）14迭代公式：初始向量x(0)=(0,0,0,0)T),2,1,0(,)315(81)211(101)325(111)26(101)(3)(2)1(4)(4)(2)(1)1(3)(4)(3)(1)1(2)(3)(2)1(1kxxxxxxxxxxxxxxkkkkkkkkkkkkkk计算结果如下表：3.6线性方程组的迭代解法（续）15x(0)=(0.0000,0.0000,0.0000,0.0000)Tx(1)=(0.6000,2.2727,-1.1000,1.8750)T…x(8)=(1.0006,1.9987,-0.9990,0.9989)Tx(9)=(0.9997,2.0004,-1.0004,1.0006)Tx(10)=(1.0001,1.9998,-0.9998,0.9998)T且有误差:||x*-x(10)||∞≈0.0002从此例看出，由迭代法产生的向量序列{x(k)}逐次逼近方程组的精确解。但是，并不是对任何一个线性方程组，由迭代法产生的向量序列{x(k)}都收敛。3.6线性方程组的迭代解法（续）解线性方程组的迭代法的基本思想与求非线性方程的迭代法的基本思想是类似的。163.6线性方程组的迭代解法（续）3.6.1迭代格式的一般形式fBxxbAx变形成等价的同解线性方程组然后任取一个初始向量x(0)∈Rn作为近似解，由公式(1)()(0,1,2,)kkxBxfk构造向量序列{x(k)}，如果向量序列{x(k)}满足173.6.1迭代格式的一般形式（续）()*limkkxx------迭代法收敛方程组的解否则，称此迭代法发散。(1)()(0,1,2,)kkxBxfk迭代格式迭代矩阵第k次迭代近似解()()*kkexx-------第k次迭代误差用迭代法解方程组(Ax=b)的关键是：183.6.1迭代格式的一般形式（续）(1)如何构造迭代格式1.雅可比(Jacobi)迭代法2.高斯-塞德尔（Gauss-Seidel)迭代法3.逐次超松弛法(1)()(0,1,2,)kkxBxfk(2)由迭代格式产生的向量序列{x(k)}的收敛条件是什么？193.6.2雅可比迭代法设线性方程组Ax=b的一般形式为11212111bxaxaxann22222121bxaxaxannnnnnnnbxaxaxa22110(1,2,,)iiain(1)设ix则可从上式解出,111221331111(]nnxbaxaxaxa雅可比（Jacobi)迭代法的步骤为：20111221331111()nnxbaxaxaxa222112332221()nnxbaxaxaxa1122,111()nnnnnnnnnxbaxaxaxa11,11,111()iiiiiiiiiinniixbaxaxaxaxa3.6.2雅可比迭代法（续）21（2）写成迭代格式(1)()()()111221331111()kkkknnxbaxaxaxa(1)()()()222112332221()kkkknnxbaxaxaxa(1)()()()1122,111()kkkknnnnnnnnnxbaxaxaxa(1)()()()()11,11,111()kkkkkiiiiiiiiiinniixbaxaxaxaxa3.6.2雅可比迭代法（续）22（3）取定初始向量(1)()()()()11,11,111()kkkkkiiiiiiiiinniiixaxaxaxaxba(1,2,,)in(0)(0)(0)(0)(0)12(,,,,,)Tinxxxxx令0,1,2,k根据迭代公式（3.23)可得向量序列{x(k)}。3.6.2雅可比迭代法（续）()()()()12(,,,)kkkkTnxxxx233.6.2雅可比迭代法（续）类似于非线性方程的迭代法，对于事先给定的精度要求ε，当(1)()kkxx就可以得到方程组的近似解*(1)kxx24雅可比迭代法的矩阵形式，3.6.2雅可比迭代法（续）2131321,11,21,3123,100000nnnnnnnnaaaLaaaaaaa112233nnaaDaa12131232,10000nnnnaaaaaUaALDU253.6.2雅可比迭代法（续）则ALDU线性方程组(3.18)Ax=b可表示为()LDUxb()DxbLUx0(1,2,,)det(D)0iiain1[()]xDbLUx相应的迭代格式为(1)1()[()]kkxDbLUx263.6.2雅可比迭代法（续）所以Jacobi迭代格式的矩阵形式(1)()kkJxJxf(1)1()[()]kkxDbLUx11()JJDLUfDb-----Jacobi迭代矩阵27例.用Jacobi迭代法求解方程组123123123202324812231530xxxxxxxxx解:按迭代公式，得雅可比迭代格式(1)()()123(1)()()213(1)()()312(2423)/20(12)/8(3023)/15kkkkkkkkkxxxxxxxxx取(0)(0)(0)(0)123(,,)(0,0,0)TTxxxx令0,1,2,k3.6.2雅可比迭代法（续）28(1)[1.2,1.5,2]Tx(1)(0)2xx(2)(1)0.45xx(2)[0.75,1.1,2.14]Tx(3)[0.769,1.138,2.12]Tx(4)[0.768125,1.138875,2.125216667]Tx(5)[0.76733,1.13832292,2.12535833]Tx(12)(13)[0.767353807,1.138409760,2.125368111]Txx3.6.2雅可比迭代法（续）29在计算机上，使用Jacobi迭代法求解方程组时，可用x，y分别表示x(k)和x(k+1)当()(1)maxkkiiixx时，停止迭代，3.6.2雅可比迭代法（续）30（4）对i=1~n令xi←yi（5）对D≥ε则转到(2)（6）输出xi（i=1~n）并停止计算（1）对i=1~n令xi←0（2）D←0（3）对i=1~n做令yi=bi对j=1~n但j≠i令yi←yi-aijxj令yi←yi/aii若|xi-yi|D则令D←|xi-yi|计算步骤3.6.2雅可比迭代法（续）31分析Jacobi迭代法的迭代过程已经求出之前发现在)1(1)1(2)1(1)1(,,,,kikkkixxxx进行迭代仍用时但当求)(1)(2)(1)1(,,,,kikkkixxxx(1)(1)(1)(1)121,,,,?kkkkiixxxx能否求时利用进行迭代呢(1)()()()11221331111()/kkkknnxaxaxaxba(1)()(