跳至主要內容

Ch4 古典迭代法

Hu2025/9/25数学

Ch4 古典迭代法

4.1 单步线性定常迭代法

4.1.1 一般定义

  1. 新的近似解xkx_k是已知近似解xk−1x_{k-1}的线性函数，并且只与xk−1x_{k-1}有关；

  2. 单步线性定常迭代法有如下形式：

xk=Txk−1+g(4.1)x_k = Tx_{k-1} + g \tag{4.1}

其中TT是迭代矩阵，gg是常数项

4.1.2 Jacobi迭代与Gauss-Seidel迭代

考虑Ax=bAx = b，令A=D−L−UA = D -L -U，则

  • Jacobi:

TJ=D−1(L+U),gJ=D−1b(4.2)T_{J} = D^{-1}(L+U), g_J = D^{-1}b \tag{4.2}

  • Weighted Jacobi:

x∗=TJx(k)+gJ⟹x(k+1)=(1−ω)x(k)+ωx∗x_{*} = T_{J}x^{(k)} + g_J \Longrightarrow x^{(k+1)} = (1-\omega)x^{(k)} + \omega x_{*}

Tω=(1−ω)I+ωD−1(L+U)(4.3)T_{\omega} = (1-\omega)I + \omega D^{-1}(L+U) \tag{4.3}

  • Gauss-Seidel:

TGS=(D−L)−1U,gGS=(D−L)−1b(4.4)T_{GS} = (D-L)^{-1}U, g_{GS} = (D-L)^{-1}b \tag{4.4}

  • Backward G-S:

TBGS=(D−U)−1L,gBGS=(D−U)−1b(4.5)T_{BGS} = (D-U)^{-1}L, g_{BGS} = (D-U)^{-1}b \tag{4.5}

注意在具体实现时，两种方法的分量计算顺序不尽相同！！！
Jacobi迭代法是每次完全只用第k−1k-1次的，而G-S迭代法是使用混杂的分量：

  • Jacobi：

aiixi(k+1)=−∑j≠i;  j=1naijxj(k)+bi(4.6)a_{ii}x_i^{(k+1)} = - \sum_{j\neq i;\;j=1}^{n} a_{ij}x_j^{(k)} + b_i \tag{4.6}

  • G-S：

aiixi(k+1)=−∑j=1i−1aijxj(k+1)−∑j=i+1naijxj(k)+bi(4.7)a_{ii}x_i^{(k+1)} = - \sum_{j=1}^{i-1} a_{ij}x_j^{(k+1)} - \sum_{j=i+1}^{n} a_{ij}x_j^{(k)} + b_i \tag{4.7}

  • Backward G-S：

aiixi(k+1)=−∑j=1i−1aijxj(k)−∑j=i+1naijxj(k+1)+bi(4.8)a_{ii}x_i^{(k+1)} = - \sum_{j=1}^{i-1} a_{ij}x_j^{(k)} - \sum_{j=i+1}^{n} a_{ij}x_j^{(k+1)} + b_i \tag{4.8}

4.1.3 收敛性理论

  • （一般性理论）单步线性定常迭代法收敛的充要条件是Mk→0M^k \rightarrow 0，
    • 进一步，充要条件是ρ(M)<1\rho(M) < 1。
  • Jacobi迭代法：
    • 若AA对称，且其对角元均大于0，则Jacobi收敛的充要条件是AA与2D−A2D-A均正定。
  • G-S迭代法：
    • 若AA对称正定，则G-S收敛。
    • 若AA严格对角占优或不可约对角占优，则Jacobi和G-S都收敛。

4.1.4 收敛速度

R∞(M)=−ln⁡ρ(M)R_{\infty}(M) = -\ln\rho(M)

4.2 超松弛迭代法

4.2.1 迭代形式

分量形式：xi(k+1)=(1−ω)xi(k)+ωxiGS,  where  xiGS  equals  xi(k+1)  in  (4.7).x_i^{(k+1)} = (1-\omega)x^{(k)}_i + \omega x_i^{GS}, \; where\; x_i^{GS} \;equals \;x_i^{(k+1)}\; in\; (4.7).
总形式：

xk+1=TSORxk+ω(D−ωL)−1b(4.9)x_{k+1} = T_{SOR}x_k + \omega(D - \omega L)^{-1}b \tag{4.9}

其中TSOR=(D−ωL)−1[(1−ω)D+ωU]T_{SOR} = (D - \omega L)^{-1}\left[(1-\omega)D + \omega U \right]称为松弛迭代法的迭代矩阵，ω\omega称为松弛因子：

  • ω=1\omega =1：G-S迭代法；ω>1\omega>1：超松弛（SOR）；ω<1\omega < 1：低松弛.

4.2.2 收敛性分析

  • SOR迭代法收敛的充要条件是ρ(Lω)<1\rho(L_{\omega}) < 1；
  • SOR迭代法收敛的必要条件是0<ω<20 < \omega < 2；
  • 若AA严格对角占优或不可约对角占优，且ω∈(0,1)\omega \in (0,1 )，则SOR收敛；
  • 若AA是实对称矩阵，则当ω∈(0,2)\omega \in (0,2)时，SOR收敛。

4.2.3 最佳松弛因子

随着ω\omega从0开始增加，ρ(TSOR)\rho(T_{SOR})逐渐减小，直至

ω=ωopt=21+1−ρ2(B)\omega = \omega_{opt} = \frac{2}{1 + \sqrt{1 - \rho^2(B)}}

此时ρ(TSOR)\rho(T_{SOR})达到极小：

ρ(Topt)=1−1−ρ2(B)1+1−ρ2(B)\rho(T_{opt}) = \frac{1 - \sqrt{1 - \rho^2(B)}}{1 + \sqrt{1 - \rho^2(B)}}

此后ω\omega增加，ρ\rho也随之增加。

链接到当前文件 0
没有文件链接到当前文件