動機
消元法通過矩陣分解求解。對於大型稀疏矩陣,因子的儲存量可能遠超原矩陣的非零項,因此值得考慮只用矩陣向量乘積及簡單方程求解來逐步改善近似。不過,每一步便宜還不夠;若收斂太慢,總成本仍可能很高。
定常方法反覆作用同一個誤差傳播矩陣;Krylov 方法則在矩陣和初始殘差生成的逐漸擴大的空間中搜索。對稱正定系統的共軛梯度法把第二種觀點與能量極小化聯繫起來。預條件通過一個較易求解的輔助系統改變搜索的幾何。
定義
定義 7.1.1
(誤差、殘差與定常分裂)
設 ,實矩陣 非奇異,解為 。定義誤差 及殘差 。若 且 非奇異,定常迭代為
逆矩陣是分析記號,實施時解關於 的方程。寫 ,分別表示對角、嚴格下三角及嚴格上三角部分。Jacobi 取 ;Gauss–Seidel 取 。迭代矩陣分別為 和 。這些定義要求所選對角或三角系統可解。
定義 7.1.2
(譜半徑、正定性與能量)
譜半徑為 ,最大值遍歷全部複特徵值。若實對稱矩陣對所有非零向量滿足 ,稱為正定。此時能量範數及能量函數為
定義 7.1.3
(Krylov 空間與 -共軛)
令 ,當 定義
若 ,稱兩個方向 -共軛。這是能量內積中的正交,不能與普通點積為零混淆。
定理/命題
定理 7.1.4
(定常收斂及範數證書)
定常迭代對每個初值都收斂到 ,當且僅當 。若某誘導矩陣範數滿足 ,則
嚴格按行對角佔優給出 Jacobi 的無窮範數證書
定理 7.1.5
(共軛梯度的極小化與收斂)
若 對稱正定,精確算術共軛梯度法在第 步得到 在 上的唯一極小點。非零搜索方向彼此 -共軛,殘差彼此普通正交。若沒有更早結束,最多經過矩陣維數那麼多步達到解。
設最小最大特徵值為 。當 ,
若 ,非零初始殘差只需一步。正交及有限步結束的結論均針對精確算術。
概念視角結構
迭代也在選擇幾何
定常方法控制同一個誤差矩陣的重複作用;CG 在擴大的仿射空間中選能量範數最優點;預條件用便宜的正定度量改變幾何。成功的分裂、小殘差及有利譜分佈因而相關,卻是不同證據。
因子二使小步數時的界可能保守;它也沒有利用特徵值聚集所帶來的優勢。反過來,正定本身並不能保證任意定常分裂收斂,後面的反例會具體說明。
證明思路或證明
矩陣冪與壓縮
證明
(Jordan 塊與幾何級數)
誤差遞推給出 。若全部特徵值模小於一,複 Jordan 形式中每個塊的冪都趨零。非零特徵值的塊元素是固定次數的 的多項式乘特徵值冪,指數衰減勝過多項式增長;零特徵值塊是冪零矩陣,最終為零。因此 。反之,對所有實初始誤差收斂,意味著 每一列趨零,故作用於複向量也趨零。若存在模至少一的特徵值,其特徵向量立刻產生矛盾。這個證明不要求矩陣可對角化。
範數界由次乘性得到。令 ,有 。收斂給出 ,以幾何級數估計便得後驗界。Jacobi 的無窮範數恰是各行非對角絕對值之和除對應對角絕對值的最大值。範數證書不成立並不證明發散,只表示這個充分論證無法決定。
共軛梯度短遞推為何有效
證明
(對短遞推作歸納)
從 、 開始。殘差為零便停止,否則使用
正定性保證非零方向的分母為正。歸納假設當前方向生成 且彼此共軛,而 與更早的方向正交,於是 。所選 使新殘差與 正交;共軛性又使它與所有更早方向正交。
對 ,利用 ,右邊兩個殘差都在 ,故 。對最後一個方向,
所選 恰使這兩個貢獻抵消,所以新方向與全部舊方向共軛。新殘差屬於 ,又與 正交;若它非零,便提供新的獨立向量,擴大後的方向生成下一個 Krylov 空間,歸納閉合。這也證明殘差彼此正交。
能量梯度為 。殘差與搜索空間正交,正是嚴格凸二次函數在仿射空間上極小化的一階條件;能量恆等式保證唯一性。非零共軛方向線性無關,數目不能超過維數,所以精確算術下有限步結束。
證明透視
三個不變量,兩個係數
歸納同時維持三個命題:方向 生成 、它們兩兩 -共軛,以及 與 正交。每個係數恰好強制一個新的關係。步長 是唯一使 的選擇;與更早方向的正交則由共軛性推出。 的對稱性正用在這裏:把 讀成 。係數 只強制與 共軛。
不顯然的一步,是與 的共軛性為何無需額外代價。每個 都是 中兩個殘差之差,而 與整個空間正交。 把 映入 這個 Krylov 性質,令兩項遞推可以取代完整的 Gram–Schmidt 正交化。正定性用了兩次: 使 有定義,而 的嚴格凸性使正交條件對應唯一極小點。歸納之所以閉合,是因為非零的 屬於 卻與 正交,恰好把生成空間擴大一維。
特徵值如何控制誤差
證明
(平移縮放後的 Chebyshev 多項式)
因為 ,仿射 Krylov 空間中任一點的誤差都可寫為 ,其中 且 。極小化性質結合正交對角化給出
當 ,取
分子在譜區間絕對值不超過一。對 ,Chebyshev 遞推給出 ,其中 。代入分母的參數,得 ,因此分母倒數不超過 ,即所需界。若 ,譜定理給出 ,一步便解出。這個界是上限而非精確的迭代次數預測。
預條件改變能量幾何
選容易求解的對稱正定 。令 ,變換系統為
變換後仍對稱正定。在其中應用 CG,可轉寫為不需要平方根的預條件遞推:解 ,用 、,初始方向為 。相關條件數屬於 ,不能隨意改成一般不對稱的書寫形式 的歐氏條件數。好的預條件在簡單求解與有利譜結構間權衡。取 雖可一步收斂,卻要求先解決原問題,通常沒有算法價值。
停止判據需說明尺度及意義。絕對殘差容差適合右端單位固定的問題,相對於右端範數的容差便於比較縮放後的系統;右端為零或很小時則需絕對替代。兩者都不能繞過逆矩陣資訊,直接變成解誤差保證。定理中的能量誤差適合分析,但計算過程中通常因不知道真解而無法直接求值。
基本 CG 每步需要一次矩陣向量乘積、向量更新及純量內積,預條件版本另需輔助求解。稀疏乘積成本與非零項數有關,平行運算中的內積通訊也可能主導成本。因此,少幾步不一定總耗時更短。昂貴的預條件分解可能適合多個右端,卻不適合單次求解,需用實際成本判斷。
例題詳解
例題 7.1.6
(一個稀疏二元系統)
設 、,解為 。Jacobi 的 ,。零初值給出 、。Gauss–Seidel 使用剛更新的第一分量,一輪已得 。這只是具體步驟比較,不是兩種方法的普遍優劣定理。
例題 7.1.7
(兩步 CG 的精確計算)
取 、、。第一步 ,,。接著 ,,第二步長 ,得到 。可分別核驗殘差的普通點積為零,以及方向的 -內積為零。
例題 7.1.8
(對角預條件的機制)
對同一系統取 ,求解只是逐分量除法,變換矩陣為單位矩陣,故預條件 CG 一步完成。一般稀疏矩陣只用正對角部分,雖便宜,卻未必得到單位矩陣或良好條件數。例子說明機制,不能保證對角預條件總有明顯收益。
常見錯誤
反例模式
正定不保證 Jacobi 收斂
取三階矩陣,對角為一,全部非對角項為 。特徵值為 ,所以對稱正定。Jacobi 矩陣的對角為零,非對角為 ,特徵值為 。沿全一向量的誤差每步放大 倍。正定假設適用於 CG 定理,卻不能挪作這個 Jacobi 分裂的收斂保證。
常見錯誤
(把小殘差當作小誤差)
界 含有條件資訊。取 、誤差 ,殘差 的範數為 ,誤差範數卻為一,上述界恰好取等。同樣,迭代變化量小,也要有壓縮證書才成為誤差界。
常見錯誤
(把精確算術的 CG 恆等式當作硬件保證)
浮點 CG 會失去精確正交,可能需要超過維數的步數;遞推更新的殘差也可能偏離實際的 。應在合理的停止檢查點重新計算實際殘差;有限步結束定理並非電腦上的步數上限。
總結
定常收斂等價於譜半徑小於一,壓縮範數給出可計算誤差證書。精確 CG 在 Krylov 空間中極小化能量,具有共軛方向及譜收斂界。正定預條件把分析轉移到變換系統。判斷數值停止是否認證原方程,還需條件及有限精度資訊。
練習
快速檢查
(對 ,求 Jacobi 矩陣、無窮範數及譜半徑。若相鄰迭代變化至多 ,求當前誤差的壓縮上界。)
;把非對角元素除以該行的對角元素。
解答 · 答案
,無窮範數為 。特徵值為 ,譜半徑為 。當前誤差不超過 乘變化量,即 。譜半徑雖然更小,卻不能直接替換這個特定範數證書中的 。
快速檢查
(給出 但 的矩陣,解釋其迭代為何仍收斂,以及第一步誤差增長為何不矛盾。)
冪零矩陣的譜半徑為零。
解答 · 答案
取 ,譜半徑為零,無窮範數為二。因為 ,任意誤差至多兩步消失,某些誤差第一步卻會增長。譜判據允許暫態放大,而指定範數中的壓縮估計不允許。
快速檢查
(若正定矩陣特徵值在 ,用定理估計六步 CG 後的能量誤差比。這個界是否斷言等號或有限精度結束?)
時 。
解答 · 答案
,故比值至多 。這是精確算術上界,可能很保守;它不表示等號,也不保證有限精度維持精確殘差及共軛恆等式。
快速檢查
(取 、,求變換矩陣、條件數及非零殘差的精確預條件 CG 步數。為何平方根形式主要用於分析?)
這裏 是對角矩陣。
解答 · 答案
,故 。條件數為一,非零殘差一步解出。實際算法只解關於 的方程並使用 ,無需構造矩陣平方根。