善用最新數據
大型線性系統未必對稱或正定;這時不能直接使用 SOR 的能量論證。我們改為利用 Gauss–Seidel 在一次掃描中使用新數值的次序,逐行控制誤差。
定義 7.3.1
(Gauss–Seidel 掃描)
設 是有限維實方陣,所有 ;固定未知數次序,並假設精確算術。把 分成對角、嚴格下三角及嚴格上三角部分 。由任意 開始,每次掃描依次計算
即 ,其中 。
右邊下標較小的值在本次掃描中已更新。因為 是對角元素非零的三角矩陣,即使 奇異,每次掃描仍有定義。要保證收斂,還須證明解存在且唯一。
逐行構造判據
定義 7.3.2
(Sassenfeld 逐行數)
按相同的更新次序定義非負數
較早更新的座標,其貢獻乘以已求得的相應界。這稱為 Sassenfeld 判據,是充分條件,而非所有收斂系統的完整刻畫。
定理 7.3.3
(Gauss–Seidel 逐行收斂判據)
若 ,則 可逆,且對任意初值,Gauss–Seidel 收斂至唯一解 。每次掃描滿足
此外,對 ,可計算的相鄰迭代差給出
證明
(沿掃描的收縮)
比較任意兩個起點 各掃描一次,設 。第一行的更新式給出 。假設對所有 已有對應的 界,則第 行取絕對值並代入這些較早座標的界,得到
歸納可得
此論證尚未假設解存在。若 ,則 ,故 ,於是 。由 得 ;方陣核為零即代表可逆。因此 存在且唯一,並為 的不動點。取 反覆使用收縮界,即得誤差界及收斂。
令 。收縮界給出 ;由迭代收斂,。取範數並求等比級數,即得相鄰差的誤差界。這是精確算術下的保證;浮點計算另須控制捨入誤差。
證明很短,但每個假設都有確定的用處。
證明透視
沿掃描次序建立誤差界
關鍵一步是按計算次序界定各座標。在第 行,已更新的座標 以 出現,歸納已把其大小界為 ,而不只是 。善用最新數據的好處正在於此,這亦是 依賴次序的原因。尚未更新的座標 以 出現,以 為界。對角元素非零只用於除以 ;它使 即使在 奇異時仍有定義。
第二步由收縮性推出解的存在與唯一,而非事先假設。對 ,恆等式 表示 是右端為零時掃描的不動點,所以 迫使 。至此 才可作為比較用的不動點。相鄰差界以伸縮級數收尾:它用剛證得的收斂,把 寫成其後所有步的和,再用 求和 。
嚴格行對角優勢是充分條件
推論 7.3.4
(嚴格行對角優勢給出判據)
若每行皆滿足 ,令
則在任何次序下 ,因此對任意右端及初值,Gauss–Seidel 均收斂。
證明
(對逐行數歸納)
每行嚴格優勢給出 。歸納地,若較早的 ,則它們均不超過一,代入定義得
第一行開始歸納,因為 。因此 。方程與未知數同時重排時,嚴格行對角優勢保持不變,所以結論對任何次序都成立。
不要求對稱的嚴格行對角優勢,既保證 Gauss–Seidel 收斂,也保證 Jacobi 收斂;但 未必是精確的收斂速率。嚴格不等式不能放寬為每行取等號。
反例模式
弱對角優勢並不足夠
聲稱:若每行都有 ,Gauss–Seidel 便收斂。取
兩行都以等號滿足弱不等式,且 、,故 。矩陣奇異,系統亦不一致,因為 不能同時等於 和 。掃描為 、,所以 每次掃描增加一,迭代無界。聲稱不成立;定理需要 ,而嚴格優勢正好提供這一點。
例:行對角優勢失敗,判據仍成功
例題 7.3.5
(行對角優勢失敗而判據成立)
考慮
第三行的 ,故非嚴格行對角優勢;Jacobi 無窮範數檢驗也因第三行比值 而失敗。可是依所列次序,
因此定理保證唯一解和任意初值的收斂。實際上 。由 開始,第一次掃描得到
第二行已用新的第一個值,第三行則用了前兩個新值。實際誤差的無窮範數為 ,小於定理的界 。Jacobi 的某個範數檢驗失敗,並不代表 Jacobi 必定發散,更不能由此斷定 Gauss–Seidel 發散。
例題 7.3.6
(兩次掃描後的可計算停止界)
由 繼續同一系統。第二次掃描給出
相鄰差為 ,無窮範數為 。由於 ,可計算的界為
實際誤差為 ,範數 。由第一次掃描得出的收縮界則較緊:。兩個界都正確。相鄰差界不需知道 ,但因子 使它在步長仍大時偏於保守;當相繼迭代已很接近時,它才成為有用的停止檢驗。
檢驗失敗意味甚麼?
例題 7.3.7
(判據失敗而迭代收斂)
取
此時 、,故 ,判據不適用。然而 ,而誤差更新滿足
由於 且 ,任意初值下兩個分量均趨近零。第一個分量可在首輪變大,但迭代仍然收斂。
常見錯誤
(把判據失敗當作發散)
判據只是上界。 時這個界不提供任何資訊,正如上例: 而迭代收斂。要證明發散需另作論證,例如找出一個每次掃描都增長的誤差分量。
常見錯誤
(以為矩陣可逆便保證掃描有定義)
可逆不能保證原次序下的掃描有定義;例如 可逆,對角元素卻是零。重排方程可能處理零對角,但會改變迭代與判據,不能假設任意次序都適用。
練習與解答
快速檢查
(對 計算判據;它能否保證收斂?)
解答 · 答案
,。因此 ,定理適用於任意右端和初值。
快速檢查
(將上面三階例子的方程和未知數均反序排列,計算新判據。)
解答 · 答案
新矩陣為 ,依次得 、、。最大值超過一;原次序通過而此處未通過,但後者本身仍不能決定收斂與否。
快速檢查
(已驗證精確算術判據 ,且 。估計誤差。)
解答 · 答案
誤差不超過 乘相鄰差,即 。此界沒有自動計入浮點捨入。
快速檢查
(舉出可逆而 Gauss–Seidel 在所列次序發散的系統。)
解答 · 答案
取 、。行列式為 ,但更新式給出 及 ;第二分量初值非零時序列無界。唯一解並不保證此迭代收斂。