為甚麼改變 Gauss–Seidel 的步長?
設 太大,不宜直接分解,而 是實對稱正定矩陣。Gauss–Seidel 每次改變一個座標,並立即使用剛算出的新座標。逐次超鬆弛法(SOR)把每次座標修正乘上一個倍數。倍數大於一可能使迭代更快,也可能走過頭。我們會證明,哪些正倍數能保證對每個對稱正定系統收斂;這並不說明對某個特定矩陣哪一個最快。
以下假設 對稱正定、,並使用精確算術。因此 ,且解 唯一。寫 ,其中 為對角部分, 分別為嚴格下、上三角部分;對稱性給出 。
定義 7.2.1
(參數為 的 SOR 掃描)
在第 次掃描開始時,向量為 。依次更新座標 :
殘差 是以已部分更新的向量計算的。 稱為欠鬆弛; 稱為超鬆弛。
當 ,這就是 Gauss–Seidel:新座標令當下該行殘差為零,但之後更新其他座標可能再次改變它。
把各座標方程合起來,可得
左邊的矩陣是對角元素為正的下三角矩陣,所以每次掃描均有定義。改變座標順序會改變 ,因此也會改變方法。
最小化一個二次函數
定義 7.2.2
(系統的能量)
方程組 的能量為
由 和對稱性,
等號只在 成立。因此解方程組等同於最小化此二次函數。若目前部分更新的向量是 ,只把第 個座標改變 ,展開得到
設 ,沿該座標使函數最小的改變為 。SOR 則取 。
引理 7.2.3
(一次鬆弛座標步的能量變化)
設 、、 及 ,則
證明
(代入鬆弛步)
上面的展開即 。代入 ,
由於 ,;代入即得第二個形式。
當 ,每一步都令 下降,除非當前殘差已為零。超鬆弛會跨過該座標的最小點,但不會走得太遠而失去能量的下降。單有下降仍不足以證明收斂到解;還須排除在離解很遠的地方停滯。
定理 7.2.4
(正定矩陣的 SOR 收斂定理)
若 是實對稱正定矩陣,且 ,則 SOR 從任意起點收斂至 。此區間是對所有正定矩陣的統一保證:若 ,即使在一維正定系統,也存在使迭代不收斂的起點。
證明
(由能量下降到完整殘差趨零)
令 表示第 次掃描更新首 個座標後的向量;故 ,。令 為第 次座標改變。把能量恆等式對所有座標及掃描求和,再用 ,得到
因此每個 。固定 ,更新前該座標的殘差等於 ,也趨於零。部分更新的向量與 只相差之前有限個座標改變,而這些改變均趨於零。由線性映射 的連續性, 的每個分量都趨於零。因 是固定有限矩陣,
此論證使用固定的有限 和固定的 ;它沒有給出適用所有正定矩陣的統一收斂速度。必要性部分就是下文端點一節的一維計算。
證明從未說明一次掃描把誤差縮小固定倍數,而是從有限的能量預算中取得收斂,詳見下文。
證明透視
能量預算從何而來
關鍵一步是把能量恆等式對每個座標步求和。單有單調下降,能量仍可停在 之上;伸縮求和則顯示各步平方的總和有限,因此步長本身趨於零。兩個假設使這個和有限:正定性令 以 為下界,而 令係數 為正。在 ,係數為零,能量預算不提供任何資訊。
其餘步驟把小步長化為小誤差。除以 ,每一步就變成更新前的殘差。每個這樣的殘差都是 的分量,在部分更新的向量而非 處計算; 有限,才能吸收中間有限個各自趨於零的步。最後一步用固定的逆矩陣 由殘差過渡到誤差。
算例:追蹤最新座標
例題 7.2.5
(一次 Gauss–Seidel 掃描及其能量)
取
矩陣正定,因為對非零 ,。當 ,座標方程為
第一次掃描得 ,第二次得 。若在第二個方程使用舊的第一座標,就是 Jacobi 步,而不是這裏的掃描。事實上,,其不動點為 ,誤差每次掃描乘上 。故 、,與精確解一致。
能量印證了引理。此處 。第一次掃描的兩個殘差為 與 ,係數 ,故兩次下降為 與 。確實 ,。最小值為 ,所以一次掃描後仍有能量差 。
例題 7.2.6
(取 的超鬆弛)
同一系統及起點下,第一座標改變 。第二殘差要使用此新值,故為 ,第二座標改變 。第一次掃描得到 ,不是 。
引理中的係數現為 ,所以兩次能量下降為 與 ,合共 。直接代入得 ,與此一致。掃描結束時的殘差為
定理保證收斂,但只看第一次掃描不能判定這個選擇長遠是否更快。
端點及假設為何重要
例題 7.2.7
(一維情形的端點)
對一維方程 ,即 、,SOR 為 ,故 。若 且 ,迭代值永遠交替變號,而能量 不變,與引理中的零下降一致;若 ,迭代值不動;若 或 ,則 ,其絕對值增長。這證明上述統一保證的必要性。
正定性也重要:沒有它,二次函數未必有下界,能量證明便不適用。對角元為正並不能代替正定。
反例模式
對稱且對角元為正並不足夠
聲稱:對每個對角元為正的對稱矩陣, 的 SOR 都收斂。取
矩陣對稱且對角元為正,但 ,所以並非正定, 沿 無下界。掃描為 、。由 開始,第二座標為 ,迭代無界,儘管唯一解是 。定理需要的是正定性,而不只是對角元為正。
定理亦不保證有限精度的實作可達任意小誤差;捨入及停止準則需另行分析。
常見錯誤
(以舊座標計算殘差)
第 個座標的殘差必須在部分更新的向量處計算。若用掃描開始時的值,便成了 Jacobi 式的步,其能量變化不受引理描述;在算例中,第一次掃描後會得到 ,而非 。
常見錯誤
(把區間當作最佳參數的建議)
定理只說 中每個 都收斂,並沒有說較大的 較快,也沒有說對某矩陣哪個 最快。接近任一端點的參數可能很慢,座標次序亦影響表現。
練習與解答
快速檢查
(對 ,由 出發,取 。求首兩個迭代值及第 步的精確誤差。)
解答 · 答案
更新式為 。故 、,不動點為 。減去不動點可得 。
快速檢查
(在上述二維例子中,求第一次 Gauss–Seidel 掃描後的殘差。為何第二分量為零,第一分量卻不是?)
解答 · 答案
在 ,,故 。第二步使用新第一座標,使第二行成立;但該步亦改變已修正過的第一行。
快速檢查
(設 對稱正定,。若一次完整 SOR 掃描不改變 ,證明起始向量解 。)
解答 · 答案
每次座標更新的能量變化均非正;由能量恆等式中嚴格正的係數,總和為零表示每次座標改變均為零。每個更新前殘差亦為零。因為座標完全沒有改變,這些殘差正是起始向量的 各分量,故起始向量為解。