数值9(迭代法收敛性证明)解析.ppt

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 diagonal 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 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) * The Curse of Dimensionality * The Blessing of Sparsity */34 */34 迭代法收敛性条件 迭代误差估计定理 《数值分析》 9 ? ? * 总结: 矩阵范数 算子范数 算子范数 矩阵1范数, 矩阵无穷范数, 矩阵2范数 例4 设||.||为Rn×n 上任意一种矩阵范数, 则对任意的A ∈ Rn×n , 有 证明: 例5 设||.||为Rn×n 上任意一种矩阵范数, 则对 A X = b ? (M–N )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 ? * ||?(k+1) ||= ||B?(k) || ≤ ||B||.||?(k) || ( k = 0, 1, 2, ··· ) * 迭代法构造 收敛条件 中止准则 引理1 * 参考: P. 83 引理2 * 引理3 证: 必要性, 设迭代法产生的序列{X(k)}收敛, 记 X*是该序列的极限点, 则X* =B X*+f。 定理4.1 对任意的f和任意的初始向量X(0)迭代法 X(k+1) =B X(k) +f 收敛的充分必要条件是 由X(0) 的任意性知 * 充分性 * 谱半径小于1是迭代收敛的充要条件,但它不易计算,所以在实际使用中通常并不好用。 推论4.1 若||B||1,则对任意的f和任意的初始向量X(0)迭代法 X(k+1) =B X(k) +f 收敛。 * 定理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* || X(k+1)–X* =B(X(k) – X* ) * ||X(k) – X* ||= || (X(k) – X(k+1) ) + (X(k+1) –X* ) || ? ? ≤ ||X(k) – X(k+1)|| + ||X(k+1) –X*|| ≤ ||X(k) – X(k+1)|| +||B|| ||X(k) –X*|| * * 迭代法构造 收敛条件(局部vs全局) 中