数值分析9(迭代法收敛性证明)

1/34迭代法收敛性条件迭代误差估计定理《数值分析》923:292/34总结:矩阵范数算子范数算子范数矩阵1范数,矩阵无穷范数,矩阵2范数3/34例4设||.||为Rn×n上任意一种矩阵范数,则对任意的A∈Rn×n,有证明:()max||,0iAxAxx设是模最大特征值对应特征向量满足。Txx则不是零矩阵。.,对于任意矩阵范数由范数定义有()TTTTAxxxxAxxAxx()AA。例5设||.||为Rn×n上任意一种矩阵范数,则对1,.=1II有特别的为算子范数则。4/34AX=b(M–N)X=bMX=NX+b记(k)=X(k)–X*(k=0,1,2,···)则有(k+1)=B(k)(k=0,1,2,···)迭代格式:X(k+1)=BX(k)+f(B=M-1N,f=M-1b)X(k+1)–X*=B(X(k)–X*)设方程组的精确解为X*,则有X*=BX*+f23:29||(k+1)||=||B(k)||≤||B||.||(k)||(k=0,1,2,···)5/3423:2911()*()()||||kkkLLxxxx0()()fxxx11(),fxAxbxMNxMbAMN其中迭代法构造收敛条件中止准则**(0)***(),()|((),)|1)(NxxxxxxxNx为的不动点在的连续且则迭代法对任意某邻域收敛6/34引理1112,lim0()1,()=max||,,,nnkkkknnBRBBBBB矩阵则的充分必要条件是其中为矩阵的谱半径是矩阵的特征值。23:29参考:P.837/34引理2()1,BIB若则是非奇异的。21:()(),kkIBIBBBIB思路-10()=jjIBB故。23:29引理311,1()1BIBB若则对于矩阵算子范数满足111:()()()()IBIBIIBBIBI思路111()()()IBIBIBIBIB8/34证:必要性,设迭代法产生的序列{X(k)}收敛,记X*是该序列的极限点,则X*=BX*+f。定理4.1对任意的f和任意的初始向量X(0)迭代法X(k+1)=BX(k)+f收敛的充分必要条件是(1)*()*2(1)*1(0)*()()()kkkkXXBXXBXXBXX()1B由X(0)的任意性知*=lim()1kkBBOB。23:299/34充分性(1)()(1)1(0)0()kkkkkjjXBXfBBXffBXBf()1lim()kkXIBf说明迭代法产生的序列收敛。()1lim0kkBB21()(),kkIBIBBBIB则-10()=jjIBB。23:2910/34谱半径小于1是迭代收敛的充要条件,但它不易计算,所以在实际使用中通常并不好用。(),:AA由性质我们有如下推论推论4.1若||B||1,则对任意的f和任意的初始向量X(0)迭代法X(k+1)=BX(k)+f收敛。23:29:()1BB思路11/34定理4.2设X*为方程组AX=b的解若||B||1,则对迭代格式X(k+1)=BX(k)+f有()(1)()1||*||||||1||||kkkXXXXB(1)||||||||1||||||*||)0()1()(XXBBXXkk(2)证||X(k+1)–X*||≤||B(X(k)–X*)||≤||B||||X(k)–X*||X(k+1)–X*=B(X(k)–X*)23:2912/34||X(k)–X*||=||(X(k)–X(k+1))+(X(k+1)–X*)||||||||||1||||||*||)1()()(kkkXXBBXX||||||||11||*||)()1()(kkkXXBXX≤||X(k)–X(k+1)||+||X(k+1)–X*||≤||X(k)–X(k+1)||+||B||||X(k)–X*||23:2913/3411()()()||||||||||*||||||kkkXXXXBB23:2911()*()()||||kkkLLxxxx()xx11,xMNxMbAMN其中迭代法构造收敛条件(局部vs全局)中止准则****(0)*()()|()|1,(,())NxxxNxxxxx为的不动点在的连续且则迭代法对任意某邻域收敛(0)X()1||||1fBB对任意的和迭代法收敛的充分必要条件是和充分条件是任意的初始向量统一的不动点框架14/34定义4.1A=(aij)n×n,如果则称A为严格对角占优阵。nijjijiiaa1||||23:29性质2A是严格对角占优矩阵,则D-L和D-U是严格对角占优矩阵。性质1A是严格对角占优矩阵,则。0||iia记A=D-L-U性质3A是严格对角占优矩阵,则当时则有和是严格对角占优矩阵。1DLU1DLU1||严格对角占优矩阵15/34定理4.3若Ax=b的系数矩阵A是严格对角占优矩阵,则Jacobi迭代和Gauss-Seidel迭代收敛。证:由于矩阵A严格对角占优1||||11nijjijiiaanijjijiiaa1||||0///0///0)(21222222111111121nnnnnnnnJaaaaaaaaaaaaADDB23:2916/341||||11nijjijiiaa所以1111||||max||||nJijinjiijiBaa故Jacobi迭代矩阵BJ=D-1(D–A)第i行绝对值求和),2,1(ni故Jacobi迭代X(k+1)=BJX(k)+f收敛。23:29()1JJBB推论A是严格对角占优矩阵,则A非奇异。1111()1=()IDAIDADAIIDA非奇异。17/341()(())1BDLU。1,||1所以存在模大于的特征值不妨设Gauss-Seidel迭代矩阵为BGS=(D-L)-1U。由于A对角占优所以矩阵也是对角占优的,则矩阵一定非奇异,矛盾。111110=det()det(())=det(()())=det(())det()nnIBIDLUDLDLUDLDLU1()DLU注释:det()det()nkAkA()det()fIBB称为的特征多项式。考虑反证法18/34新证:1(),DLUx设为的一个特征值为相应特征向量。=1,1,1mxxx选择的使得存在=所有其它分量都不大于。1()()DLUxxLUxDx特征值意味着或。,,11,11,11,1,-1,1,||=||=|+++++|||++||+||++||=||||mmmmmmmmmmmmmnnmmmmmmnmjjmmmaaxaxaxaxaxaaaaaa19/34定理4.4方程组Ax=b中,若A是实对称正定矩阵,则Gauss-Seidel迭法收敛。证明:由A=D–L–LTBGS=(D–L)-1LTA正定,故p=xTDx0,记xTLTx=a,则有xTAx=xT(D–L–LT)x=p–a–a=p–2a0xLDxxLxTTT)(xxLLDT1)(xLDxLT)(设为BGS的任一特征值,x为其特征向量,则23:2920/341)2(2222222aappaapapaapaxLDxxLxTTT)(所以迭代矩阵BGS的谱半径(BGS)1,从而当A是实对称正定矩阵时,Gauss-Seidel迭代法收敛。23:29定理方程组Ax=b中,若A是实对称正定矩阵,则Jacobi迭法收敛？(反例)21/34(1)()()0;JGSBB定理4.5设BJ元素均非负,则下列关系有且只有一个成立:参考文献:P.Stein,R.L.Rosenberg,Onthesolutionoflinearsimultaneousequationsbyiteration,J.LondonMath.Soc.(2)0()()1;GSJBB(3)()()1;JGSBB(4)1()()JGSBB。23:2922/3411()()()||||||||||*||||||kkkXXXXBB23:2911()*()()||||kkkLLxxxx()xx11,xMNxMbAMN其中迭代法构造收敛条件(局部vs全局)中止准则****(0)*()()|()|1,(,())NxxxNxxxxx为的不动点在的连续且则迭代法对任意某邻域收敛(0)X()1||||1fBB对任意的和迭代法收敛的充分必要条件是和充分条件是任意的初始向量统一的不动点框架23/34直接法vs迭代法基于高斯消元法的直接方法提供了有限步内就可以得到解的方法。23:29寻求迭代方法的理由是什么呢？十阶百阶万阶百万阶亿阶小不大较大大超大24/34迭代法优势1:直接法运行一个完整LU分解才能得到解,迭代法从初始解开始每步对其加工改善使其更加精确。问题是在用户容忍的范围内需要多少步才能得到收敛性？23:29注释:运行一个完整LU分解花费O(n3)阶运算,一般地,迭代法每次迭代花费O(n2)阶运算,即每次迭代仅需要完整LU分解花费的一部分。25/34迭代法优势2:求解稀疏方程组是使用迭代法的主要理由。23:29注释:系数矩阵稀疏度为n,则求解稀疏方程组迭代法每步迭代花费O(n)阶运算。求解特殊结构方程组(如Toeplitz)迭代法每步迭代花费O(nlogn)阶运算。26/34(),01(0)(1)0ufxxuuPoisson方程:令h=1/(n+1),xi=ih(i=0,1,···,n+1)记ui=u(xi),(i=0,1,···,n+1)迭代计算格式:1(1)()()21(())/2iikkkiiuuuhfx121)2(iiiihfxuuu差分格式:22()()()()hfahfahfafa22()()()()hfahfahfafa22()2()()()()fahfafahfaOhh1(1)(1)()21(())/2iikkkiiuuuhfx27/342112112An=10000;e=ones(n,1);A=spdiags([e-2*ee],-1:1,n,n),spy(A)28/34HB矩阵稀疏模式来源TheoriginalHarwell-Boeingcollection来源:TheUniversityofFloridaSparseMatrixCollection29/34FreeFieldTechnologies矩阵稀疏模式来源3Dvibro-acousticproblem,aircraftenginenacelle30/34vanHeukelum矩阵稀疏模式来源DNAelectrophoresis31/34garon2矩阵稀疏模式2DFEM,Navier-Stokes,CFD32/34n=10000;e=ones(n,1);n2=n/2;a=spdiags([-e3*e-e],-1:1,n,n);c=spdiags([e/2],0,n,n);c=fliplr(c);a=a+c;a(n2+1,n2)=-1;a(n2,n2+1)=-1;b=zeros(n,1);b(1)=2.5;b(n)=2.5;b(2:n-1)=1.5;b(n2