《数值分析9(迭代法收敛性证明)课件》由会员分享，可在线阅读，更多相关《数值分析9(迭代法收敛性证明)课件（34页珍藏版）》请在金锄头文库上搜索。
1、2020/10/15,迭代法收敛性条件 迭代误差估计定理,数值分析 9, ,总结:,矩阵范数,算子范数,算子范数 矩阵1范数, 矩阵无穷范数, 矩阵2范数,例4 设|.|为Rnn 上任意一种矩阵范数, 则对任意的A Rnn , 有,证明:,例5 设|.|为Rnn 上任意一种矩阵范数, 则对,2020/10/15,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-1
2、b ),X(k+1) X*= B(X(k) X*),设方程组的精确解为 X*,则有,X* = B X* + f ,|(k+1) |= |B(k) | |B|.|(k) | ( k = 0, 1, 2, ),2020/10/15,迭代法构造,收敛条件,中止准则,2020/10/15,引理1,参考: P. 83,2020/10/15,引理2,引理3,2020/10/15,证: 必要性, 设迭代法产生的序列X(k)收敛, 记 X*是该序列的极限点, 则X* =B X*+f。,定理4.1 对任意的f和任意的初始向量X(0)迭代法 X(k+1) =B X(k) +f 收敛的充分必要条件是,由X(0) 的
3、任意性知,2020/10/15,充分性,2020/10/15,谱半径小于1是迭代收敛的充要条件,但它不易计算,所以在实际使用中通常并不好用。,推论4.1 若|B|1,则对任意的f和任意的初始向量X(0)迭代法 X(k+1) =B X(k) +f 收敛。,2020/10/15,定理4.2 设X*为方程组 AX=b 的解若|B|1,则对迭代格式 X(k+1) = B X(k) + f 有,(1),(2),证,| X(k+1) X* | = |B(X(k) X*) | |B| | X(k) X* |,2020/10/15,|X(k) X* |= | (X(k) X(k+1) ) + (X(k+1)
4、X* ) |, |X(k) X(k+1)| + |X(k+1) X*| |X(k) X(k+1)| +|B| |X(k) X*|,2020/10/15,迭代法构造,收敛条件(局部vs全局),中止准则,统一的不动点框架,2020/10/15,定义4.1 A=(aij)nn, 如果 则称A为 严格对角占优阵。,性质2 A 是严格对角占优矩阵, 则D-L和D-U是严格对角占优矩阵。,性质1 A 是严格对角占优矩阵, 则 。,记 A=D-L-U,性质3 A 是严格对角占优矩阵, 则当 时则 有 和 是严格对角占优矩阵。,严格对角占优矩阵,2020/10/15,定理4.3 若Ax=b的系数矩阵 A 是严
5、格对角占优矩阵,则Jacobi迭代和Gauss-Seidel迭代收敛。,证: 由于矩阵 A 严格对角占优,2020/10/15,所以,故Jacobi迭代矩阵BJ = D-1(D A) 第 i 行绝对值求和,故Jacobi迭代 X(k+1) =BJ X(k) + f 收敛。,推论 A 是严格对角占优矩阵, 则A非奇异。,Gauss-Seidel迭代矩阵为BGS = (D-L)-1U。,由于A对角占优所以矩阵 也是对角占优的,则矩阵一定非奇异,矛盾。,注释:,考虑反证法,新证:,2020/10/15,定理4.4 方程组 Ax=b 中, 若 A 是实对称正定矩阵,则Gauss-Seidel迭法收敛。
6、,证明: 由 A = D L LT BGS = (D L)-1LT,A 正定,故 p = xTDx0, 记 xTLTx = a , 则有,xTAx=xT(D L LT)x=p a a =p 2a 0,设 为BGS的任一特征值, x 为其特征向量,则,2020/10/15,所以迭代矩阵 BGS 的谱半径 (BGS) 1,从而当A,是实对称正定矩阵时, Gauss-Seidel迭代法收敛。,定理 方程组 Ax=b 中, 若 A 是实对称正定矩阵,则Jacobi迭法收敛？(反例),2020/10/15,定理4.5 设BJ元素均非负, 则下列关系有且只有一个成立:,参考文献: P. Stein, R.
7、L. Rosenberg, On the solution of linear simultaneous equations by iteration, J. London Math. Soc.,2020/10/15,迭代法构造,收敛条件(局部vs全局),中止准则,统一的不动点框架,2020/10/15,直接法vs迭代法,基于高斯消元法的直接方法提供了有限步内就可以得到解的方法。,寻求迭代方法的理由是什么呢？,十阶 百阶 万阶 百万阶 亿阶,小 不大 较大 大 超大,2020/10/15,迭代法优势1:,直接法运行一个完整LU分解才能得到解,迭代法从初始解开始每步对其加工改善使其更加精确。问题
8、是在用户容忍的范围内需要多少步才能得到收敛性？,注释:运行一个完整LU分解花费O(n3)阶运算,一般地,迭代法每次迭代花费O(n2)阶运算, 即每次迭代仅需要完整LU分解花费的一部分。,2020/10/15,迭代法优势2:,求解稀疏方程组是使用迭代法的主要理由。,注释:系数矩阵稀疏度为n, 则求解稀疏方程组迭代法每步迭代花费O(n)阶运算。求解特殊结构方程组(如Toeplitz)迭代法每步迭代花费O(nlogn)阶运算。,Poisson方程:,令 h = 1/(n+1) , xi= ih ( i = 0,1, , n+1 ),记 ui= u(xi ), (i = 0,1, , n+1),迭代计
9、算格式:,差分格式:,n=10000;e=ones(n,1); A = spdiags(e -2*e e, -1:1, n, n), spy(A),HB矩阵稀疏模式 来源 The original Harwell-Boeing collection,来源:The University of Florida Sparse Matrix Collection,FreeFieldTechnologies矩阵稀疏模式 来源3D vibro-acoustic problem, aircraft engine nacelle,vanHeukelum矩阵稀疏模式 来源DNA electrophoresis,
10、garon2矩阵稀疏模式 2D FEM, Navier-Stokes, CFD,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) tic d=diag(a); % extract dia
11、gonal of a r=a-diag(d); % r is the remainder x=zeros(n,1); % initialize vector x for j=1:50 % loop for Jacobi iteration x = (b-r*x)./d; end t1=toc tic,x=full(a)b,t2=toc % Back Slash (Direct Method),Demo1,2020/10/15,help sparfun,Matlab与大数据处理,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),2020/10/15,The Curse of Dimensionality,The Blessing of Sparsity,
