[[1 線形方程式の解法の選択]]&br;
[[2 参考文献および参考書の記述]]&br;
線形方程式, &math(Ax=b); >>> 実非対称/複素非エルミート, &math(A\not=A^H); >>> 高速性重視 >>> Bi-CG 法
線形方程式, &math(Ax=b); >>> 実非対称/複素非エルミート, &math(A\not=A^H); >>> 高速性重視 >>> Bi-CR 法
#contents

---------------------------------------------
*概要 [#y341284b]
-Bi-CR法(双共役残差法)は2005年に曽我部, 杉原, 張によって提案された非エルミート線形方程式向けのKrylov部分空間法である.

*概要 [#k0b28ebd]
-初期近似解を&math(\vec{x}_0);, 対応する初期残差を&math(\vec{r}_0:=\vec{b}-A\vec{x}_0);と置く.
この時, Bi-CG法の&math(k);反復目の近似解&math(\vec{x}_k);は,
#br
CENTER:&math(\vec{x}_k \in \vec{x}_0 + {\mathcal K}_k(A,\vec{r}_0), \quad {\mathcal K}_k(A,\vec{r}_0) := {\bf span}\{\vec{r}_0, A\vec{r}_0, \ldots, A^{k-1}\vec{r}_0 \});
#br
のように, 初期近似解&math(\vec{x}_0);とクリロフ部分空間&math({\mathcal K}_k(A,\vec{r}_0));で張るアフィン空間に含まれ, 残差ベクトル&math(\vec{r}_k=\vec{b}-A\vec{x}_k);が
#br
CENTER:&math(\vec{r}_k \bot A^H{\mathcal K}_k(A^H,\vec{r}^\ast_0));
#br
の直交条件(Petrov-Galerkin条件)を満たすように設定される.
ここで, &math(\vec{r}_0^\ast);は初期シャドウ残差と呼ばれ, &math( (\vec{r}_0, \vec{r}_0^\ast)\neq0);となるように設定する. 
一般には&math(\vec{r}_0^\ast = \vec{r}_0);と設定される.

*参考文献および参考書 [#pdc04787]
-Krylov部分空間の基底として, Bi-Lancoz原理によって生成された双直交基底を用いる.
Bi-Lanczos原理はArnoldi原理と異なり短い漸化式を持つため, [[GMRES 法]], [[GCR 法]], [[FOM 法]]と異なり, 一般にはリスタートやトランケート等の技法は必要としない.
その代わりに, 反復当たりに&math(A);だけでなく&math(A^H);に対する行列ベクトル積を必要とする.

**原著論文 [#b732c5a9]
[6] Roger Fletcher, Conjugate gradient methods for indefinite systems, In: Lecture Notes in Mathematics, G. Alistair Watros (ed.), vol. 506, Springer-Verlag: New York, NY, 1976; 73–89.
-[[CR 法]]を非エルミート線形方程式へ拡張した解法であり, Bi-CR法をエルミート線形方程式に対して適用した場合は, CR法と数学的に同値である.

**教科書 [#u75370e4]
[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;
P21–23
//---------------------------------------------
*導出 [#y765dbc2]
準備中

[14] Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM: Philadelphia, PA,
2003.&br;
P222–224
//---------------------------------------------
*アルゴリズム [#g3c09fe9]
**Bi-CR法 [#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{r}_0, \vec{p}_0^\ast = \vec{r}_0^\ast);
+For &math(k = 0, 1, 2, \ldots);
+　　&math(\quad \alpha_k = (\vec{r}_k^\ast, A\vec{r}_k)/ (A^H\vec{p}_k^\ast, A\vec{p}_k));
+　　&math(\quad \vec{x}_{k+1} = \vec{x}_k + \alpha_k \vec{p}_k);
+　　&math(\quad \vec{r}_{k+1} = \vec{r}_k - \alpha_k A \vec{p}_k);
+　　&math(\quad \vec{r}_{k+1}^\ast = \vec{r}_k^\ast - \bar{\alpha}_k A^H \vec{p}_k^\ast);
+　　&math(\quad \beta_k = (\vec{r}_{k+1}^\ast,A\vec{r}_{k+1})/(\vec{r}_k^\ast,A\vec{r}_k));
+　　&math(\quad \vec{p}_{k+1} = \vec{r}_{k+1} + \beta_k \vec{p}_k);
+　　&math(\quad \vec{p}_{k+1}^\ast = \vec{r}_{k+1}^\ast + \bar{\beta}_k \vec{p}_k^\ast);
+　　&math(\quad A\vec{p}_{k+1} = A\vec{r}_{k+1} + \beta_k A\vec{p}_k);
+End For

[27] Henk A. van der Vorst, Iterative Krylov Methods for Large Linear Systems, Cambridge University
Press: New York, NY, 2003.&br;
P95–98
**前処理付きBi-CR法 [#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 = K^{-1}\vec{r}_0, \vec{p}_0^\ast = K^{-H} \vec{r}_0^\ast);
+For &math(k = 0, 1, 2, \ldots);
+　　&math(\quad \alpha_k = (K^{-H}\vec{r}_k^\ast, AK^{-1}\vec{r}_k)/ (K^{-H}A^{H}\vec{p}_k^\ast, A\vec{p}_k));
+　　&math(\quad \vec{x}_{k+1} = \vec{x}_k + \alpha_k \vec{p}_k);
+　　&math(\quad \vec{r}_{k+1} = \vec{r}_k - \alpha_k A \vec{p}_k);
+　　&math(\quad \vec{r}_{k+1}^\ast = \vec{r}_k^\ast - \bar{\alpha}_k A^H \vec{p}_k^\ast);
+　　&math(\quad K^{-H}\vec{r}_{k+1}^\ast = K^{-H}\vec{r}_k^\ast - \bar{\alpha}_k K^{-H}A^H \vec{p}_k^\ast);
+　　&math(\quad \beta_k = (K^{-H}\vec{r}_{k+1}^\ast, AK^{-1}\vec{r}_{k+1})/(K^{-H}\vec{r}_k^\ast, AK^{-1}\vec{r}_k));
+　　&math(\quad \vec{p}_{k+1} = K^{-1} \vec{r}_{k+1} + \beta_k \vec{p}_k);
+　　&math(\quad \vec{p}_{k+1}^\ast = K^{-H} \vec{r}_{k+1}^\ast + \bar{\beta}_k \vec{p}_k^\ast);
+　　&math(\quad A\vec{p}_{k+1} = AK^{-1} \vec{r}_{k+1} + \beta_k A\vec{p}_k);
+End For

[23] Masaaki Sugihara and Kazuo Murota, Theoretical Numerical Linear Algebra, Iwanami Press:
Tokyo, 2009, (in Japanese).&br;
P181–190

[29] 藤野 清次, 張 紹良, 反復法の数理 (応用数値計算ライブラリ)　朝倉書店, 1996.&br;
P38–41
//---------------------------------------------
*サンプルプログラム [#z4fb948d]
準備中

//---------------------------------------------
*適用事例 [#xb92758f]
準備中

*参考文献および参考書 [#pdc04787]

**原著論文 [#b732c5a9]
[18] Tomohiro Sogabe, Masaaki Sugihara and Shao-Liang Zhang, An extension of the conjugate residual method for solving nonsymmetric linear systems, Transactions of the Japan Society for Industrial and Applied Mathematics 2005; 15(3):445–459, (in Japanese).

[19] Tomohiro Sogabe, Masaaki Sugihara and Shao-Liang Zhang, An extension of the conjugate residual method to nonsymmetric linear systems, Journal of Computational and Applied Mathematics 2009; 226(1):103–113.

**教科書 [#u75370e4]
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS