科学计算方法9(迭代法收敛性证明)

1、引理1,引子,证: 必要性, 设迭代法产生的序列x(k)收敛, 记 x*是该序列的极限点, 则x* =B x*+f。,定理4.1 对任意的f和任意的初始向量x(0)迭代法 x(k+1) =Bx(k) +f 收敛的充分必要条件是,充分性,谱半径小于1是迭代收敛的充要条件,但它不易计算,所以在实际使用中通常并不好用。,推论4.1 若|B|1,则对任意的f和任意的初始向量x(0)迭代法 x(k+1) =Bx(k) +f 收敛。,定理4.2 设x*为方程组 Ax=b 的解若|B|1,则对迭代格式 x(k+1) = Bx(k) + f 有,(1),(2),证,| x(k+1) x* | = |B(x(k

2、) 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全局),中止准则,统一的不动点框架,是否可以不写出迭代矩阵就直接判断迭代法的收敛？,A=9 -1 -1;-1 10 -1;-1 -1 15; %triu(X,K) is the elements on and above the %K-th diagonal of X L = -tril(A,-1);U =

3、-triu(A,1); %Jacobi迭代矩阵D-1(L+U) Eig1=eig(inv(diag(diag(A)*(-tril(A,-1)- triu(A,1) %GS迭代矩阵(D+L)-1U Eig2=eig(inv(diag(diag(A)+tril(A,-1)*(-triu(A,1),定义 A=(aij)nn, 如果 , 则称A为严格对角占优阵。,严格对角占优矩阵,定理 若Ax=b的系数矩阵 A 是严格对角占优矩阵,则Jacobi迭代收敛。,定理 若Ax=b的系数矩阵 A 是严格对角占优矩阵,则Gauss-Seidel迭代收敛。,定理 方程组 Ax=b 中, 若 A 是对称正定矩阵,则

4、Gauss-Seidel迭法收敛。,定理 方程组 Ax=b 中, 若 A 是实对称正定矩阵,则Jacobi迭法收敛？（反例）,Demo:,n=1000; A=diag(-3*ones(n,1)+diag(ones(n-1,1),1)+ diag(ones(n-1,1),-1); b=ones(n,1); x0=zeros(n,1);nmax=100; tol=10(-5); omega=1.2; x1,his1,iter1=Jacobi(A,b,x0,nmax,tol); x2, his2,iter2=GS(A,b,x0,nmax,tol); figure,plot(his1,r) hold

5、on, plot(his2,g),代码:,n=1000; A=diag(-3*ones(n,1)+diag(ones(n-1,1),1)+ diag(ones(n-1,1),-1); %triu(X,K) is the elements on and above the K-th diagonal of X L = -tril(A,-1);U = -triu(A,1); %Jacobi迭代矩阵D-1(L+U) Eig1=max(abs(eig(inv(diag(diag(A)*(-tril(A,-1)- triu(A,1) %GS迭代矩阵(D+L)-1U Eig2=max(abs(eig(in

6、v(diag(diag(A)+tril(A,-1)*(-triu(A,1),谱半径 0.6667 (Jacobi) 0.4529 (Gauss-Seidel),如何衡量收敛速度呢？,引子,是否可以加速收敛速度呢？,Hilbert矩阵,从更高视野的算法构造,A = M N Ax =b (M N )x = b Mx = Nx + b x(k+1) = (M-1N) x(k) + M-1b,Jacobi迭代法 M = D和N=L+U,A = D L U,Gauss-Seidel迭代 M = D L和N = U,是否还有其它的分裂格式？,从更高视野的算法分析,x(k+1) = (M-1N) x(k) + M-1b,练习 3,试试实现Jacobi和Gauss-Seidel方法。你有其它想法吗？并同样精度情况下的比较各种方法的速度。,标准: 1. 代码美 2. 文档美,作业 3,分享有趣的线性方程组？,标准: 文档(wor