计算方法-第六章复习

第六章线性方程组的数值求解6.1高斯顺序消去法6.2高斯列主元消去法6.5追赶法6.6向量与矩阵的范数6.7误差分析6.8迭代法引言bAxbbbxxxaaaaaaaaabxaxaxabxaxaxabxaxaxamnmnmmnnmnmnmmnnnn简记为矩阵形式线性方方程组212121222211121122112222212111212111123231236451221xxxxxxxx用消去法解方程组例11161116()0415041522110411111160415()0026*(1,23):,TAbx回代解、求解解得高斯顺序消去法的条件()11111110(1,2,,)0(1,2,,).0,0(1,2,,)iiiiiiiiiaikADikDaaaDikaa约化的素的充要条件是矩阵的顺序主子式定主即理元()(),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现在我们再用列主元法解例36.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,6A21解：12AA34设，计算的各种范数。--例6nnii1inARi12n,Amax设的特征值为（，，，定义）称（）为谱半径。,.,(1,2,)()nnppARpAA（特征值上界定理）设对于有定理22221()20()(c)=()3()1()()()vvvAcondAAccondAcondAAcondAARcondRAcondARcondA条件数常用性质：、对任何非奇异矩阵，都有1、设为非奇异阵且常数，则、如果为正交矩阵，则；如果为非奇异矩阵，为正交矩阵，则1()(1,2)()1vvvAcondAAAvAAcondAA3、矩阵的条件数设为非奇异阵，称数或为矩阵的条件数。矩阵的条件数是一个十分重要的概念，当的条件数相对的大即时,则线性方程组是“病态”的，当的条件数相对小，则线性方程组是“定义：良态”的。迭代法适用于求解大型稀疏的线性方程组，其基本思想是通过构造迭代格式产生迭代序列，由迭代序列来逼近原方程组的解，因此，要解决的基本问题是：1.如何构造迭代格式2.迭代序列是否收敛一.基本迭代法的格式及收敛性二.几种实用的基本迭代法三.应用实例6.8迭代法一.基本迭代法的格式及收敛性设有线性代数方程组a11x1+a12x2+····+a1nxn=b1a21x1+a22x2+····+a2nxn=b2.....................an1x1+an2x2+····+annxn=bnA=M+NM的逆好求。Ax=b(M+N)x=bMx=-Nx+bx=-M-1Nx+M-1b用矩阵表示：Ax=bA为系数矩阵，非奇异且设aii≠0；b为右端，x为解向量11,,AxbxBxgBMNgMb1(11)(),,(0,1,2,)nkknxBAxbxBxxgBMNgMbkBRgng基其中称为迭代矩本迭代法的阵，是已知迭格式的代维向量，(0)(1)()(),{}kkkxxBxgx给定由迭代格式即可产生迭代序列。()(1)()limkkkkxxxBxgxBxgAxb当对取极限得注：分解A是一个重要问题(1)()()(0)(){}kkkkxBxgxxxxk基本迭代法产生的迭代序列，如果对任取初始向量都有lim，则称此迭代法是收敛的，否则是定义发散的。()()()()1212()()(,,,),(,,,),limlim,(1,2,,)kkkkTnTnnkkiikkxxxxxxxxRxxxxin对则在Rn中，点列的收敛等价于每个分量的收敛。即()()()()()(),(),limlim,(,1,2,,)kkkijijkkijijkkAAaAaAAaaijn同理，的收敛与所选择的范数无关。若则(1)()(0)()()1.kkxBxgxB迭代法收敛的充要条件迭代格式对任意初始向量都收敛的充分必要条件是定理1()(1)()()(1)()(1)(0)1,.113kkkkkkkxBxgBBBxxxxBBxxxxB如果迭代格式的迭代矩阵满足则有如下的误差估计式定理maxmax(3)kkk给出最大迭代次数当迭代终止，给出失败信息。()(1)()()(1)()(1)||||1,2,,.,||(||ma|1)x|kkpkkkkkiiixxpxxpxxxx绝对误差标准。给出容许误差界当时，终止迭代，解取为常取()(1)()||||||||(2)kkkxxx相对误差标准。给出容许误差界迭代终止标准()(1)(0)1kkBxxxxB由误差估计式估计迭代次数()(1)(0)(1)(0)1ln1()lnkkBxxkBxxxxBB估计迭代次数二.几种实用的基本迭代法1、Jacobi迭代法2、Gauss-Seidel迭代法3、超松弛迭代法（SOR)1、Jacobi迭代12121211,12,112nnnnnnnnnaaADaaaUaLaaaa422142114400000022040,100,002004110000ADLUDLU例：1111()(),JJAxbxDLUxDbBxgBDLUgDb于是其中(1)()kkJJacoxxgiBb迭代的矩阵格式Jacobi迭代矩阵11()()()AxbDLUxbDxLUxbxDLUxDb推导其分量形式1111221331122221123322112211nnnnnnnnnnnnnaxaxaxaxbaxaxaxaxbaxaxaxaxb第i个方程除以aii(i=1,2,…,n),得()()AxbDLUxbDxLUxb由得1311211231111111123221221322222222121121nnnnnnnnnnnnnnnnnnnaaabxxxxaaaaaaabxxxxaaaaaaabxxxxaaaa1311211231111111123221221322222222121121nnnnnnnnnnnnnnnnnnnaaabxxxxaaaaaaabxxxxaaaaaaabxxxxaaaaJacobi迭代的分量形式(1)()()()13112121311111111(1)()()()23221213222222222(1)()()()121121kkkknnkkkknnkkkknnnnnnnnnnnnnnnaaabxxxxaaaaaaabxxxxaaaaaaabxxxxaaaa1121111111()12221()()2222222()1200,0nknkkJknnnnnnnnnnaabaaaxabaxaaaBxgxbaaaaa令：，则x(k+1)=BJx(k)+g，这里BJ=D-1(L+U),g=D-1b(1)()1()/,1,2,,nkkiiijjiijjixbaxain(1)()kkJJacoxxgiBb迭代的矩阵格式Jacobi迭代公式（分量形式）给出初始向量x(0),即可得到向量序列：x(1),x(2),…,x(k),…若x(k)→x*,则x*是解。例1：设方程组为3103220241225321321321xxxxxxxxx解：Jacobi迭代格式为试写出其Jacobi分量迭代格式以及相应的迭代矩阵，并求解。10310351)323(10152141)220(415125152)212(51)(2)(1)(2)(1)1(3)(3)(1)(3)(1)1(2)(3)(2)(3)(2)1(1kkkkkkkkkkkkkkkxxxxxxxxxxxxxxx故Jacobi迭代矩阵为2105511042310510JB取x(0)=(0,0,0)t,e=1