Tag Archives: 共軛梯度法

從滿正交法 (FOM) 推導共軛梯度法 (CG)

本文的閱讀等級:高級 考慮線性方程 ,其中 是 階可逆實矩陣, 是非零向量。在線性方程的迭代解法中,滿正交法 (full orthogonalization method,簡稱 FOM) 適用於一般非對稱矩陣,共軛梯度法 (conjugate gradient method,簡稱 CG) 則限定於實對稱正定矩陣。令 為初始猜測解, 為對應近似解 的殘差 (residual),以及 Krylov 子空間 。FOM 與 CG 同屬 Krylov 子空間法,而且有同樣的定義條件: 本文從 FOM 推導 CG,證明 CG 是 FOM 的一種簡約表達。關於 FOM 與 CG 的介紹,請參閱“Krylov … Continue reading

Posted in 線性代數專欄, 數值線性代數 | Tagged , , , | Leave a comment

Krylov 子空間法──線性方程的數值解法 (三):共軛梯度法

本文的閱讀等級:高級 共軛梯度法 (conjugate gradient method) 是一個適用於實對稱正定矩陣的線性方程數值解法。顧名思義,共軛梯度法的核心是共軛 (conjugacy) 和梯度 (一階導數)。共軛能夠加快收斂,梯度則提供正交基底。因為這兩個特性,共軛梯度法的結構簡單優美,儲存量及運算量少,並且無須設定參數。對於大尺寸矩陣,我們往往無法使用直接法求解,譬如 Cholesky 分解 (見“Cholesky 分解”),這時候可以採用以迭代方式計算的共軛梯度法。此外,對於大型非線性最佳化問題,共軛梯度法也是最有效的數值算法之一。

Posted in 線性代數專欄, 數值線性代數 | Tagged , , , , | 2 Comments