数值分析迭代法收敛性证明资料.pptx
总结总结:矩阵范数矩阵范数算子范数算子范数算子范数 矩阵1范数,矩阵无穷范数,矩阵2范数第1页/共34页例例4 设设|.|为为Rnn 上任意一种矩阵范数上任意一种矩阵范数,则对则对任意的任意的A Rnn,有有证明证明:例例5 设设|.|为为Rnn 上任意一种矩阵范数上任意一种矩阵范数,则对则对第2页/共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,)迭代格式:X(k+1)=B X(k)+f (B=M-1N,f=M-1b)X(k+1)X*=B(X(k)X*)设方程组的精确解设方程组的精确解为为 X*,则有则有X*=B X*+f 23:33|(k+1)|=|B(k)|B|.|(k)|(k=0,1,2,)第3页/共34页23:33迭代法构造迭代法构造收敛条件收敛条件中止准则中止准则第4页/共34页引理引理1 23:33参考参考:P.83第5页/共34页引理引理2 23:33引理引理3 第6页/共34页证:必要性,设迭代法产生的序列X(k)收敛,记X*是该序列的极限点,则X*=B X*+f。定理4.1 对任意的f和任意的初始向量X(0)迭代法 X(k+1)=B X(k)+f 收敛的充分必要条件是由X(0)的任意性知 23:33第7页/共34页充分性 23:33第8页/共34页 谱半径小于谱半径小于1是迭代收敛的充要条件是迭代收敛的充要条件,但它不但它不易计算易计算,所以在实际使用中通常并不好用所以在实际使用中通常并不好用。推论4.1 若|B|1,则对任意的f和任意的初始向量X(0)迭代法 X(k+1)=B X(k)+f 收敛。23:33第9页/共34页定理4.2 设X*为方程组 AX=b 的解若|B|0,记记 xTLTx=a,则有则有xTAx=xT(D L LT)x=p a a=p 2a 0设设 为为BGS的任一特征值的任一特征值,x 为其特征向量为其特征向量,则则23:33第18页/共34页所以迭代矩阵所以迭代矩阵 BGS 的谱半径的谱半径 (BGS)1,从而当从而当A 是实对称正定矩阵时是实对称正定矩阵时,Gauss-Seidel迭代法收敛。迭代法收敛。23:33定理定理 方程组方程组 Ax=b 中中,若若 A 是实对称正定矩阵是实对称正定矩阵,则则Jacobi迭法收敛？迭法收敛？(反例反例)第19页/共34页定理定理4.5 设设BJ元素均非负元素均非负,则下列关系有且则下列关系有且只有一个成立只有一个成立:参考文献参考文献:P.Stein,R.L.Rosenberg,On the solution of linear simultaneous equations by iteration,J.London Math.Soc.23:33第20页/共34页23:33迭代法构造迭代法构造收敛条件收敛条件(局部局部vs全局全局)中止准则中止准则统一的不动点框架统一的不动点框架第21页/共34页直接法vs迭代法 基于高斯消元法的直接方法提供了基于高斯消元法的直接方法提供了有限步有限步内内就可以得到解的方法。就可以得到解的方法。23:33 寻求迭代方法的理由是什么呢？寻求迭代方法的理由是什么呢？十阶十阶 百阶百阶 万阶万阶 百万阶百万阶 亿阶亿阶 小小 不大不大 较大较大 大大 超大超大第22页/共34页迭代法优势1:直接法运行一个完整LU分解才能得到解,迭代法从初始解开始每步对其加工改善使其更加精确。问题是在用户容忍的范围内需要多少步才能得到收敛性？23:33注释:运行一个完整LU分解花费O(n3)阶运算,一般地,迭代法每次迭代花费O(n2)阶运算,即每次迭代仅需要完整LU分解花费的一部分。第23页/共34页迭代法优势迭代法优势2:求解稀疏方程组是使用迭代法的主要理由。求解稀疏方程组是使用迭代法的主要理由。23:33注释:系数矩阵稀疏度为n,则求解稀疏方程组迭代法每步迭代花费O(n)阶运算。求解特殊结构方程组(如Toeplitz)迭代法每步迭代花费O(nlogn)阶运算。第24页/共34页Poisson方程方程:令令 h=1/(n+1),xi=ih(i=0,1,n+1)记记 ui=u(xi),(i =0,1,n+1)迭代计算格式迭代计算格式:差分格式差分格式:第25页/共34页n=10000;e=ones(n,1);A=spdiags(e-2*e e,-1:1,n,n),spy(A)第26页/共34页 HB矩阵稀疏模式矩阵稀疏模式来源来源 The original Harwell-Boeing collection来源来源:The University of Florida Sparse Matrix Collection第27页/共34页 FreeFieldTechnologies矩阵稀疏模式矩阵稀疏模式来源来源3D vibro-acoustic problem,aircraft engine nacelle第28页/共34页 vanHeukelum矩阵稀疏模式矩阵稀疏模式 来源来源DNA electrophoresis第29页/共34页 garon2矩阵稀疏模式矩阵稀疏模式 2D FEM,Navier-Stokes,CFD第30页/共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 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页 help sparfunMatlab与大数据处理与大数据处理Elementary sparse matrices(例如spdiags)Full to sparse conversion(例如sparse)Working with sparse matrice(例如nnz,spy)Linear algebra(例如svds,ilu,eigs)Linear equations(iterative methods)(例如pcg)23:33第32页/共34页 The Curse of Dimensionality23:33The Blessing of Sparsity第33页/共34页23:33感谢您的观看。第34页/共34页
