[[1 線形方程式の解法の選択]]&br;
[[2 参考文献および参考書の記述]]&br;
線形方程式, &math(Ax=b); >>> 実対称/複素エルミート, &math(A=A^H); >>> 省メモリ型 >>> 最急降下法
#contents

---------------------------------------------
*概要 [#nfab542d]
-[[CG 法]]の2次関数最小化として導出過程で現れるアルゴリズム．

-[[CG 法]]と比べて，反復当たりの計算量および使用メモリが少ない解法である．ただしその半面，一般に収束性はあまり良くない．

//---------------------------------------------
*導出 [#u80b188b]
~線形方程式&math(A\vec{x}=\vec{b});の真の解を&math(\vec{x}^\ast:=A^{-1}\vec{b});と置く.
この時, 2次関数
#br
//#math(\phi(\vec{x}):= (\vec{x}-\vec{x}^\ast, A(\vec{x}-\vec{x}^\ast)))
CENTER:&math(\phi(\vec{x}):= (\vec{x}-\vec{x}^\ast, A(\vec{x}-\vec{x}^\ast)));
#br
は, &math(\phi(\vec{x}) \geq 0 = \phi(\vec{x}^\ast));を満たす.
そこで, 2次関数&math(\phi(\vec{x}));の最小化問題
#br
#math( \min_{\vec{x} \in C^n } \phi(\vec{x}) )
#br
を(反復法で)解くことで, 線形方程式&math(A\vec{x}=\vec{b});の解を得ることを考える.

**逐次最小化法 [#p7fd3c6e]
~最小化問題(1)を解く単純な反復法として, 適当な初期近似解&math(\vec{x}_0);に対し,

+何らかの方法で, 探索方向ベクトル&math(\vec{p}_k);を定める.
+&math(\phi(\vec{x}_k+\alpha_k \vec{p}_k));を最小化するよう&math(\alpha_k);を設定し, &math(\vec{x}_{k+1} = \vec{x}_k + \alpha_k \vec{p}_k);のように解を更新する.

を繰り返すアルゴリズムが考えられる.
このアルゴリズムは''逐次最小化法''とよばれ, 1次元最小化の係数&math(\alpha_k);は&math(\alpha_k = \frac{ (\vec{r}_k,\vec{p}_k)}{(\vec{p}_k,A\vec{p}_k)});として容易に計算出来る.

**最急降下法 [#h7e9d6fa]
~探索方向ベクトル&math(\vec{p}_k);の設定によって様々な逐次最小化法が存在するが, 
#br
CENTER:&math(\vec{p}_k = -\nabla \phi(\vec{x}_k) = \vec{r}_k);
#br
のように&math(\vec{x}=\vec{x}_k);における&math(\phi(\vec{x}));の最急降下方向に選ぶのが最も自然な方法であろう.
この方法は''最急降下法''と呼ばる.
最急降下法は目的関数&math(\phi(\vec{x}_k));が単調に減少し, 直感的には優れた方法ではあるものの, 計算精度および収束性の面から実用的でないことが知られている.

~ただし，[[CG 法]]で保存されるベクトルが&math(\vec{b}, \vec{x}_k, \vec{r}_k, \vec{p}_k, A\vec{p}_k);の計5本であるのに対し，最急降下法では&math(\vec{b}, \vec{x}_k, \vec{r}_k, A\vec{r}_k);の4本と少ない．
（ここで，$math(\vec{b};は場合によっては不要である．）

//---------------------------------------------
*アルゴリズム [#la457890]
**最急降下法 [#vf9dca7d]
+Set an initial guess &math(\vec{x}_0);
+Compute &math(\vec{r}_0=\vec{b}-A\vec{x}_0);
+For &math(k = 0, 1, 2, \ldots);
+　　&math(\quad \alpha_k = (\vec{r}_k, \vec{r}_k)/ (\vec{r}_k, A\vec{r}_k));
+　　&math(\quad \vec{x}_{k+1} = \vec{x}_k + \alpha_k \vec{r}_k);
+　　&math(\quad \vec{r}_{k+1} = \vec{r}_k - \alpha_k A \vec{r}_k);
+End For

**前処理付き最急降下法 [#da0d7d55]
+Set an initial guess &math(\vec{x}_0);
+Compute &math(\vec{r}_0=\vec{b}-A\vec{x}_0);
+For &math(k = 0, 1, 2, \ldots);
+　　&math(\quad \alpha_k = (K^{-1} \vec{r}_k, \vec{r}_k)/ (K^{-1} \vec{r}_k, A K^{-1} \vec{r}_k));
+　　&math(\quad \vec{x}_{k+1} = \vec{x}_k + \alpha_k K^{-1} \vec{r}_k);
+　　&math(\quad \vec{r}_{k+1} = \vec{r}_k - \alpha_k A K^{-1} \vec{r}_k);
+End For


//---------------------------------------------
*サンプルプログラム [#u9e26e2e]
準備中

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

*参考文献および参考書 [#j0c14a29]
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS