科學計算方法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全局),中止準則,統(tǒng)一的不動點框架,是否可以不寫出迭代矩陣就直接判斷迭代法的收斂？,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為嚴格對角占優(yōu)陣。,嚴格對角占優(yōu)矩陣,定理 若Ax=b的系數(shù)矩陣 A 是嚴格對角占優(yōu)矩陣,則Jacobi迭代收斂。,定理 若Ax=b的系數(shù)矩陣 A 是嚴格對角占優(yōu)矩陣,則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,試試實現(xiàn)Jacobi和Gauss-Seidel方法。你有其它想法嗎？并同樣精度情況下的比較各種方法的速度。,標準: 1. 代碼美 2. 文檔美,作業(yè) 3,分享有趣的線性方程組？,標準: 文檔(wor