數(shù)值分析迭代法收斂性證明資料實(shí)用教案

1、總結(jié)總結(jié)(zngji): 矩陣矩陣(j (j zhn)zhn)范數(shù)范數(shù)算子算子(sun (sun z)z)范數(shù)范數(shù) 算子范數(shù) 矩陣1范數(shù), 矩陣無(wú)窮范數(shù), 矩陣2范數(shù)第1頁(yè)/共34頁(yè)第一頁(yè)，共34頁(yè)。例例4 設(shè)設(shè)|.|為為Rnn 上任意一種上任意一種(y zhn)矩陣矩陣范數(shù)范數(shù), 則對(duì)任意的則對(duì)任意的A Rnn , 有有證明證明(zhngmng): ( )max|,0iAxAxx 設(shè)設(shè)是是模模最最大大特特征征值值對(duì)對(duì)應(yīng)應(yīng)特特征征向向量量滿(mǎn)滿(mǎn)足足。Txx則則不不 是是 零零 矩矩 陣陣 。. ,對(duì)對(duì)于于任任意意矩矩陣陣范范數(shù)數(shù)由由范范數(shù)數(shù)定定義義有有( )TTTTAxxxxAxxA xx()A

2、A 。例例5 設(shè)設(shè)|.|為為Rnn 上任意上任意(rny)一種矩陣范數(shù)一種矩陣范數(shù), 則對(duì)則對(duì)1,.=1II 有有特特別別的的為為算算子子范范數(shù)數(shù)則則。第2頁(yè)/共34頁(yè)第二頁(yè)，共34頁(yè)。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, )迭代(di di)格式: X(k+1) = B X(k) + f ( B = M-1N, f=M-1b ) X(k+1) X*= B(X(k) X*) 設(shè)方程組的精確設(shè)方程組的精確(jngqu)解為解為 X*,則有則有

3、X* = B X* + f 1:51 |(k+1) |= |B(k) | |B|.|(k) | ( k = 0, 1, 2, )第3頁(yè)/共34頁(yè)第三頁(yè)，共34頁(yè)。1:5111( )*( )()|kkkLLxxxx 0( )( )f xxx 11( ),f xAxbxMNxM bAMN 其其中中迭代法構(gòu)造迭代法構(gòu)造(guzo)收斂收斂(shulin)條件條件中止中止(zhngzh)準(zhǔn)則準(zhǔn)則*(0)*( ), ()|( ),)|1) (NxxxxxxxN x 為為的的不不動(dòng)動(dòng)點(diǎn)點(diǎn)在在 的的連連續(xù)續(xù)且且則則迭迭代代法法對(duì)對(duì)任任意意某某鄰鄰域域收收斂斂第4頁(yè)/共34頁(yè)第四頁(yè)，共34頁(yè)。引理引理1 11

4、2,lim0( )1,( )=max|,n nkkkk nnBRBBBBB 矩矩陣陣則則的的充充分分必必要要條條件件是是其其中中為為矩矩陣陣 的的譜譜半半徑徑是是矩矩陣陣 的的特特征征值值。1:51參考參考(cnko): P. (cnko): P. 8383第5頁(yè)/共34頁(yè)第五頁(yè)，共34頁(yè)。引理引理2 ( )1,BIB 若若則則是是非非奇奇異異的的。21:()(),kkIB IBBBIB 思思路路-10() =jjIBB 故故。1:51引理引理3 11,1()1BIBB 若若則則對(duì)對(duì)于于矩矩陣陣算算子子范范數(shù)數(shù)滿(mǎn)滿(mǎn)足足 111:()()()()IB IBIIBB IBI 思思路路111()()

5、()IBIB IBIBIB第6頁(yè)/共34頁(yè)第六頁(yè)，共34頁(yè)。證: 必要性, 設(shè)迭代法產(chǎn)生的序列(xli)X(k)收斂, 記X*是該序列(xli)的極限點(diǎn), 則X* =B X*+f。 定理4.1 對(duì)任意的f和任意的初始向量X(0)迭代法 X(k+1) =B X(k) +f 收斂的充分(chngfn)必要條件是(1)*( )*2(1)*1(0)*()()()kkkkXXB XXBXXBXX ( )1B 由X(0) 的任意性知 *=lim( )1kkBBOB 。1:51第7頁(yè)/共34頁(yè)第七頁(yè)，共34頁(yè)。充分性 (1)( )(1)1(0)0()kkkkkjjXBXfB BXffBXB f ( )1li

6、m()kkXIBf 說(shuō)說(shuō)明明迭迭代代法法產(chǎn)產(chǎn)生生的的序序列列收收斂斂。( )1lim0kkBB 21()(),kkIB IBBBIB 則則-10() =jjIBB 。1:51第8頁(yè)/共34頁(yè)第八頁(yè)，共34頁(yè)。 譜半徑小于譜半徑小于1是迭代收斂的充要條件是迭代收斂的充要條件,但它不易但它不易計(jì)算計(jì)算,所以在實(shí)際所以在實(shí)際(shj)使用中通常并不好用。使用中通常并不好用。(),:AA 由由性性質(zhì)質(zhì)我我們們有有如如下下推推論論推論4.1 若|B|1,則對(duì)任意的f和任意的初始向量(xingling)X(0)迭代法 X(k+1) =B X(k) +f 收斂。1:51:( )1BB 思思路路第9頁(yè)/共34

7、頁(yè)第九頁(yè)，共34頁(yè)。定理(dngl)4.2 設(shè)X*為方程組 AX=b 的解若|B|0, 記記 xTLTx = a , 則有則有xTAx=xT(D L LT)x=p a a =p 2a 0 xLDxxLxTTT)( xxLLDT 1)(xLDxLT)( 設(shè)設(shè) 為為BGS的任一特征值的任一特征值, x 為其特征向量為其特征向量,則則 1:51第18頁(yè)/共34頁(yè)第十八頁(yè)，共34頁(yè)。1)2(2222222 aappaapapa apaxLDxxLxTTT )( 所以迭代矩陣所以迭代矩陣 BGS 的譜半徑的譜半徑 (BGS) 1,從而當(dāng)從而當(dāng)A 是實(shí)對(duì)稱(chēng)正定矩陣是實(shí)對(duì)稱(chēng)正定矩陣(j zhn)時(shí)時(shí), Ga

8、uss-Seidel迭代法迭代法收斂。收斂。1:51定理定理 方程組方程組 Ax=b 中中, 若若 A 是實(shí)對(duì)稱(chēng)是實(shí)對(duì)稱(chēng)(duchn)正定矩陣正定矩陣,則則Jacobi迭法收斂？迭法收斂？(反例反例)第19頁(yè)/共34頁(yè)第十九頁(yè)，共34頁(yè)。(1) ()()0;JGSBB 定理定理4.5 設(shè)設(shè)BJ元素元素(yun s)均非負(fù)均非負(fù), 則下列關(guān)則下列關(guān)系有且只有一個(gè)成立系有且只有一個(gè)成立:參考文獻(xiàn)參考文獻(xiàn): : P. Stein, R.L. Rosenberg, On the solution of linear simultaneous equations by iteration, J. Lon

9、don Math. Soc.(2) 0 ()()1;GSJBB (3) ()()1;JGSBB (4) 1 ()()JGSBB 。1:51第20頁(yè)/共34頁(yè)第二十頁(yè)，共34頁(yè)。11( )( )()|*|kkkXXXXBB 1:5111( )*( )()|kkkLLxxxx ( )xx 11,xMNxM bAMN其其中中迭代法構(gòu)造迭代法構(gòu)造(guzo)收斂條件收斂條件(tiojin)(局部局部vs全局全局)中止中止(zhngzh)準(zhǔn)則準(zhǔn)則*(0)*()( )|()| 1,(, ()N xxxN xxxxx 為為的的不不動(dòng)動(dòng)點(diǎn)點(diǎn)在在的的連連續(xù)續(xù)且且則則迭迭代代法法對(duì)對(duì)任任意意某某鄰鄰域域收收斂斂(

10、0)X( )1| | |1fBB 對(duì)對(duì)任任意意的的 和和迭迭代代法法收收斂斂的的充充分分必必要要條條件件是是和和充充分分條條件件是是任任意意的的初初始始向向量量統(tǒng)一的不動(dòng)點(diǎn)框架統(tǒng)一的不動(dòng)點(diǎn)框架第21頁(yè)/共34頁(yè)第二十一頁(yè)，共34頁(yè)。直接(zhji)法vs迭代法 基于基于(jy)高斯消元法的直接方法提高斯消元法的直接方法提供了有限步內(nèi)就可以得到解的方法。供了有限步內(nèi)就可以得到解的方法。1:51 尋求迭代方法的理由尋求迭代方法的理由(lyu)是什么呢？是什么呢？十階十階 百階百階 萬(wàn)階萬(wàn)階 百萬(wàn)階百萬(wàn)階 億階億階 小小 不大不大 較大較大 大大 超大超大第22頁(yè)/共34頁(yè)第二十二頁(yè)，共34頁(yè)。迭代

11、法優(yōu)勢(shì)(yush)1: 直接法運(yùn)行一個(gè)完整LU分解才能得到解,迭代法從初始(ch sh)解開(kāi)始每步對(duì)其加工改善使其更加精確。問(wèn)題是在用戶(hù)容忍的范圍內(nèi)需要多少步才能得到收斂性？1:51注釋:運(yùn)行一個(gè)完整LU分解花費(fèi)O(n3)階運(yùn)算,一般地,迭代(di di)法每次迭代(di di)花費(fèi)O(n2)階運(yùn)算, 即每次迭代(di di)僅需要完整LU分解花費(fèi)的一部分。第23頁(yè)/共34頁(yè)第二十三頁(yè)，共34頁(yè)。迭代法優(yōu)勢(shì)迭代法優(yōu)勢(shì)(yush)2: 求解求解(qi ji)稀疏方程組是使用迭代法的稀疏方程組是使用迭代法的主要理由。主要理由。1:51注釋:系數(shù)矩陣稀疏度為n, 則求解稀疏方程組迭代法每步迭代花費(fèi)O

12、(n)階運(yùn)算(yn sun)。求解特殊結(jié)構(gòu)方程組(如Toeplitz)迭代法每步迭代花費(fèi)O(nlogn)階運(yùn)算(yn sun)。第24頁(yè)/共34頁(yè)第二十四頁(yè)，共34頁(yè)。( ),01(0)(1)0uf xxuu Poisson方程方程(fngchng):令令 h = 1/(n+1) , xi= ih ( i = 0,1, , n+1 )記記 ui= u(xi ), (i = 0,1, , n+1)迭代迭代(di di)計(jì)算格計(jì)算格式式:1(1)( )( )21()/ 2iikkkiiuuuh f x 121)2(iiiih f xuuu 差分差分(ch fn)格式格式:22()( )( )( )

13、hf ahf ahfafa22()( )( )( )hf ahf ahfafa22()2 ( )()( )()f ahf af ahfaO hh 1(1)(1)( )21()/ 2iikkkiiuuuh f x 第25頁(yè)/共34頁(yè)第二十五頁(yè)，共34頁(yè)。2112112A n=10000;e=ones(n,1);A = spdiags(e -2*e e, -1:1, n, n), spy(A)第26頁(yè)/共34頁(yè)第二十六頁(yè)，共34頁(yè)。 HB矩陣矩陣(j zhn)稀疏模式稀疏模式來(lái)源來(lái)源 The original Harwell-Boeing collection來(lái)源來(lái)源(liyun):The Uni

14、versity of Florida Sparse Matrix (liyun):The University of Florida Sparse Matrix CollectionCollection第27頁(yè)/共34頁(yè)第二十七頁(yè)，共34頁(yè)。 FreeFieldTechnologies矩陣稀疏矩陣稀疏(xsh)模式模式來(lái)源來(lái)源3D vibro-acoustic problem, aircraft engine nacelle第28頁(yè)/共34頁(yè)第二十八頁(yè)，共34頁(yè)。 vanHeukelum矩陣稀疏模式矩陣稀疏模式(msh) 來(lái)源來(lái)源DNA electrophoresis第29頁(yè)/共34頁(yè)第二十九

15、頁(yè)，共34頁(yè)。 garon2矩陣矩陣(j zhn)稀疏模式稀疏模式 2D FEM, Navier-Stokes, CFD第30頁(yè)/共34頁(yè)第三十頁(yè)，共34頁(yè)。 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

16、 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頁(yè)/共34頁(yè)第三十一頁(yè)，共34頁(yè)。 help sparfunMatlab與大數(shù)據(jù)處理與大數(shù)據(jù)處理Elementary sparse matrices (例如(lr)spdiags)Full to sparse conversion (例如(lr)sparse)Wor