動機
將邊值問題離散化只是計算的一半:所得方程組仍須求解。網格很大時,明確求逆既浪費儲存空間,也忽略了差分模板的稀疏結構。迭代法則反覆利用局部數據改善近似。必須區分有限方程組的精確解和微分方程的解:我們可以把一個過粗甚至錯誤的離散方程組求得非常精確,卻仍得不到準確的連續解。
Jacobi 法在一次掃描中只用上一輪的值;Gauss–Seidel 法一算出新值就使用它。逐次超鬆弛法(SOR)則沿這個修正走一部分或超過一步。我們先從 Poisson 方程組建立算法,再對任意對稱正定矩陣以能量證明收斂。
定義
考慮 上的 和已知兩端邊界值。令 , 近似 。將中央差分式乘以 得
定義 3.6.1
(Gauss–Seidel 與 SOR 掃描)
把已知端點項移到右邊,便得 : 的對角元為 ,相鄰非對角元為 。更一般地,若矩陣的對角元非零,一次按索引遞增順序的 Gauss–Seidel 掃描設定
SOR 取 ,其中 已使用鬆弛後的新值。 是 Gauss–Seidel, 是欠鬆弛, 是超鬆弛。每個座標各更新一次稱為一輪掃描;改變次序會改變迭代過程,但方程組不變。
定義 3.6.2
(離散能量與殘差)
若 對稱正定,定義離散能量 和殘差 。唯一能量極小值點 滿足
因此能量差以 -範數衡量代數誤差。同時把 和 乘以相同正數,解與迭代不變,但能量和殘差的尺度會改變。
定理/命題
定理 3.6.3
(SOR 的能量下降與收斂)
設 是實對稱正定 矩陣,,且 。對任意初始向量,以固定座標次序循環進行 SOR,均收斂至 的唯一解。若某次更新時的當前殘差分量是 ,則該次能量下降量為
命題 3.6.4
(殘差與代數誤差)
若對稱正定矩陣 的最小特徵值是 ,則任何近似 滿足
這些界限只比較有限線性方程組的解,不包含離散化誤差。
證明或證明思路
證明
(能量的逐座標下降)
固定除第 個以外的座標,沿 的能量為二次式 。它在 達到最小;SOR 取 。代入即得上述下降量。正定性保證 ,而能量有下界。把所有更新的下降量求和,可知各次更新所見殘差分量的平方可加,因此趨於零。
現在要把每次更新時的殘差,連到每輪開始時的殘差。每次只改變一個座標,其增量為 ,所以各次增量趨於零。每輪只有固定的 次更新,而 固定,故同一輪開始時與任何更新時的殘差之差趨於零。每個座標都在該輪被訪問,因此輪首殘差的每個分量均趨於零。由固定矩陣 可知輪首向量收斂至 ;中間向量亦收斂至同一極限。證明並沒有假設每個誤差分量每次都下降。
證明透視
正定性與參數範圍各自的作用
證明三次用到正定性,每次作用不同。它給出 ,所以每次座標更新都有定義,而沿 的能量是開口向上的拋物線。它令 以 為下界,所以非負下降量之和有限。它亦令 可逆,所以殘差趨於零便迫使迭代趨於 。條件 只用一次:它令因子 為正,於是有限的下降總和控制 ;在 時下降量為零,論證便得不到任何結論。對稱性使 正是 的梯度;對非對稱矩陣, 的梯度是 ,下降恆等式不再描述該更新。關鍵一步是由更新當刻的分量過渡到整個殘差。可加性只控制正被更新的座標在更新當刻的殘差分量。由於每次更新只把一個座標移動 ,而每輪只有 次更新,殘差在一輪內幾乎不變,這些分量便拼合成輪首的完整殘差。
殘差命題只需要對稱矩陣的譜定理。
證明
(殘差的譜界)
令 ,則 。對稱矩陣的正交對角化給出 ,以及 ,即得第二個命題。
三種誤差必須分開。掃描使有限方程組的能量下降;要由殘差界定代數誤差,還須考慮矩陣尺度和最小特徵值。要把 與連續解的網格取樣比較,則另需相容性與穩定性的論證。
例題
例題 3.6.5
(一次順序掃描)
令 、,由 出發。Gauss–Seidel 先算得 ,再用這個新值算得 。同時更新的 Jacobi 法第一輪則得到 。直接解方程得 ,兩者第一輪都不是精確解。
概念視角代數
把一輪掃描看成固定的矩陣分裂
寫 ,其中 為對角、 為嚴格下三角、 為嚴格上三角。按遞增次序的一輪 Gauss–Seidel 恰為 ,故誤差滿足 ;SOR 則換成 。對任何初值都收斂,等價於譜半徑小於一。在上例中 ,所以第一輪之後每輪誤差乘以 ;確實 。
例題 3.6.6
(一次超鬆弛掃描)
同一方程組和初值,取 。第一個未鬆弛候選值為 ,故鬆弛後是 。第二個候選值使用這個新值,為 ;由零鬆弛後得到 。第一次更新的殘差為 ,能量下降量為 。直接計算也有 、。
例題 3.6.7
(殘差可能造成錯覺)
對未除以 的一維 Poisson 矩陣,,網格細化時趨於零。若 與相應特徵向量平行,則 。因此相同絕對殘差容許值在較細網格上可能允許較大的代數誤差。方程整體縮放會改變殘差數值,卻不改變迭代;有意義的停止準則須說明尺度和範數。
常見錯誤與細節
常見錯誤
(可用參數範圍不是速度保證)
此處 保證收斂,是因為 對稱正定;它不保證每個參數都比 Gauss–Seidel 快,也不能把證明直接套用到任意非對稱對流矩陣。端點 不能包括:純量方程 從零開始會在 與 之間交替。
常見錯誤
(更新量小不是誤差證明)
單憑更新量小也不能普遍保證誤差小;選極小的 本來就會使每次更新很小。殘差準則應與合適的離散化誤差估計比較,實際計算亦須限制迭代次數。
非齊次邊界值在掃描前應移入 ,而不是當作內部未知數。這裏沒有給出一般矩陣的最佳鬆弛參數。最後,正定性並非證明上的技術細節。
反例模式
Gauss–Seidel 發散的對稱矩陣
聲稱:對每個對角元非零的對稱矩陣,Gauss–Seidel 都收斂。取
它對稱且可逆,解為 。由 出發,第一輪先設 ,再設 ;下一輪得 。一般而言,第二個座標每輪乘以 ,迭代發散。失效的假設是正定性: 的特徵值為 和 ,而 給出 。此時能量 沒有下界,其下降不能推出任何結論。修正後的命題就是定理:對稱且正定。
快速檢查
快速檢查
(Gauss–Seidel 在同一輪更新第二個座標時,使用第一個座標的哪個值?)
解答 · 答案
使用剛算出的新值。對 SOR 而言,這是鬆弛後的新值,不是未鬆弛的候選值。
練習
快速檢查
(從零開始,對 、 進行兩輪 Gauss–Seidel,計算第二輪後的殘差。)
解答 · 答案
第一輪得 ;第二輪得 、。故 :每輪最後第二個方程恰好成立,但第二座標改變後第一個方程未必仍成立。
快速檢查
(對純量方程 ,推導 SOR 的誤差遞推式,並確定何時對所有初值收斂。)
解答 · 答案
候選值恆為 ,因此 ,誤差滿足 。對所有初值收斂當且僅當 ,即 。
快速檢查
(設 、。對 計算殘差、能量差和命題中的能量上界。該上界對此向量是否取等?)
解答 · 答案
,,而上界為 。界限有效,但對此向量不取等;若殘差落在最小特徵值 的特徵空間,則可取等。