1 線形方程式の解法の選択
2 参考文献および参考書の記述
線形方程式,
>>> 実対称/複素エルミート,
>>> 省メモリ型 >>> 最急降下法
概要 †
- CG 法の2次関数最小化として導出過程で現れるアルゴリズム.
- CG 法と比べて,一般に収束性はあまり良くない.
ただし,CG 法で保存する必要のあるベクトルは
の計4本であるのに対し,最急降下法では
の3本と少なく,メモリの制約がある場合には選択肢の一つとなりうる.
導出 †
線形方程式
の真の解を
と置く.
この時, 2次関数
は,
を満たす.
そこで, 2次関数
の最小化問題

・・・(1)
を(反復法で)解くことで, 線形方程式
の解を得ることを考える.
逐次最小化法 †
最小化問題(1)を解く単純な反復法として, 適当な初期近似解
に対し,
- 何らかの方法で, 探索方向ベクトル
を定める.
を最小化するよう
を設定し,
のように解を更新する.
を繰り返すアルゴリズムが考えられる.
このアルゴリズムは逐次最小化法とよばれ, 1次元最小化の係数
は
として容易に計算出来る.
最急降下法 †
探索方向ベクトル
の設定によって様々な逐次最小化法が存在するが,
のように
における
の最急降下方向に選ぶのが最も自然な方法であろう.
この方法は最急降下法と呼ばる.
最急降下法は目的関数
が単調に減少し, 直感的には優れた方法ではあるものの, 計算精度および収束性の面から実用的でないことが知られている.
アルゴリズム †
最急降下法 †
- Set an initial guess

- Compute

- For

-

-

-

- End For
前処理付き最急降下法 †
- Set an initial guess

- Compute

- For

-

-

-

- End For
サンプルプログラム †
準備中
適用事例 †
準備中
参考文献および参考書 †