8-收敛性分析初步

1、向量序列的收敛性 迭代法的收敛性分析 迭代误差估计定理 平面温度场计算,收敛性分析初步,平面点列:,X (k)Rn : X(1), X (2), , X (k) , ,利用向量范数等价性, 对任意范数 | |,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, ),计算格式: X(k+1) = B X(k) + f ( B = M-1N ),X(k+1) X*= B(X(k) X*),设方程组的精确解为 X*,则有,X

2、* = B X* + f ,(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,事实上 ( I - B)( I + B + B2 + + Bk ) =I Bk+1,注3:

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为严格对角占优阵.,例1 常微分方程边值问题,求在 x1=0.1, x2=0.2, , x9=0.9 处的数值解, yj-1 + (2 + h2) yj yj+1 = xj h2 ( j= 1,2,9),高斯-赛德尔迭代格式:,误差限设置：10-5。 迭代次数k=60，error0 = 1.2742e-004,定理4.3 若Ax=b的系数矩阵A是严格对角占优矩阵,则Jacobi迭

4、代和Seidel迭代均收敛,证: 由于矩阵A严格对角占优,由A矩阵构造Jacobi迭代矩阵BJ = D-1(D A) 第 i 行绝对值求和,所以,矩阵B 的谱,设n阶方阵B 的n个特征值为:,则称集合,为B 的谱. 记为 ch B,矩阵B的谱半径,注1: 当B是对称矩阵时, |B|2 = (B),注2: 对 Rnn 中的范数| |,有 (B) | B |,特征值取模最大,定理4.1 迭代法 X(k+1) = B X(k) + f 收敛 谱半径(B) 1,例2 线性方程组 A X = b, 分别取系数矩阵为,分析Jacobi 迭代法和 Seidel 迭代法的敛散性,Jacobi X(k+1)=D

5、-1(U+L)X(k)+D-1b Seidel X(k+1) = (D L)-1b + (D L)-1UX(k),Ans= 1.2604e-005,D=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,-2,D=diag(diag(A2) B2=D(D-A2) max(abs(eig(B2),Ans= 1.1180,发散,DL=tril(A1) B1=DL(DL-A1) max(abs(eig(B1),Ans= 2,发散,DL=tril(A2) B2=DL(DL-A2)

6、 max(abs(eig(B2),Ans= 1/2,收敛,定理4.2 :设X*为方程组 AX=b 的解 若|B|1,则对迭代格式 X(k+1) = B X(k) + f 有,(1),(2),证 由|B|1,有,| X(k+1) X* | |B| | X(k) X* |,|X(k+1) X(k) |= |(X* X(k) (X* X(k+1)|,|(X* X(k) | |(X* X(k+1)|,| X(k+1) X* | |B| | X(k) X* |, |(X* X(k)| |B| |(X* X(k)|,= ( 1 - | B |) |(X* X(k)|,平面温度场问题:,令 h = 1/(n

7、+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,高斯-赛德尔迭代法实验(误差限10-8):,定理4.4 方程组 Ax=b 中, 若 A 是实对称正定矩阵,则Gauss-Seidel迭法收敛,证明: 由 A = D L LT BG-S = (D L)-1LT,A 正定,故 p = xTDx0, 记 xTLTx = a , 则有,xTAx=xT(D L LT)x=p

8、a a =p 2a 0,设 为BG-S的任一特征值, x 为其特征向量,则,称 R= ln 为迭代法的渐近收敛速度。,所以, 迭代矩阵 BG-S 的谱半径 (BG-S) 1,从而当,方程组 Ax=b的系数矩阵A 是实对称正定矩阵时, Gauss-Seidel迭代法收敛。,(i=1,2, n; k = 1,2,3, ),超松驰(SOR)迭代法,Gauss-Seidel迭代格式,最佳松驰因子选取,迭代矩阵,为Jacobi迭代谱半径.,定理4.8 若 A 是对称正定矩阵, 则当0 2 时,SOR 迭代法解方程组 Ax = b 是收敛的。,BJ = D-1(U+L),平面温度场问题:,令 h = 1/

9、(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,系数矩阵,Seidel迭代格式,SOR迭代格式,最佳松驰因子,Gauss-Seidel迭代实验 (误差限10-8):,SOR迭代实验(误差限10-8):,块迭代法简介 设 ARnn, xRn, bRn,其中, AiiRnini, AijRninj , xiRni, BiRni,将方程组 Ax = b 中系数矩阵 A 按行列分块,将A分解, A = DB LB UB,Jacobi块迭代 DB 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,算法I:,三对角矩阵的三角分解 A = L U,( k = 2,3,n1 )