[[1 線形方程式の解法の選択]]&br;
[[2 参考文献および参考書の記述]]&br;
線形方程式, &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);と設定される.

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

-[[CR 法]]を非エルミート線形方程式へ拡張した解法であり, Bi-CR法をエルミート線形方程式に対して適用した場合は, CR法と数学的に同値である.

//---------------------------------------------
*導出 [#y765dbc2]
準備中

//---------------------------------------------
*アルゴリズム [#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

**前処理付き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


//---------------------------------------------
*サンプルプログラム [#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