Tag Archives: Krylov 子空間法

從滿正交法 (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

Krylov 子空間法──線性方程的數值解法 (二):GMRES 與 FOM

本文的閱讀等級:高級 令 為一 階實矩陣。對於非零向量 , 稱為 Krylov 子空間。設 是次數最小的多項式使得 ,稱為 相對 的最小多項式。Krylov 子空間應用於線性方程的數值解法建立於下列基礎 (見“Krylov 子空間法──線性方程的數值解法 (一):Arnoldi 與 Lanczos 算法”): 令 。若 ,則 Krylov 序列 為一線性獨立集,就有 。若 ,則 。 當 ,Arnoldi 算法可求得 Krylov 子空間 的一組單範正交基底 (orthonormal basis) 。 Arnoldi 算法給出 Arnoldi … Continue reading

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

Krylov 子空間法──線性方程的數值解法 (一):Arnoldi 與 Lanczos 算法

本文的閱讀等級:高級 令 為一 階複矩陣, 為一非零向量。向量序列 稱為 Krylov 序列,此序列所生成的子空間稱為 Krylov 子空間 (見“Krylov 子空間法”),記為 。 因為 是有限維空間 的一個子空間,當 不斷增大時,Krylov 序列 最終會是一個線性相關集。設 為最小的正整數使得 ,也就是說 為一個線性獨立集且 。因此,存在唯一數組 滿足 。 定義 次多項式 。 因為 ,我們稱 為 相對於 的最小 (消滅) 多項式 (minimal polynomial)。以下考慮 為可逆矩陣。我們可以斷定 ,否則有 ,即存在次數小於 … Continue reading

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

Krylov 子空間法

本文的閱讀等級:中級 令 為一 階複矩陣, 為一 維非零向量。1931年,俄國應用數學家、海軍工程師克雷洛夫 (Aleksey Krylov) 提出一個創新的想法[1]:運用向量序列 ,稱為 Krylov 序列,計算 的特徵多項式。Krylov 序列的擴張稱為 Krylov 子空間 (或循環子空間),記為 。 明顯地, 是 的一個子空間,故必存在最小正整數 使得 可表示為 的線性組合。如果 , 定義 次多項式 。 因為 ,我們說 是 相對於 的消滅多項式 (annihilating polynomial)。運用類似最小多項式 (minimal polynomial) 的論證方式可證明 (見“最小多項式 (上)”):給定任何矩陣—向量對 … Continue reading

Posted in 特徵分析, 線性代數專欄 | Tagged , , , , , | 10 Comments