4.2 SOR 超鬆弛法#

概念說明#

Gauss-Seidel 每步把 \(x_i\) 從舊值移到「局部正確值」。SOR（Successive Over-Relaxation，逐次超鬆弛）的想法很簡單卻影響深遠：既然要動，何不動得更多？將 GS 更新記為 \(\hat{x}_i\) ，SOR 取

其中 \(\omega\) 是鬆弛因子： \(\omega = 1\) 退回 Gauss-Seidel； \(0 < \omega < 1\) 為欠鬆弛（保守、有助於穩住震盪）； \(1 < \omega < 2\) 為超鬆弛（激進、沿 GS 方向過頭一步以加速）。譜半徑分析給出嚴格結論：**SOR 收斂的必要條件是 \(0 < \omega < 2\) **；對嚴格對角佔優矩陣， \(\omega \le 1\) 保證收斂。

\(\omega\) 的威力在特殊結構的矩陣上有精確理論。對均匀網格的拉普拉斯系統（模型問題），設 Jacobi 譜半徑為 \(\rho_J = \cos(\pi h)\) （ \(h\) 為網格步距），則最佳鬆弛因子有 Young 公式：

效果驚人：GS 需迭代 \(O(h^{-2})\) 次，最佳 SOR 只需 \(O(h^{-1})\) 次。網格 100×100 時，迭代次數從約 14000 降到約 300——兩個數量級。原理直觀：GS 能快速壓制「高頻誤差」，對「低頻誤差」卻非常遲鈍（ \(\rho_{GS} = 1 - O(h^2)\) 貼著 1）；超鬆弛的過頭修正恰好放大了對低頻誤差的推力。這個「頻率」觀點也是多重網格法（9.1 節）的入門磚。

實務上 \(\omega_{\text{opt}}\) 常未知（一般矩陣沒有 Young 公式），常用策略：試幾個 \(\omega\) 畫迭代次數曲線取最低點；或動態估計譜半徑線上調整。曲線在最佳點附近左側平緩、右側陡峭，故寧可略小勿過大。

生活類比#

調淋浴水溫：保守的人每次小轉一點（欠鬆弛，穩但久），激進的人按直覺多轉半圈（超鬆弛，快但可能沖過頭再拉回）。經驗告訴我們「比直覺再多轉一點、但別轉過兩倍」，正是 \(1 < \omega < 2\) 的甜蜜區。

演算法步驟#

1. 選鬆弛因子 \(\omega\) （預設 1.3 左右試探，或用 Young 公式）。
2. 對每個 \(i\) ：先算 GS 值 \(\hat{x}_i = \dfrac{1}{a_{ii}}(b_i - \sum_{j \ne i} a_{ij} x_j)\) 。
3. 更新 \(x_i \leftarrow (1-\omega) x_i + \omega \hat{x}_i\) 。
4. 每輪結束算殘差，小於容許值停止；超過最大迭代則回報。

Python 範例#

對模型問題（一維拉普拉斯）比較 GS 與不同 \(\omega\) 的 SOR：

import numpy as np

def sor(n, omega, tol=1e-10, max_iter=50000):
    """解 -u'' = f 離散系統：x[i-1] - 2x[i] + x[i+1] = -h^2, x[0]=x[n+1]=0"""
    h = 1.0 / (n + 1)
    x = np.zeros(n + 2)
    it = 0
    for it in range(1, max_iter + 1):
        delta = 0.0
        for i in range(1, n + 1):
            gs = 0.5 * (x[i-1] + x[i+1] + h*h)   # GS 更新
            new = (1 - omega) * x[i] + omega * gs
            delta = max(delta, abs(new - x[i]))
            x[i] = new
        if delta < tol:
            break
    return it

n = 100
rhoJ = np.cos(np.pi / (n + 1))
w_opt = 2 / (1 + np.sqrt(1 - rhoJ**2))
print(f"理論最佳 omega = {w_opt:.4f}")
for w in [1.0, 1.7, w_opt, 1.95]:
    print(f"omega = {w:.4f}: 迭代 {sor(n, w)} 次")

輸出顯示 \(\omega = 1\) （GS）需上萬次迭代， \(\omega_{\text{opt}}\) 附近驟降到數百次，而 \(\omega\) 過大（1.95）又回升——完美的 U 型曲線。

複雜度與收斂性分析#

每輪成本與 Gauss-Seidel 相同 \(O(\text{nnz})\) ，加速純粹來自減少輪數。模型問題上 \(k_{GS} = O(h^{-2})\) ， \(k_{SOR} = O(h^{-1})\) ；一般情形若能估到 \(\rho_J\) ，也有類似量級的改善。記憶體不變。調參成本（試 \(\omega\) ）是一次性的，可在同構問題間重用——偏微分方程求解器正是這樣做的。

練習#

1. 用 4.1 的對角佔優矩陣測 \(\omega \in \{0.8, 1.0, 1.2, 1.5\}\) ，畫出迭代次數對 \(\omega\) 的曲線。
2. 證明：SOR 收斂蘊含 \(0 < \omega < 2\) （提示：迭代矩陣的行列式與特徵值乘積的關係）。
3. 把 SOR 改寫成「紅黑排序」版本（先更新偶數指標、再更新奇數指標），使迴圈可向量化，並比較速度。