数值分析实验 - 解线性方程组的迭代法

数值分析实验 6 - 解线性方程组的迭代法

目的和意义

问题提出

数值分析实验 - 线性方程组的直接解法 所列目的和意义的线性方程组,试分别选用 Jacobi 迭代法,Gauss-Seidol 迭代法和 SOR 方法计算其解

要求

  1. 体会迭代法求解线性方程组,并能与消去法做以比较;
  2. 分别对不同精度要求,如 \(\epsilon=10^{-3},10^{-4},10^{-5}\), 由迭代次数体会该迭代法的收敛快慢;
  3. 对方程组 2, 3 使用 SOR 方法时,选取松弛因子 \(\omega=0.8, 0.9, 1, 1.1, 1.2\) 等,试看对算法收敛性的影响,并能找出你所选用的松弛因子的最佳者;
  4. 给出各种算法的设计程序和计算结果

目的和意义

  1. 通过上机计算体会迭代法求解线性方程组的特点,并能和消去法比较;
  2. 运用所学的迭代法算法,解决各类线性方程组,编出算法程序;
  3. 体会上机计算时,终止步骤 \(\|x^{(k+1)}-x^{(k)}\|_{\infty}<\epsilon\)\(k>\) (予给的迭代次数), 对迭代法敛散性的意义;
  4. 体会初始解 \(x^{(0)}\), 松弛因子的选取,对计算结果的影响

计算公式

\[ A=D-L-U \]

其中

  • \[ D=\begin{bmatrix} a_{11}\\ &a_{22}\\ \phantom{\vdots}&&\ddots\\ &&&a_{nn} \end{bmatrix} \]
  • \[ L=\begin{bmatrix} 0\\ -a_{21}&0\\ \vdots&\vdots&\ddots\\ -a_{n1}&-a_{n2}&\dots&0 \end{bmatrix} \]
  • \[ U=\begin{bmatrix} 0&-a_{12}&\dots&-a_{1n}\\ &0&\dots&-a_{2n}\\ &&\ddots&\vdots\\ &&&0 \end{bmatrix} \]

Jacobi 迭代法

\[ G=D^{-1}(L+U) \]

\[ x^{(k+1)}=Gx^{(k)}+D^{-1}b \]

收敛条件为 \(\rho(G)<1\)

Gauss-Seidol 迭代法

\[ G=(D-L)^{-1}U \]

\[ x^{(k+1)}=Gx^{(k)}+(D-L)^{-1}b \]

收敛条件为 \(\rho(G)<1\)

SOR 方法

\[ G=(D-\omega L)^{-1}((1-\omega)D+\omega U) \]

\[ x^{(k+1)}=Gx^{(k)}+\omega(D-\omega L)^{-1}b \]

收敛条件为 \(\rho(G)<1\)

程序设计

主程序

Show code

Jacobi 迭代法

Show code

Gauss-Seidol 迭代法

Show code

SOR 方法

Show code

结果讨论和分析

结果

方程组的解经验证符合要求,为节省篇幅而略去

  • \(\epsilon=10^{-3}\) 时的迭代次数

    方程组 1方程组 2方程组 3
    Jacobi 迭代法不收敛不收敛15
    Gauss-Seidol 迭代法不收敛12567
    SOR 方法 (\(\omega=0.8\))不收敛189510
    SOR 方法 (\(\omega=1.2\))不收敛8429
  • \(\epsilon=10^{-4}\) 时的迭代次数

    方程组 1方程组 2方程组 3
    Jacobi 迭代法不收敛不收敛15
    Gauss-Seidol 迭代法不收敛16929
    SOR 方法 (\(\omega=0.8\))不收敛255113
    SOR 方法 (\(\omega=1.2\))不收敛113211
  • \(\epsilon=10^{-5}\) 时的迭代次数

    方程组 1方程组 2方程组 3
    Jacobi 迭代法不收敛不收敛15
    Gauss-Seidol 迭代法不收敛212911
    SOR 方法 (\(\omega=0.8\))不收敛320716
    SOR 方法 (\(\omega=1.2\))不收敛142313
  • SOR 方法中,方程组 2 的迭代次数与 \(\omega\) 的变化图像

  • SOR 方法中,方程组 3 的迭代次数与 \(\omega\) 的变化图像

结论

  • SOR 方法中
    • 对于方程组 2, \(\omega=1.9\) 时的迭代步数最小,且与 \(\omega=0.8\) 时的迭代步数差别较大
    • 对于方程组 3, \(\omega=1.0\) 时的迭代步数最小,不同 \(\omega\) 之间迭代步数差别不大