為甚麼逐個更新分量?
模型離散化後常得到大型稀疏方程組 。直接分解可能需要大量儲存空間,定常迭代則反覆改進近似解。Jacobi 用舊向量計算所有新分量;Gauss–Seidel 一算出新分量便立即使用。因此方程的排列次序也是算法的一部分。我們會證明對稱正定系統的一個收斂結果,並看清鬆弛參數的作用。這個結果以精確算術為前提,不能直接預測運算時間或捨入誤差。
將 分解為對角、嚴格下三角與嚴格上三角部分,假設 。從舊迭代向量 出發,Gauss–Seidel 的一輪滿足
這可用前代法計算,無須形成逆矩陣。第 個分量利用目前最新的數值,先算出暫定值
定義 1.7.1
(Gauss–Seidel 與 SOR 的一輪)
Gauss–Seidel 的一輪依次處理 ,並令 。參數為 (各輪固定不變)的逐次超鬆弛法(SOR)則令 ,其中 用已經鬆弛過的分量 ()計算。
當 ,它就是 Gauss–Seidel; 稱為欠鬆弛, 稱為超鬆弛。名稱並不保證超鬆弛一定更快。
能量與收斂性
現在假設 是實對稱正定矩陣。那麼 ,解 唯一,而且
梯度為 。固定其他分量時, 是這個二次函數沿第 個分量的唯一最小點。SOR 朝它走比例 的距離,也可能越過它。
引理 1.7.2
(一次鬆弛分量更新的能量變化)
對當前向量 ,令 ,則第 個分量的 SOR 更新為 ,而且
證明
(沿一個分量展開二次函數)
對 ,由 對稱得 。代入 得 ,即所述之值。
係數 恰在 時為正,並在 (精確的分量最小點)時最大。
定理 1.7.3
(對稱正定系統的 SOR 收斂性)
若 實對稱正定且 ,則從任意初始向量出發,SOR 都收斂到唯一解。
證明
(每輪嚴格下降與緊緻性)
引理說明每次更新都不會增加能量誤差。令 為一整輪把誤差 映到新誤差的線性映射。每個非零誤差在整輪之後能量都嚴格下降:否則上式中的各平方項都為零,每個分量均不變,故原向量滿足 ,與 可逆矛盾。在能量範數 的緊單位球面上,連續函數 因而有小於一的最大值 。於是 。此證明未給出實用的 ,也沒有找出最優的 。
證明透視
由單一分量的下降到一致收縮
引理只給出逐個分量的不增;證明分兩步把它加強。第一步是整輪嚴格下降。若一輪沒有損失能量,由於 ,該輪遇到的每個梯度分量都為零,於是沒有分量移動,而這些分量正是起始誤差的 的分量。可逆性於是迫使 。對稱性較早已用上,使 成為 的梯度;正定性給出 和範數 。第二步是一致性。單是每個 都嚴格下降,比值 仍可逐漸逼近一。由於 是線性的,比值只依賴方向,而緊單位球面上的連續函數取得最大值,所以 。在 時第一步失效,這正是排除邊界的原因。
完成一輪更新
例題 1.7.4
(比較兩種鬆弛參數)
令 、。首個對角元為正,行列式為 ,故 正定;精確解為 。從 出發,Gauss–Seidel 先得 ,再用新值算出 。
若 ,第一分量變為 ;用此新值計算第二分量的暫定值 ,鬆弛後得 。兩個序列均在定理條件下收斂,但只比較第一步不能斷定哪一個先達到指定容差。
常見錯誤
(在一輪之後才鬆弛,而非在一輪之中)
SOR 在計算下一個分量之前便鬆弛當前分量。把完成的 Gauss–Seidel 向量鬆弛為 是另一種方法。在上例取 ,它給出 ,而 SOR 給出 :SOR 的第二分量已經看到鬆弛後的第一分量。
例題 1.7.5
(觀察一輪中的能量下降)
對同一方程組,。在從 出發的 Gauss–Seidel 一輪中,第一次更新有 、,引理預測下降 ;確實 。第二次更新從 出發,、,預測下降 ,直接計算亦得 。能量誤差由 降至 ,一輪內約縮小為原來的 倍。
例題 1.7.6
(邊界 保持能量)
取 及相同數據,第一分量變為 。第二分量的暫定值為 ,故 。一輪後迭代為 ,而
每次更新都把分量對該方向的最小點作反射,因子 為零,能量毫無損失,儘管矩陣正定。收斂定理採用開區間,正是為了排除這種情況。
反例模式
正定性不能挽救任意參數
對一維方程 ,SOR 的誤差滿足 。若 ,非零誤差永遠交替變號;若 ,誤差絕對值增大;若 ,迭代不動。因此正定性本身不能保證任意參數下收斂。
嚴格對角佔優是某些定常迭代常用的充分條件,但不是上述定理的必要前提。例如 的首個對角元及行列式 均為正,所以正定;第一行卻不對角佔優。另一方面,更新量小並不單獨證明誤差小。
常見錯誤
(因更新量小而停止)
對純量方程 ,取 、,第一次更新的大小是 ,誤差卻仍是 ; 輪後誤差為 。相鄰兩輪變化微小,可能只反映 很小或收縮很慢,並不代表接近解。應檢查適當縮放的殘差,並設定迭代次數上限。
練習與解答
快速檢查
(計算例子的第二輪 Gauss–Seidel。)
從 出發,每個新分量一算出便立即使用。
解答 · 答案
從 出發,新分量依次為 與 。
快速檢查
(對 取 、,求前兩步。)
誤差每步乘以 。
解答 · 答案
,。誤差因子是 ,因此交替而收斂。
快速檢查
(對 求 Jacobi 迭代矩陣及譜半徑。)
Jacobi 矩陣是 。
解答 · 答案
,其特徵值滿足 ,故 。它雖不嚴格對角佔優,Jacobi 仍收斂;充分條件不成立不等於發散。
快速檢查
(為甚麼證明不能涵蓋 ?)
看看引理中的係數。
解答 · 答案
能量下降係數為零,嚴格下降與一致收縮的論證都失效。一維反例和上面保持能量的一輪更說明邊界處確實可能不收斂。