8收斂性分析初步

1、向量序列的收斂性迭代法的收斂性分析迭代誤差估計(jì)定理平面溫度場計(jì)算收斂性分析初步平面點(diǎn)列:X (k)Rn : X(1), X (2), , X (k) , 利用向量范數(shù)等價(jià)性, 對(duì)任意范數(shù) | |A X = b (MN )X = b M X = N X + b記 (k) = X(k) X* ( k = 0, 1, 2, 3, )則有 (k+1) = B (k) (k) = B (k-1) ( k = 1, 2, 3, )計(jì)算格式: X(k+1) = B X(k) + f ( B = M-1N ) X(k+1) X*= B(X(k) X*) 設(shè)方程組的精確解為 X*,則有X* = B X* + f

2、 (1)(k) = B (k-1)=B2 (k-2)=Bk (0)迭代格式 X(k+1) = B X(k) + f 收斂(2)證: 由(k) = B (k-1),得 | (k)| | B| | (k-1)| ( k = 1, 2, 3, )所以命題 若|B|1,則迭代法 X(k+1) =B X(k) +f 收斂| (k)| | B|k | (0)| | B| 1注1: AX = b X = BX + f ( I B )X = f X = ( I B )-1 f 注2: 若 則( I - B)-1 = I + B + B2 + + Bk + 事實(shí)上 ( I - B)( I + B + B2 +

3、+ Bk ) =I Bk+1注3: X(k) =B X(k-1) + f = B(B X(k-2) + f) + f = = Bk X(0) + ( I + B + + Bk-1)f ( I B )-1 f 定義4.1 A=(aij)nn, 如果則稱A為嚴(yán)格對(duì)角占優(yōu)陣.例1 常微分方程邊值問題 求在 x1=0.1, x2=0.2, , x9=0.9 處的數(shù)值解 yj-1 + (2 + h2) yj yj+1 = xj h2 ( j= 1,2,9) 高斯-賽德爾迭代格式:誤差限設(shè)置：10-5。迭代次數(shù)k=60，error0 = 1.2742e-004 定理4.3 若Ax=b的系數(shù)矩陣A是嚴(yán)格對(duì)角

4、占優(yōu)矩陣,則Jacobi迭代和Seidel迭代均收斂證: 由于矩陣A嚴(yán)格對(duì)角占優(yōu)由A矩陣構(gòu)造Jacobi迭代矩陣BJ = D-1(D A)第 i 行絕對(duì)值求和所以矩陣B 的譜設(shè)n階方陣B 的n個(gè)特征值為: 則稱集合為B 的譜. 記為 ch B矩陣B的譜半徑注1: 當(dāng)B是對(duì)稱矩陣時(shí), |B|2 = (B) 注2: 對(duì) Rnn 中的范數(shù)| |,有 (B) | B |特征值取模最大定理4.1 迭代法 X(k+1) = B X(k) + f 收斂 譜半徑(B) 1例2 線性方程組 A X = b, 分別取系數(shù)矩陣為分析Jacobi 迭代法和 Seidel 迭代法的斂散性Jacobi X(k+1)=D-

5、1(U+L)X(k)+D-1bSeidel X(k+1) = (D L)-1b + (D L)-1UX(k) Ans= 1.2604e-005D=diag(diag(A1);B1=D(D-A1);max(abs(eig(B1)A1=1,2,-2;1,1,1;2,2,1收斂A2=2,-1,1;1,1,1;1,1,-2D=diag(diag(A2)B2=D(D-A2)max(abs(eig(B2)Ans= 1.1180發(fā)散DL=tril(A1)B1=DL(DL-A1)max(abs(eig(B1)Ans= 2發(fā)散DL=tril(A2)B2=DL(DL-A2)max(abs(eig(B2)Ans=

6、1/2收斂定理4.2 :設(shè)X*為方程組 AX=b 的解若|B|1,則對(duì)迭代格式 X(k+1) = B X(k) + f 有(1)(2)證 由|B|0, 記 xTLTx = a , 則有xTAx=xT(D L LT)x=p a a =p 2a 0設(shè) 為BG-S的任一特征值, x 為其特征向量,則稱 R= ln 為迭代法的漸近收斂速度。所以, 迭代矩陣 BG-S 的譜半徑 (BG-S) 1,從而當(dāng)方程組 Ax=b的系數(shù)矩陣A 是實(shí)對(duì)稱正定矩陣時(shí), Gauss-Seidel迭代法收斂。(i=1,2, n; k = 1,2,3, )超松馳(SOR)迭代法Gauss-Seidel迭代格式最佳松馳因子選取

7、迭代矩陣為Jacobi迭代譜半徑.定理4.8 若 A 是對(duì)稱正定矩陣, 則當(dāng)0 2 時(shí)SOR 迭代法解方程組 Ax = b 是收斂的。BJ = D-1(U+L) 平面溫度場問題:令 h = 1/(n+1) , xj= jh, yj = jh ( i , j = 0,1, , n+1 )記 ui,j= u(xi , yj ), ( i , j = 0,1, , n+1 )線性方程組( i,j = 1,n )u0, j = 0, ui, 0 = 0, ui, n+1 = 0系數(shù)矩陣Seidel迭代格式SOR迭代格式最佳松馳因子結(jié)點(diǎn)數(shù)n2 102 202 402迭代次數(shù) 182 606 2077CP

8、U時(shí)間(s) 0.97 4.328 58.531誤差 0.0023 6.4274e-4 1.6814e-4Gauss-Seidel迭代實(shí)驗(yàn) (誤差限10-8):SOR迭代實(shí)驗(yàn)(誤差限10-8):結(jié)點(diǎn)數(shù)n2 102 202 402迭代次數(shù) 40 74 137CPU時(shí)間(s) 0.11 0.6560 4.9530 誤差 0.0023 6.4306e-4 1.6944e-4 塊迭代法簡介設(shè) ARnn, xRn, bRn其中, AiiRnini, AijRninj , xiRni, BiRni將方程組 Ax = b 中系數(shù)矩陣 A 按行列分塊將A分解, A = DB LB UB Jacobi塊迭代 D

9、B X(k+1) = (LB + UB)X(k) + B( i=1,2, r )(2)Gauss-Seidel塊迭代 DB X(k+1) = LB X(k+1)+ UBX(k) + b( i=1,2, r )( i,j = 1,n )邊值問題:, , AU = F Gauss-Seidel算法I:三對(duì)角矩陣的三角分解 A = L U( k = 2,3,n1 )緊格式: L+U I 下三角方程組 LY = f 算法II:上三角方程組 UX = Y 算法III: n2 102 202 402 602迭代次數(shù) 107 339 1135 2331CPU時(shí)間0.3750 4.3750 58.0470 284.9060誤差 0.0023 6.42e-4 1.68e-4 7.51e-5五點(diǎn)差分格式塊迭代實(shí)驗(yàn) (誤差限:1e-008) n2 102 202 402 602迭代