数值分析迭代法收敛性证明资料实用教案

1、总结总结(zngji): 矩阵矩阵(j (j zhn)zhn)范数范数算子算子(sun (sun z)z)范数范数 算子范数 矩阵1范数, 矩阵无穷范数, 矩阵2范数第1页/共34页第一页，共34页。例例4 设设|.|为为Rnn 上任意一种上任意一种(y zhn)矩阵矩阵范数范数, 则对任意的则对任意的A Rnn , 有有证明证明(zhngmng): ( )max|,0iAxAxx 设设是是模模最最大大特特征征值值对对应应特特征征向向量量满满足足。Txx则则不不 是是 零零 矩矩 阵阵 。. ,对对于于任任意意矩矩阵阵范范数数由由范范数数定定义义有有( )TTTTAxxxxAxxA xx()A

2、A 。例例5 设设|.|为为Rnn 上任意上任意(rny)一种矩阵范数一种矩阵范数, 则对则对1,.=1II 有有特特别别的的为为算算子子范范数数则则。第2页/共34页第二页，共34页。A X = b (MN )X = b M X = N X + b记记 (k) = X(k) X* ( k = 0, 1, 2, )则有 (k+1) = B (k) ( k = 0, 1, 2, )迭代(di di)格式: X(k+1) = B X(k) + f ( B = M-1N, f=M-1b ) X(k+1) X*= B(X(k) X*) 设方程组的精确设方程组的精确(jngqu)解为解为 X*,则有则有

3、X* = B X* + f 1:51 |(k+1) |= |B(k) | |B|.|(k) | ( k = 0, 1, 2, )第3页/共34页第三页，共34页。1:5111( )*( )()|kkkLLxxxx 0( )( )f xxx 11( ),f xAxbxMNxM bAMN 其其中中迭代法构造迭代法构造(guzo)收敛收敛(shulin)条件条件中止中止(zhngzh)准则准则*(0)*( ), ()|( ),)|1) (NxxxxxxxN x 为为的的不不动动点点在在 的的连连续续且且则则迭迭代代法法对对任任意意某某邻邻域域收收敛敛第4页/共34页第四页，共34页。引理引理1 11

4、2,lim0( )1,( )=max|,n nkkkk nnBRBBBBB 矩矩阵阵则则的的充充分分必必要要条条件件是是其其中中为为矩矩阵阵 的的谱谱半半径径是是矩矩阵阵 的的特特征征值值。1:51参考参考(cnko): P. (cnko): P. 8383第5页/共34页第五页，共34页。引理引理2 ( )1,BIB 若若则则是是非非奇奇异异的的。21:()(),kkIB IBBBIB 思思路路-10() =jjIBB 故故。1:51引理引理3 11,1()1BIBB 若若则则对对于于矩矩阵阵算算子子范范数数满满足足 111:()()()()IB IBIIBB IBI 思思路路111()()

5、()IBIB IBIBIB第6页/共34页第六页，共34页。证: 必要性, 设迭代法产生的序列(xli)X(k)收敛, 记X*是该序列(xli)的极限点, 则X* =B X*+f。 定理4.1 对任意的f和任意的初始向量X(0)迭代法 X(k+1) =B X(k) +f 收敛的充分(chngfn)必要条件是(1)*( )*2(1)*1(0)*()()()kkkkXXB XXBXXBXX ( )1B 由X(0) 的任意性知 *=lim( )1kkBBOB 。1:51第7页/共34页第七页，共34页。充分性 (1)( )(1)1(0)0()kkkkkjjXBXfB BXffBXB f ( )1li

6、m()kkXIBf 说说明明迭迭代代法法产产生生的的序序列列收收敛敛。( )1lim0kkBB 21()(),kkIB IBBBIB 则则-10() =jjIBB 。1:51第8页/共34页第八页，共34页。 谱半径小于谱半径小于1是迭代收敛的充要条件是迭代收敛的充要条件,但它不易但它不易计算计算,所以在实际所以在实际(shj)使用中通常并不好用。使用中通常并不好用。(),:AA 由由性性质质我我们们有有如如下下推推论论推论4.1 若|B|1,则对任意的f和任意的初始向量(xingling)X(0)迭代法 X(k+1) =B X(k) +f 收敛。1:51:( )1BB 思思路路第9页/共34

7、页第九页，共34页。定理(dngl)4.2 设X*为方程组 AX=b 的解若|B|0, 记记 xTLTx = a , 则有则有xTAx=xT(D L LT)x=p a a =p 2a 0 xLDxxLxTTT)( xxLLDT 1)(xLDxLT)( 设设 为为BGS的任一特征值的任一特征值, x 为其特征向量为其特征向量,则则 1:51第18页/共34页第十八页，共34页。1)2(2222222 aappaapapa apaxLDxxLxTTT )( 所以迭代矩阵所以迭代矩阵 BGS 的谱半径的谱半径 (BGS) 1,从而当从而当A 是实对称正定矩阵是实对称正定矩阵(j zhn)时时, Ga

8、uss-Seidel迭代法迭代法收敛。收敛。1:51定理定理 方程组方程组 Ax=b 中中, 若若 A 是实对称是实对称(duchn)正定矩阵正定矩阵,则则Jacobi迭法收敛？迭法收敛？(反例反例)第19页/共34页第十九页，共34页。(1) ()()0;JGSBB 定理定理4.5 设设BJ元素元素(yun s)均非负均非负, 则下列关则下列关系有且只有一个成立系有且只有一个成立:参考文献参考文献: : P. Stein, R.L. Rosenberg, On the solution of linear simultaneous equations by iteration, J. Lon

9、don Math. Soc.(2) 0 ()()1;GSJBB (3) ()()1;JGSBB (4) 1 ()()JGSBB 。1:51第20页/共34页第二十页，共34页。11( )( )()|*|kkkXXXXBB 1:5111( )*( )()|kkkLLxxxx ( )xx 11,xMNxM bAMN其其中中迭代法构造迭代法构造(guzo)收敛条件收敛条件(tiojin)(局部局部vs全局全局)中止中止(zhngzh)准则准则*(0)*()( )|()| 1,(, ()N xxxN xxxxx 为为的的不不动动点点在在的的连连续续且且则则迭迭代代法法对对任任意意某某邻邻域域收收敛敛(

10、0)X( )1| | |1fBB 对对任任意意的的 和和迭迭代代法法收收敛敛的的充充分分必必要要条条件件是是和和充充分分条条件件是是任任意意的的初初始始向向量量统一的不动点框架统一的不动点框架第21页/共34页第二十一页，共34页。直接(zhji)法vs迭代法 基于基于(jy)高斯消元法的直接方法提高斯消元法的直接方法提供了有限步内就可以得到解的方法。供了有限步内就可以得到解的方法。1:51 寻求迭代方法的理由寻求迭代方法的理由(lyu)是什么呢？是什么呢？十阶十阶 百阶百阶 万阶万阶 百万阶百万阶 亿阶亿阶 小小 不大不大 较大较大 大大 超大超大第22页/共34页第二十二页，共34页。迭代

11、法优势(yush)1: 直接法运行一个完整LU分解才能得到解,迭代法从初始(ch sh)解开始每步对其加工改善使其更加精确。问题是在用户容忍的范围内需要多少步才能得到收敛性？1:51注释:运行一个完整LU分解花费O(n3)阶运算,一般地,迭代(di di)法每次迭代(di di)花费O(n2)阶运算, 即每次迭代(di di)仅需要完整LU分解花费的一部分。第23页/共34页第二十三页，共34页。迭代法优势迭代法优势(yush)2: 求解求解(qi ji)稀疏方程组是使用迭代法的稀疏方程组是使用迭代法的主要理由。主要理由。1:51注释:系数矩阵稀疏度为n, 则求解稀疏方程组迭代法每步迭代花费O

12、(n)阶运算(yn sun)。求解特殊结构方程组(如Toeplitz)迭代法每步迭代花费O(nlogn)阶运算(yn sun)。第24页/共34页第二十四页，共34页。( ),01(0)(1)0uf xxuu Poisson方程方程(fngchng):令令 h = 1/(n+1) , xi= ih ( i = 0,1, , n+1 )记记 ui= u(xi ), (i = 0,1, , n+1)迭代迭代(di di)计算格计算格式式:1(1)( )( )21()/ 2iikkkiiuuuh f x 121)2(iiiih f xuuu 差分差分(ch fn)格式格式:22()( )( )( )

13、hf ahf ahfafa22()( )( )( )hf ahf ahfafa22()2 ( )()( )()f ahf af ahfaO hh 1(1)(1)( )21()/ 2iikkkiiuuuh f x 第25页/共34页第二十五页，共34页。2112112A n=10000;e=ones(n,1);A = spdiags(e -2*e e, -1:1, n, n), spy(A)第26页/共34页第二十六页，共34页。 HB矩阵矩阵(j zhn)稀疏模式稀疏模式来源来源 The original Harwell-Boeing collection来源来源(liyun):The Uni

14、versity of Florida Sparse Matrix (liyun):The University of Florida Sparse Matrix CollectionCollection第27页/共34页第二十七页，共34页。 FreeFieldTechnologies矩阵稀疏矩阵稀疏(xsh)模式模式来源来源3D vibro-acoustic problem, aircraft engine nacelle第28页/共34页第二十八页，共34页。 vanHeukelum矩阵稀疏模式矩阵稀疏模式(msh) 来源来源DNA electrophoresis第29页/共34页第二十九

15、页，共34页。 garon2矩阵矩阵(j zhn)稀疏模式稀疏模式 2D FEM, Navier-Stokes, CFD第30页/共34页第三十页，共34页。 n=10000;e = ones(n,1); n2=n/2;a = spdiags(-e 3*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:n2+1)=1;% Jacobi Method (Iterative

16、 Method)ticd=diag(a); % extract diagonal of ar=a-diag(d); % r is the remainderx=zeros(n,1); % initialize vector xfor j=1:50 % loop for Jacobi iterationx = (b-r*x)./d;endt1=toctic,x=full(a)b,t2=toc % Back Slash (Direct Method)Demo1第31页/共34页第三十一页，共34页。 help sparfunMatlab与大数据处理与大数据处理Elementary sparse matrices (例如(lr)spdiags)Full to sparse conversion (例如(lr)sparse)Wor