線性方程組(3)-靜態迭代法

02-28

上一節講到直接解法有誤差積累和破壞矩陣稀疏性的問題。

實際中應用較廣泛的是解法通常是迭代法。迭代法的結果的誤差可以由迭代終止條件控制，只要迭代能收斂到滿足迭代終止條件，那麼結果的誤差就不會超出終止條件控制的範圍。但是，在此之前先要確定迭代法能否在可以接受的步數之內收斂。

不嚴謹地說，迭代法收斂性的大致趨勢是：對於常用的大多數迭代法，矩陣的條件數越小收斂越快。

常用的迭代終止條件有： $lVert vec{b}-Avec{x}^{left(k ight)} Vert<varepsilon$ 、 $lVert vec{x}^{left(k ight)}-vec{x}^{left(k-1 ight)} Vert<varepsilon$ 等， $varepsilon$ 的選取取決於對解的精度要求。

靜態迭代法（stationary iterative methods）是指形如

$vec{x}^{left(k+1 ight)}= Gvec{x}^{left(k ight)}+vec{c}$

的迭代法。因為 $G$ 和 $vec{c}$ 不隨迭代步數而變化，所以叫靜態迭代法。這裡介紹三種靜態迭代法：雅可比法（Jacobi method）、高斯-賽德爾法（Gauss-Seidel method）和松馳法（successive relaxation method）。

靜態迭代法收斂的充分條件是，存在運算元範數 $lVert cdot Vert$ ，使得 $lVert G Vert < 1$ ；更容易計算的一個充分條件是， $G$ 的最大特徵值的模小於 $1$ 。

雅可比法

一個線性方程組的第 $i$ 個方程是

$sum_{j=1}^{n}a_{ij}x_{j}=b_{i}$

假設除了 $x_i$ 以外的所以未知數都已被解出，那麼

$x_i=frac{1}{a_{ii}}left(b_i-sum_{j=0,j eq i}^{n}a_{ij}x_j ight)$

即可推導出迭代法

$x_i^{left(k+1 ight)}=frac{1}{a_{ii}}left(b_i-sum_{j=0}^{i-1}a_{ij}x_j^{left(k ight)}-sum_{j=i+1}^{n}a_{ij}x_j^{left(k ight)} ight)$

若將矩陣 $A$ 分解為三部分 $A=L+D+U$ ，其中 $L$ 為不包括對角線的下三角部分， $D$ 為對角線， $U$ 為不包括對角線的上三角部分；則雅可比法可寫成矩陣形式

$vec{x}^{left(k+1 ight)} = -D^{-1}left(L+U ight)vec{x}^{left(k ight)}+D^{-1}vec{b}$

高斯-賽德爾法

在雅可比法中，新值是用舊值代入解出的，而我們通常認為新值比舊值更接近精確解。如果 $x_1^{left(k+1 ight)}$ 到 $x_n^{left(k+1 ight)}$ 是按順序依次計算的，那麼在計算 $x_i^{left(k+1 ight)}$ 時可以用前面已經計算出來的 $i-1$ 個新值，即

$x_i^{left(k+1 ight)}=frac{1}{a_{ii}}left(b_i-sum_{j=0}^{i-1}a_{ij}x_j^{left(k+1 ight)}-sum_{j=i+1}^{n}a_{ij}x_j^{left(k ight)} ight)$

高斯-賽德爾法也可以寫成矩陣形式

$vec{x}^{left(k+1 ight)}= -D^{-1}Lvec{x}^{left(k+1 ight)}-D^{-1}Uvec{x}^{left(k ight)}+D^{-1}vec{b}$

或

$vec{x}^{left(k+1 ight)} = -left(D+L ight)^{-1}Uvec{x}^{left(k ight)}+left(D+L ight)^{-1}vec{b}$

高斯-賽德爾法還有其反向形式，即先計算 $x_{n}^{left(k+1 ight)}$ 到 $x_{i+1}^{left(k+1 ight)}$ ，再計算 $x_{i}^{left(k+1 ight)}$ ，迭代公式為

$x_i^{left(k+1 ight)}=frac{1}{a_{ii}}left(b_i-sum_{j=0}^{i-1}a_{ij}x_j^{left(k ight)}-sum_{j=i+1}^{n}a_{ij}x_j^{left(k+1 ight)} ight)$

矩陣形式

$vec{x}^{left(k+1 ight)} = -left(D+U ight)^{-1}Lvec{x}^{left(k ight)}+left(D+U ight)^{-1}vec{b}$

雅可比法與高斯-賽德爾法的總結與比較

雅可比法和高斯-賽德爾法收斂的一個充分條件是係數矩陣 $A$ 嚴格對角佔優或不可約弱對角佔優。

高斯-賽德爾法由於使用了新值，收斂性比雅可比法好。但是前面提到， $x_1^{left(k+1 ight)}$ 到 $x_n^{left(k+1 ight)}$ 是按順序依次計算的，這就使得高斯-賽德爾法的並行性有限，從而迭代一步的計算時間比雅可比法要長。

松馳法

高斯-賽德爾法迭代公式可寫為

$vec{x}^{left(k+1 ight)}= vec{x}^{left(k ight)}+left(-vec{x}^{left(k ight)}-D^{-1}Lvec{x}^{left(k+1 ight)}-D^{-1}Uvec{x}^{left(k ight)}+D^{-1}vec{b} ight)$

將這個變化量乘上鬆弛因子 $omega$ ，得到

$vec{x}^{left(k+1 ight)}= vec{x}^{left(k ight)}+omegaleft(-vec{x}^{left(k ight)}-D^{-1}Lvec{x}^{left(k+1 ight)}-D^{-1}Uvec{x}^{left(k ight)}+D^{-1}vec{b} ight)$

即

$vec{x}^{left(k+1 ight)} = -left(D+omega L ight)^{-1}left(left(1-omega ight)D-omega U ight)vec{x}^{left(k ight)}+omegaleft(D+omega L ight)^{-1}vec{b}$

鬆弛法中的

$G=-left(D+omega L ight)^{-1}left(left(1-omega ight)D-omega U ight)$

可以證明，其最大特徵值的模 $lvertlambda_{max} vertgeqslant lvert omega-1 vert$ ，所以應該選取 $0<omega<2$ 。在實際應用中通常取 $1<omega<2$ 時收斂較快，這個條件下的鬆弛法又稱為超松馳法（successive over-relaxation method）。

靜態迭代法在上個世紀還非常流行，曾有很多論文討論如何改進高斯-賽德爾法、如何選取鬆弛因子等等。隨著非靜態迭代法的發展，靜態迭代法因收斂性不足而逐漸被取代。這裡為何還要講靜態迭代法呢？這裡先不做解釋，之後會有需要靜態迭代法的地方出現。