動機
對大型稀疏線性系統,存儲稠密分解可能比矩陣乘向量昂貴得多。迭代方法改用矩陣–向量乘積構造一系列近似。共軛梯度法利用此前收集的資訊選擇新搜索方向,而不是在每步應用一個固定的定常迭代矩陣。
它的特殊結構依賴矩陣性質。對實對稱正定矩陣,求解 等價於最小化嚴格凸二次函數。共軛梯度法在矩陣給出的能量內積下選擇兩兩正交的方向,並在逐漸擴大的 Krylov 空間中給出最佳近似。這些是精確算術定理;實際實現還需處理停止、尺度和捨入誤差。
能量視角
定義 3.2.1
(對稱正定性與能量範數)
令 對稱正定(SPD):,且對每個非零 有 。定義
唯一解 是 的唯一最小點。事實上,對 ,
殘差 是 的負梯度,滿足 。
小殘差和小解誤差是不同結論。在 Euclidean 範數下,;病態矩陣可能放大殘差。能量範數則依 對不同方向賦予不同權重。因此,能量誤差最小化定理不能被說成每一步的每個 Euclidean 誤差分量都下降。
定義 3.2.2
(Krylov 空間與共軛性)
從 和 出發,定義
非零向量 若在 時滿足 ,則稱它們 共軛。正定性使 共軛族線性無關。仿射空間 包含將次數小於 的 的多項式作用於初始殘差所構造的全部修正。
算法及其保證
若 ,則 已經是解,不需要迭代。否則令 。對 ,只要 ,便計算
若 則停止;否則取
矩陣通過 使用,不必構造 。終止之前, 正定且搜索方向非零,故分母為正;下文歸納證明會證明方向非零。精確解已得到時,停止檢查可避免後續零分母。
定理 3.2.3
(正交性、最小化與有限步終止)
在精確算術中,終止之前殘差 兩兩 Euclidean 正交,方向 兩兩 共軛。若未提前終止,經過 步後,
並且 在 上唯一最小化 。算法至多經過 步到達精確解。
定理 3.2.4
(條件數收斂界)
令 為 的極端特徵值,且 。在精確算術中,對終止之前每個 ,
若 , 是單位矩陣的正數倍,共軛梯度法至多一步終止。上式是最壞情況界,不是說實際誤差每步都恰好乘以該因子。
概念視角分析
同一個迭代值:最優多項式
記 ,則 。 中每一點的誤差都是 ,其中 是次數至多為 、且 的多項式;反過來,每個這樣的多項式都會出現。因此 就是在此約束下使 最小的多項式所對應的點。在標準正交的特徵基下,設 ,這個量等於 。所以共軛梯度法是在 的譜上的多項式逼近問題:約束是 ,並要求 在 中有份量的特徵值處很小。
短遞推為何有效
證明
(正交性與能量最小化)
我們同時歸納這些關係。第 步的不變量是: 非零且兩兩 共軛; 與先前方向正交;;所有已構造的 屬於 。初始時 ,共軛性及與先前方向的正交性為空條件,,且兩個向量均在 中。特別地 。假設第 步的不變量成立。當 ,由 得 。因此所選步長滿足
對於 ,歸納假設給出 。每個先前殘差是相應方向及前一個方向的線性組合,所以 也與 正交。
更新也保持真實殘差恆等式:。為了檢查下一方向的共軛性,使用 。當 ,殘差正交性給出 ,且 。當 ,
所選 使這兩項在 中相消。當 ,由於 ,所以 。歸納完成,並證明每個分母在終止前為正。
Krylov 歸屬關係同樣由歸納得到:;若 ,則 ,且 。前 個方向線性無關,又位於維數至多為 的 ,所以該空間維數為 並由它們生成。所以 ,且 。對任意 ,
內積的勾股恆等式說明,給 加上任何非零 都會增大能量誤差,故最小點唯一。非零共軛方向至多有 個;經過 步後,殘差與整個 正交,因而為零。若更早為零,則已得到精確解。
證明透視
為甚麼只需要前一個方向?
一般投影方法可能需要消去沿所有先前方向的分量。這裏 把較舊方向的共軛條件轉化為殘差正交性。只有最近一個方向需要顯式的 修正。這種簡潔來自對稱性與相互配合的不變量,並非任意迭代方法的共同性質。
證明
(從 Krylov 最小值到譜界)
令 。由於 , 中任意修正都給出 形式的誤差,其中 次數至多為 且 ;反過來,每個這樣的多項式都給出 Krylov 空間中的修正。在標準正交特徵向量基下寫 。由 ,且譜位於 中,
最小化定理對每個符合條件的多項式給出 ,所以任取一個即可得到上界。當 ,取
其中 。在譜區間上分子的絕對值至多為一,且 。對 ,寫 ,則 。在分母參數處,,因此分母倒數至多為 ,證明該界。特徵值聚集或初始誤差在困難特徵方向上沒有分量時,譜區間界可能較保守。事實上,若 只在 個不同特徵值 的特徵空間上有非零分量,則 滿足 。Krylov 最優性因而迫使算法至多 步精確終止,也可能更早。這個更精細的結論同樣依賴精確算術。
例題
例題 3.2.5
(對角系統上的兩步迭代)
取 、、。於是 ,且
因此 ,並滿足 。下一步 ,得到
殘差也正交:。精確兩步終止說明了維數定理;浮點算術中,兩步後計算的殘差未必恰好為零。
例題 3.2.6
(重複特徵值可能提前終止)
設 , 和 任意。若 ,則 ,且 。不論維數多大,一步就能解出系統。更一般地,若 Krylov 空間提前包含所需解修正,算法可能早於 步終止;單純統計不同特徵值並不是浮點算術下的迭代保證。
例題 3.2.7
(能量誤差與殘差)
取 ,假設候選誤差為 。則 ,、、。另一個誤差 的殘差範數也是一,但 Euclidean 誤差和能量誤差都為一。殘差相對於譜的方向很重要;未經尺度調整的一個殘差範數不能直接報告逐座標誤差。
反例模式
對稱但非正定並不足夠
取 、、。系統有唯一解 ,但 給出 ,所以共軛梯度法第一步就沒有定義。此二次函數不定且無下界;該解是鞍點而非最小點。非奇異性和對稱性不能替代正定性。
常見錯誤
常見錯誤
(將有限步終止當作浮點保證)
正交性、精確零殘差及 步終止都使用精確算術。捨入可能破壞共軛性,也可能使遞推更新的殘差與顯式計算的 不同。實際停止準則應考慮尺度及殘差與誤差的差別;精確證明本身不能提供通用浮點停止容差。
常見錯誤
(對任意非對稱系統套用定理)
這裏的算法與能量論證要求 對稱正定。其他 Krylov 方法處理其他矩陣,但具有不同不變量和收斂結論。預條件也需要自己的假設:即使相關矩陣都是 SPD,左預條件後的算子在普通 Euclidean 內積下也未必對稱。
總結
共軛梯度法通過短遞推組合矩陣–向量乘積。在精確算術中,殘差正交與 共軛性給出每個 Krylov 空間上的能量最小點,並保證至多 步終止。譜界解釋條件數的作用,實現及捨入行為則需另行分析。
練習
快速檢查
(取 、、。計算第一次共軛梯度步,包括 和 。)
從 開始。
解答 · 答案
,所以 。因此 ,。
快速檢查
(取 、、,已知第一步為 、。求 和 ,並驗證 。)
利用 。
解答 · 答案
,。它與 的 內積為 。又 ,所以 。因此 ,即精確解。
快速檢查
(某 SPD 矩陣的 。計算 步時能量界的因子,並解釋為何它未必是實際誤差比。)
先算比值 。
解答 · 答案
此時 ,所以上界因子為 。實際比值取決於特徵值、初始誤差和精確算術;該不等式對具體實例不一定達到等號。
快速檢查
(令 ,其中 ,殘差為 。求相應誤差 並解釋 的作用。)
利用 。
解答 · 答案
由 ,誤差為 。殘差範數為 ,但誤差範數為一。小特徵值可以使很小的殘差對應大得多的誤差。