為甚麼不求逆矩陣?
大型最小二乘問題或正則化模型可能產生方程組 :矩陣 的維數很大,但計算它與向量的乘積仍然可行。即使 很稀疏,明確儲存 也可能不可行。共軛梯度法(CG)只用矩陣向量乘法、向量更新和內積來構造近似解,不必儲存逆矩陣。它的保證要求一類特定的矩陣;推導先假定精確算術,再另行討論有限精度。
定義 4.5.1
(對稱正定矩陣與 -內積)
若實矩陣 滿足 ,且對每個非零 都有 ,則稱 為對稱正定(SPD)。對 SPD 矩陣 ,-內積為 ;若 ,則稱 -正交(共軛)。
線性方程組等價於最小化一個二次函數,而這個改寫推動方法的每一步。
引理 4.5.2
(把方程組化為二次最小化)
設 對稱正定,,。則 ,且對每個 ,
因此 是 的唯一最小點,而殘差 是負梯度。
證明
(配方)
由對稱性,,所以 。利用 及 ,
由正定性,除非 ,右邊皆為正。
若每次都只沿殘差移動,就是最速下降法,後續步驟可能抵消先前進展。CG 選取互相 -正交的方向;沿新方向最小化時,不會破壞先前方向上的駐點條件。
遞推公式
從任意 出發,令 、。若 就停止;否則計算
若 就停止;否則令
由正定性,非零方向滿足 ;分母不是可任意調整的參數。殘差遞推來自 ,因此初始化後每一步只需一次新的 乘積。這說法不包括生成或儲存 的成本,也不包括分散式內積所需通訊。
定理 4.5.3
(精確算術下的 CG)
設 對稱正定。停止之前,各方向非零且兩兩 -正交, 與此前所有方向正交。 是 上 的唯一最小點。此方法至多經過 次迭代得到精確解。
證明
(對方向作歸納)
歸納假設 兩兩 -正交,且 與 正交。當 時 ,所以 ; 時也成立。 的導數為 ,在 處為零。並且
若尚未停止,則 非零:否則它與 的內積為零,但該內積等於 。當 時,由 ,再利用 與此前方向正交,可知 ,因為右邊兩個殘差都屬於此前方向的生成空間。當 時,同一遞推與殘差正交性給出 。又 ,故上述 使 ;當 時, 的兩項均為零。歸納完成。
由於 與所述空間的一組基正交, 沿該空間的方向導數均為零;嚴格正定性保證它是唯一最小點。非零且兩兩 -正交的向量線性無關,因此至多有 個方向。若已走過 個方向,殘差與 的一組基正交,必為零。
證明每一步只明確強制一個正交條件,卻得出與所有更早方向的正交性。
證明透視
一次修正換來全部舊的正交性
正定性用了兩次:它使每個步長的分母為正,並把搜尋空間上的駐點變成唯一最小點。對稱性使條件可以任意次序閱讀,於是兩個方向的 -正交只是一個條件而非兩個。關鍵一步是恆等式 :它把 乘以舊方向寫成兩個舊殘差之差。這兩個殘差都位於更早方向的生成空間,而新殘差已與該空間正交,所以新方向自動與除最近一個以外的所有方向共軛;係數 只需消去那一個分量。這就是 CG 只需短遞推、而毋須對已儲存方向做完整 Gram–Schmidt 掃描的原因。論證以計數閉合:非零共軛方向線性無關,至多有 個;與 個線性無關向量都正交的殘差必為零。
例題 4.5.4
(兩個方向,而非兩次獨立猜測)
取 ,,。於是 ,,,得到 、。接著 ,。檢驗得 。由於 ,故 ,得到 ,。確實 。
次迭代只是上界;下例只需一步便停止。
例題 4.5.5
(一步即終止)
取 、、。則 ,,,所以 、。更新殘差為 ,真實殘差 也是零。方法在此停止: 會把 除以 ,產生無意義的方向 ,所以不計算它。提早停止是因為 是 的特徵向量,第一次直線搜尋已到達 。
概念視角代數
CG 是最佳多項式
由遞推式歸納可知,在終止之前,方向 生成 Krylov 空間 。因此 ,其中 是次數至多為 且 的多項式;由引理,CG 選取的正是使 最小的 。若 只在 的 個特徵空間中有分量,以這些特徵值構成的多項式 給出零誤差,故 CG 至多 步便停止,正如上一個例子及 的情況。
此方法從不需要矩陣本身,只需要一個作用該矩陣的程序。
例題 4.5.6
(無需儲存矩陣的正則化算子)
令 ,即列線性相關的單一行,並取 ,於是 對稱正定,儘管 奇異。以 作用它。以 、 求解 。
第一步:,,,,,,。
第二步:,,,。檢驗 。於是 ,,,。直接計算亦得 。
成本、停止條件和假設
對 的 CSR 矩陣,若存有 個條目,一次乘積需要 運算,儲存需要 個陣列元素。CG 保留常數個長度為 的向量,故在單位成本模型下一次迭代需要 運算。實際系統還可能有顯著的同步、記憶體傳輸和預條件器成本。若使用無需明確儲存矩陣的算子,則應用該算子的成本和記憶體取代上述 CSR 數字。精確算術定理只保證終止,並不保證掃描 次很便宜。
常見的實際準則是重新計算真實殘差 ,並在 時停止,其中非負容差依應用選擇。捨入會使遞推更新的殘差偏離真實殘差。殘差小也不自動意味著前向誤差同樣小:由 ,有 ;病態性可以放大誤差。有限精度還可能破壞精確共軛性及至多 步終止的保證。應定期及退出時檢查真實殘差、設定迭代上限;若意外出現非正的 ,應調查算子或數值失效,而不是宣稱收斂。運行中替換遞推殘差會改變後續算法,需要恰當的實作策略。
常見錯誤
(只憑更新殘差停止)
迴圈中的 由 產生,而不是計算 。精確算術下兩者相同;浮點運算中兩者會逐漸分離,真實殘差停滯後,更新殘差仍可能繼續變小。若只因 很小便報告收斂,而退出時不重新計算 ,就可能認證一個未達容差的迭代值。
常見錯誤
(恰好跑 次迭代便停止)
「至多 步」是精確算術下的終止結論。浮點運算中方向會失去共軛性,所以 步後殘差未必為零;當 很大時,本意是憑殘差測試遠早於此便停止。應使用基於殘差的停止準則並配合迭代上限,而不是以維數作為停止準則。
對最小二乘,若 ,則 對稱正定;可用 而不形成 。這可能節省儲存,但正規方程可能惡化條件數,不能因此省略精度檢查。固定的 SPD 預條件器可能改善變換後系統,但構造和應用它均有成本,而且需要相應的預條件遞推。
反例模式
僅有對稱性並不足夠
取 、、。則 ,儘管 ,仍有 ,所以第一個步長就要除以零。這個矩陣對稱且可逆,解為 ,卻是不定的。修正後的假設是正定性,它保證每個非零方向都有 。
練習與解答
快速檢查
(設 、、。比較 和 。)
先求 。
解答 · 答案
解為 ,故 ,但 。這恰好達到上界 。絕對殘差小並不能單獨保證同樣小的誤差。
快速檢查
(證明對任意實矩陣 和 , 對稱正定,即使 的列線性相關也是如此。)
展開 。
解答 · 答案
它是對稱的;對非零 ,有 。當 時第一項可以為零;正則項提供嚴格正性。
快速檢查
(在 的例子中,驗證第二步保留沿 的零方向導數。)
利用殘差遞推及共軛性 。
解答 · 答案
第一步後 。由於 ,有 。 沿 的方向導數是 ,所以仍為零。這正是保留先前進展的機制。
快速檢查
(對 、任意 及 ,CG 需要多少次迭代?)
計算 。
解答 · 答案
一次。此時 ,,所以 ,。每個非零向量都是 的特徵向量,因此第一次直線搜尋已是精確的。