![[JICFuS Wiki]](image/pukiwiki.png "[JICFuS Wiki]")
[[1 線形方程式の解法の選択]]&br; [[2 参考文献および参考書の記述]]&br; 線形方程式, &math(Ax=b); >>> 実非対称/複素非エルミート, &math(A\not=A^H); >>> 高速性重視 >>> 改良法： >>> CGS 法 #contents --------------------------------------------- *概要 [#y341284b] -CGS法は1986年にSonneveldによって提案された非エルミート線形方程式向けのKrylov部分空間法である. -[[Bi-CG 法]]の収束性を加速多項式を用いて改良した, Bi-CG法の積型解法の一種. -加速多項式として, Bi-CG法の残差多項式を利用. -Bi-CG法が反復当たりに&math(A);および&math(A^H);に対する行列ベクトル積を必要とするのに対し, CGS法は&math(A);に対する行列ベクトル積を2回必要とする. -Bi-CG法が反復当たりに&math(A);および&math(A^H);に対する行列ベクトル積を必要とするのに対し, CGS法は&math(A^H);に対する行列ベクトル積は不要で, 代わりに&math(A);に対する行列ベクトル積を2回必要とする. -CGS法は収束した場合にはBi-CG法と比較して優れた収束性を示すものの, 収束が非常に不安定であり, 解を得られない場合も多く存在する. //--------------------------------------------- *導出 [#y765dbc2] 準備中 //--------------------------------------------- *アルゴリズム [#g3c09fe9] **CGS法 [#xc2f5148] +Set an initial guess &math(\vec{x}_0); +Compute &math(\vec{r}_0=\vec{b}-A\vec{x}_0); +Set an arbitrary vector &math(\vec{r}_0^\ast); s.t. &math( (\vec{r}_0, \vec{r}_0^\ast)\neq0);, e.g., &math( \vec{r}_0^\ast = \vec{r}_0); +Set &math(\vec{p}_0 = \vec{u}_0 = \vec{r}_0); +For &math(k = 0, 1, 2, \ldots); + &math(\quad \alpha_k = (\vec{r}_0^\ast, \vec{r}_k)/ (\vec{r}_0^\ast, A\vec{p}_k)); + &math(\quad \vec{q}_{k} = \vec{u}_k - \alpha_k A \vec{p}_k); + &math(\quad \vec{x}_{k+1} = \vec{x}_k + \alpha_k (\vec{u}_k + \vec{q}_k) ); + &math(\quad \vec{r}_{k+1} = \vec{r}_k - \alpha_k A(\vec{u}_k + \vec{q}_k) ); + &math(\quad \beta_k = (\vec{r}_{0}^\ast,\vec{r}_{k+1})/(\vec{r}_0^\ast,\vec{r}_k)); + &math(\quad \vec{u}_{k+1} = \vec{r}_{k+1} + \beta_k \vec{q}_k); + &math(\quad \vec{p}_{k+1} = \vec{u}_{k+1} + \beta_k (\vec{q}_k+\beta_k \vec{p}_k) ); +End For **前処理付きCGS法 [#xc2f5148] +Set an initial guess &math(\vec{x}_0); +Compute &math(\vec{r}_0=\vec{b}-A\vec{x}_0); +Set an arbitrary vector &math(\vec{r}_0^\ast); s.t. &math( (\vec{r}_0, \vec{r}_0^\ast)\neq0);, e.g., &math( \vec{r}_0^\ast = \vec{r}_0); +Set &math(\vec{p}_0 = \vec{u}_0 = \vec{r}_0); +For &math(k = 0, 1, 2, \ldots); + &math(\quad \alpha_k = (\vec{r}_0^\ast, \vec{r}_k)/ (\vec{r}_0^\ast, AK^{-1}\vec{p}_k)); + &math(\quad \vec{q}_{k} = \vec{u}_k - \alpha_k A K^{-1}\vec{p}_k); + &math(\quad \vec{x}_{k+1} = \vec{x}_k + \alpha_k K^{-1}(\vec{u}_k + \vec{q}_k) ); + &math(\quad \vec{r}_{k+1} = \vec{r}_k - \alpha_k AK^{-1}(\vec{u}_k + \vec{q}_k) ); + &math(\quad \beta_k = (\vec{r}_{0}^\ast,\vec{r}_{k+1})/(\vec{r}_0^\ast,\vec{r}_k)); + &math(\quad \vec{u}_{k+1} = \vec{r}_{k+1} + \beta_k \vec{q}_k); + &math(\quad \vec{p}_{k+1} = \vec{u}_{k+1} + \beta_k (\vec{q}_k+\beta_k \vec{p}_k) ); +End For //--------------------------------------------- *サンプルプログラム [#z4fb948d] 準備中 //--------------------------------------------- *適用事例 [#xb92758f] 準備中 *参考文献および参考書 [#k5f39e24] **原著論文 [#mf7e72ba] [20] Peter Sonneveld, CGS, a fast Lanczos-type solver for nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing 1989; 10(1):36–52. **教科書 [#u649329b] [2] Richard Barrett, Michael W. Berry, Tony F. Chan, James Demmel, June Donato, Jack Dongarra, Victor Eijkhout, Roldan Pozo, Charles Romine and Henk A. van der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM: Philadelphia, PA, 1993.&br; P25–27 [14] Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM: Philadelphia, PA, 2003.&br; P229–231 [27] Henk A. van der Vorst, Iterative Krylov Methods for Large Linear Systems, Cambridge University Press: New York, NY, 2003.&br; P102–106 [29] 藤野 清次, 張 紹良, 反復法の数理 (応用数値計算ライブラリ) 朝倉書店, 1996.&br; P46–47
