Tag Archives: Lanczos 算法

從滿正交法 (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 子空間法──線性方程的數值解法 (一):Arnoldi 與 Lanczos 算法

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

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